一、简介

格规约是将格的基向量转换为正交性更好、长度更短的新基向量的数学方法，主要应用于多输入多输出（MIMO）系统信号检测和密码分析领域。其核心在于通过算法改善基向量正交性，典型应用包括MIMO检测器设计、最短向量问题（SVP）求解及公钥密码系统分析。

二、SVP与CVP

1.SVP（shortest Vector Problem）最短向量问题

在这一个格L中最短的非零向量即寻找一个v满足欧几里得范数最小（指该集合的每一个元素的平方和再开方）范数就是指长度。注意，格中最短的向量可能不止一个。

格基规约：找到最接近正交的基向量

假设v不是基中的向量，此刻该向量一定可以通过在其他基向量方向的投影来得到一个更短的向量

2.CVP（Closet Vector Problem）最近向量问题

给定一个不在格内的向量w，找到一个格内向量v，满足||v-w||最小

与SVP的关系：有些问题可以通过对CVP加上一维之后转变为SVP问题，因为SVP相比CVP稍微简单一些

三、格攻击理论

1.Minkowski凸体定理

（1）定理

场景：

$L \subset \mathbb{R}^n:一个满秩格$

$S \subset \mathbb{R}^n:要研究的几何形状（一个点集)$

$定理：设S是 \mathbb {R}^n 中的一个子集，若它同时满足以下三个条件：$

$1. 凸性：对于 S 中任意两点 x, y ，连接它们的整个线段都在 S 中
$

$2. 中心对称性：如果点 x 在 S 中，那么它的对称点 -x 也在 S 中$

$3. 体积足够大： S 的体积（勒贝格测度）满足 \text{Vol}(S) > 2^n \cdot \det(L)$

$那么，集合 S 中一定包含一个非零的格点。即，存在：$

$ \mathbf{0} \neq \mathbf{v} \in L \cap S$

$
甚至更强的结论：如果 S 还是紧致的（在 \mathbb{R}^n 中闭且有界），那么条件可以放宽到 \text{Vol}(S) \geq 2^n \cdot \det(L) ，结论依然成立$

（2）证明

$目标：证明如果 \text{Vol}(S) > 2^n \det(L) ，那么 S 包含非零格点$

$1. 缩放：考虑将 S 缩小为原来的一半，得到集合：$

$\frac{1}{2}S = { \frac{1}{2}x : x \in S } $

$ · 关键性质： \text{Vol}(\frac{1}{2}S) = (\frac{1}{2})^n \text{Vol}(S) > \det(L) 。（因为 \text{Vol}(S) > 2^n \det(L) ，除以 2^n 后大于 \det(L) ）$

$2. 平移：现在把缩小的集合 \frac{1}{2}S 平移到每一个格点 \mathbf{v} \in L 上，得到一族集合：$

$ \frac{1}{2}S + \mathbf{v}$

$3.矛盾论证$

$假设所有这些平移后的集合两两不交（即没有任何重叠）$

$ 取一个以原点为中心、边长为 N 的巨大立方体 C_N 。这个立方体内包含大约 (N^n / \det(L)) 数量级的格点$

$每个平移集合 \frac{1}{2}S + \mathbf{v} 的体积都是 \text{Vol}(\frac{1}{2}S)$

$因此，所有这些落在 C_N 内的“小S副本”的总体积大约为：$

$(格点数量) × (每个小S的体积) ≈ (N^n / det(L)) × Vol(½S)$

$由于我们假设它们不重叠，这个总体积必须小于等于大立方体 C_N 本身的体积 N^n$

$所以我们得到不等式：(N^n / det(L)) × Vol(½S) ≤ N^n，两边约去 N^n ，得到：$

$Vol(½S) ≤ det(L)。$

$但这与我们一开始的条件 Vol(½S) > det(L) ，矛盾！$

$故而必然存在两个不同的格点 \mathbf{v} \neq \mathbf{w} \in L ，使得它们对应的平移集合相交：$

$ (\frac{1}{2}S + {v}) \cap (\frac{1}{2}S + {w}) \neq \varnothing$

$4.构造$

$ 设这个交集中的一点为 {z} ，那么 {z} = \frac{1}{2}{s}_1 + {v} = \frac{1}{2}{s}_2 + {w} ，其中 {s}_1, {s}_2 \in S$

$ 整理得： {v} - {w} = \frac{1}{2}{s}_2 - \frac{1}{2}{s}_1 = \frac{1}{2}({s}_2 - {s}_1) $

$注意到右边：因为 S 是凸且中心对称的，所以如果 {s}_2, -{s}_1 \in S ，那么它们的中点 \frac{1}{2}({s}_2 + (-{s}_1)) = \frac{1}{2}({s}_2 - {s}_1) 也一定在 S 中$

$因此，我们找到了一个非零的格点 \mathbf{v} - \mathbf{w} \in L ，并且它就在原来的集合 S 中$

证毕！

证明重点思路是：通过“缩小一半再平移”的操作，将“在一个大集合里找一个格点”的问题，转化为了“许多小集合是否重叠”的体积问题，并利用凸对称性从重叠点构造出了目标格点。

2.Hermite定理

（1）定理

$设 L \subset \mathbb{R}^n 是一个秩为 n 的满秩格$

$
Hermite定理：存在一个只与维度 n 有关的常数 \gamma_n （称为 Hermite常数），使得对于任何这样的格 L ，都存在一个非零向量 \mathbf{v} \in L ，满足：$

$|\mathbf{v}|^2 \le \gamma_n \cdot (\det(L))^{2/n}$

$· \det(L) : 它代表了格的基本“密度”或“每一点所占的平均体积$

$ 几何意义： (\det(L))^{1/n} 可以粗略理解为格在 n 维空间中的“平均边长”$

$· \gamma_n : Hermite常数。它是一个只依赖于维度 n 的普适常数$

$它的确切值只在少数维度已知（如 \gamma_1 = 1, \gamma_2 = 2/\sqrt{3}, \gamma_3 = 2^{1/3}, \gamma_4 = \sqrt{2}, \gamma_8 = 2 ）$

$ 对于一般的 n ，我们知道它的增长上界： \gamma_n \le \frac{2}{\pi} \Gamma(\frac{n}{2}+1)^{2/n} \sim \frac{2n}{\pi e} （其中 \Gamma 是Gamma函数）。当 n 很大时，大约以 O(n) 线性增长$

（2）证明

用Minkowski证明Hermite

$目标：证明存在非零 \mathbf{v} \in L ，使得 |\mathbf{v}| \le c_n (\det(L))^{1/n}$

$1.构造合适的集合S：$

选择 S 为一个以原点为中心的n维球（球体），半径为 r

检查Minkowski定理的条件：

前两个略了

$· 体积条件：球的体积是 $

$ V_n(r) = \frac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)} r^n$

$应用Minkowski定理，所以需要 Vol(S) ≥ 2^n det(L)（对于紧致的球，可以用等号）。即：
$

$ \frac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)} r^n \ge 2^n \det(L)$

$2.解出半径：$

$r^n \ge \frac{2^n \Gamma(\frac{n}{2}+1)}{\pi^{n/2}} \det(L)$

$ r \ge \left( \frac{2^n \Gamma(\frac{n}{2}+1)}{\pi^{n/2}} \right)^{1/n} (\det(L))^{1/n}$

$令 r_0 = \left( \frac{2^n \Gamma(\frac{n}{2}+1)}{\pi^{n/2}} \right)^{1/n} (\det(L))^{1/n}$

$3.应用Minkowski$

$对于半径为 r_0 的球 S_0 ，其体积 Vol(S_0) = 2^n det(L)。$

$由于球是紧致的，又Minkowski定理，在这个球 S_0 内，存在一个非零的格点 \mathbf{v}$

$又 \mathbf{v} 在球内，它的长度（到原点的距离）必然不超过球的半径 r_0，即：$

$这样我们不仅证明了这样的短向量存在，还直接给出了一个具体的上界常数 c_n $

$（虽然这个 c_n 不是最优的Hermite常数 \sqrt{\gamma_n} ，但它确实是一个只与维度 n 有关的常数）$

3.高斯启发式

（1）公式

$对于一个满秩 n 维格 L \subset \mathbb{R}^n ，其最短向量长度 \lambda_1(L) 的高斯启发式值（记作 \text{GH}(L)）定义为：$

$\text{GH}(L)= \sqrt{\frac{n}{2\pi e}} \cdot (\det(L))^{1/n}$

$在一个随机选择的格中的最短非零向量满足:$

$| \mathbf v_{shortest} | \approx \sigma(L)$

四、应用

（1）典

（2）配平

如果仅使用上面应用中的知识的话，在实际应用中会发现构造出来的格基很多都不会符合条件，其实还需要结合一个配平的技巧

（3）总结

找小未知数，构造线性方程、短向量和格基
$配平使得∥w∥⪅σ(L(B))$
LLL解短向量，注：维度不能过高
短向量中提取未知数

五、类型

1.NTRU

2.HNP

（1）简介

HNP(Hidden Number Problem)隐藏数问题是格密码学中的一个非常重要的归约模型。

它在密码学中有着经典的应用，比如：

攻击泄露部分比特的Diffie-Hellman密钥
攻击许多签名算法（如DSA/ECDSA）在非随机k（或部分k泄露）情况下的密钥恢复。

（2）原理

$给定一个Oα,g(x)，每次访问会返回α⋅gx(modp)的高k位（MSB_k),目标是解出α，而且k越小越好。$

$给出n组方程： $

$\beta_i \equiv \alpha_i x_0 \pmod q $

对于题目来说

$\beta_i 拆成泄露的高位B_i 和未知的低位b_i相加：$

$A_i*x_0 \equiv B_i+b_i \pmod q$

$首先选一组定义为第0组，满足gcd(A_0,q)=1，即A_0模q可逆：$

$x_0 \equiv A_0^{-1}(B_0+b_0) \pmod q$

$然后对i=1,2,…的每一组代入然后消去x_0,最终得到：$

$A_0^{-1}(A_iB_0-A_0B_i)+A^{-1}A_ib_0 \equiv b_i \pmod q$

$令D_i\equiv A_0(A_iB_0-A_0B_i)\pmod q,E_i\equiv A_0^{-1}A_i \pmod q展开模数q： $

$D_i+E_ib_0-k_iq=b_i$

$记q是m位的，\beta_i共泄露s位。那么D_i+E_ib_0-b_i是2m-s位，k_i是m-s位，最终所有未知数都m-s位$

$令常数R=2^{m-s}，构造格L(B)：$

$使得：$

$\mathbf vB=(k_1,k_2,…,k_{n-1},b_0,1)B=(b_1,b_2,…,b_{n-1},b_0,R)=\mathbf w$

$使得：$

$| \mathbf w | \approx 2^{m-s}$

$\sigma(L(B)) \approx 2^{\frac{nm-s}{n+1}}$

$若 |\mathbf w| \leq \sigma(L(B)):$

$m-s \leq \frac{nm-s}{n+1}$

$化简得：$

$sn \geq m$

$那么若| \mathbf w | \leq \sigma(L(B))：$

$s（n+1) \geq m$

另外，实际用的时候调BKZ的效果会比LLL好很多，而且block_size越大越好，但是耗时会越长。

3.背包密码

（1）简介

Merkle-Hellman背包算法由Merkle与Hellman于1977年提出，是一种基于背包问题的公钥加密算法。其核心原理是通过将易解背包问题转化为难解背包问题，分别构造私钥与公钥完成加解密。该算法属于早期基于组合数学难题的公钥密码体制，其实现流程包含简单背包求解和密钥转换步骤。该算法后续被发现存在多种破译方法，包括利用Euclid除法、Shamir破译方法及格的规约基算法等。

（2）概念

简单背包（超递增序列）：存在快速解密算法（私钥，陷门）。
困难背包（一般序列）：没有快速算法，只能穷举（公钥，伪装）。
密码设计：用一个可逆的变换，把简单背包伪装成困难背包公开出去。

超递增数列

$一个正整数序列(b_1,b_2,…,b_n)，若\forall i>1 有：$

$b_i>b_1+b_2+…+b_{i-1}$

（3）原理

Ⅰ.加密

$生成私钥 n位（超递增序列），选择模数M（M>\sum^{n}_{i=1}b_i）$
$选择乘数W，1<W<M,gcd(M,W)=1$
$计算公钥序列 a_i \equiv W*b_i \pmod M$
$明文：n位二进制串m=(m_1,m_2,…,m_n),其中m_i \in {0,1},则密文C=\sum^n_{i=1}m_ia_i$

1
2
3

def encrypt(plaintext_bits, public_key):
    # plaintext_bits 是一个0/1列表，长度等于公钥长度
    return sum(bit * pk for bit, pk in zip(plaintext_bits, public_key))

Ⅱ.解密（贪心算法）

$模逆还原：C’ \equiv {W^{-1}C} \equiv{W^-1*\sum ^n_{i-1}m_iWb_i} \equiv \sum^n_{i=1}m_ib_i \pmod M$

$又M>\sum^n_{i=1}b_i,那么M> \sum ^n_{i=1}m_ib_i，故而C’= \sum ^n_{i=1}m_ib_i$

$贪心算法：若S \geq b_n,则x_n=1,S’=S-b_n，继续比较；否则x_n=0$

def decrypt(ciphertext, private_key, M, W):
    b_seq, M, W = private_key
    W_inv = inverse_mod(W, M)
    C_prime = (W_inv * ciphertext) % M

    # 对超递增序列 b_seq 使用贪心算法解密
    plain_bits = []
    for bi in reversed(b_seq): # 从大到小
        if C_prime >= bi:
            plain_bits.append(1)
            C_prime -= bi
        else:
            plain_bits.append(0)
    plain_bits.reverse() # 因为我们是从后往前解的
    return plain_bit

（4）LLL

Ⅰ.

$已知S=\sum^{n-1}_{i=0} x_iM_i和M_i，求x_i \in {1,0 }$

$构造矩阵：$

$那么存在 \mathbf v：$

$\mathbf v=[x_0,x_1,…,x_{n-1},-1]$

$使得 \mathbf vM=\mathbf w:$

$\mathbf w=[2x_0-1,2x_1-1,…,2x_{n-1}-1,0]$

$这样构造的好处是w中元素为{-1,0,1},接下来进行估算$

$不妨设min{M_i}=M_{min},那么：$

$det(L(B))=2^n|S-\frac{1}{2} \sum^{n-1}{i=0}M_i|=2^n| \sum^{n-1}{i=0}(x_i- \frac{1}{2})M_i| \geq 2^n|\sum^{n-1}{i=0}(x_i-\frac{1}{2})M{min}| \geq 2^n{\frac{1}{2}nM_{min}}$

$故而：$

$|w|=\sqrt{\sum^{n-1}_{i=0}(2x_i-1)^2}=\sqrt n$

$\sigma(L(B))= {\sqrt {\frac{n}{2e\pi}}det(L(B))^\frac{1}{n}} \geq {\sqrt {\frac{n}{2e\pi}}(2^n\frac{1}{2}nM_{min})^{\frac{1}{n}}}$

$有时需要给最后一列配一个系数（通常选1或\sqrt n量级）$

Ⅱ.

$构造矩阵：$

$存在\mathbf v:$

$\mathbf v=(x_1,x_2,…,x_n,-1)$

$使得 \mathbf vL=\mathbf w:$

$\mathbf w=(x_1,x_2,…,x_n,0)$

Ⅲ .带模的背包加密

$由S=\sum^n_{i=0}x_iM_i \pmod p:$

$S=\sum^n_{i=0}x_iM_i-kp$

$构造矩阵：$

$\begin{pmatrix}
2&&&&&M_1\
&2&&&&M_2\
&&\ddots&&\
&&&2&0&M_n\
1&1&\cdots&1&1&S\
0&0&\cdots&0&0&P
\end{pmatrix}$

$存在\mathbf v:$

$\mathbf v=(x_1,x_2,…,x_n,-1,k)$

$使得 \mathbf vL=\mathbf w:$

$\mathbf w=(2x_1-1,2x_2-1,…,2x_n-1,-1,0)$

注意

$记M为背包公钥，S为密文，n=len(M)$

$背包密度为d=\frac{n}{\log_2(max(M_i))}$

$当密度d<0.9408时$

大概率有唯一解，可使用格基规约（LLL、BKZ）在多项式时间内找到解

当密度d>1时

可能有多解

*from* Crypto.Util.number *import* *
*import* math
M=[M1,M2,M3,...,Mn]
n=len(M)
max=max(M)
density=n/math.log2(max)
print(f"{density:.6f}")

调整密度

降低密度：

$增大元素值：增大max(M_i)$
$减少元素数量：减小n$

六、算法工具

1.LCG（线性同余生成器）

（1）简介

线性同余发生器（Linear congruential generator），简称LCG，是一种能产生具有不连续计算的伪随机序列的分段线性方程的算法，它代表了最古老和最知名的伪随机序列生成器算法之一，其理论相对容易理解，并且易于实现和快速，特别是在可以通过存储位截断提供模运算的计算机硬件上。

（2）计算公式

生成器由循环关系定义：

$X_{n+1}=aX_n+c \pmod m$

$其中，X为伪随机序列，m表示模量，a表示乘数（a<m)，c表示增量(c<m)，X_0表示初始值或种子(X_0<m)$

$c是指定生成器的整数常量:$

$若c=0，则称为乘法同余发生器$
$若c \neq0 ，则称为混合同余发生器$

$取模优化：当m=2^k时，取模运算可以用位与(&)代替$

$X_{n+1}=(aX_n+c)& (m-1)$

（3）区间长度

周期长度：

LCG的周期最多为m，达到最大周期的条件：

(c,m)=1
a-1能被m的所有质因数整除
若m为4的倍数，那么a-1也必须为4的倍数

常见参数：

m为素数，c=0
m为2的幂
$c \neq 0$

（4）例子

Ⅰ.已知连续完整输出，恢复参数(a,c,m)

$先利用差分消除c：$

$x_2-x_1=a(x_1-x_0) \pmod m$

$x_3-x_2=a(x_2-x_1) \pmod m$

$那么：$

$T=(x_2-x_1)^2-(x_3-x_2)(x_1-x_0)=0 \pmod m$

$收集多个T_i,计算他们的最大公约数得到m$

$然后解线性方程组求a,c$

from sage.all import *

# 假设我们观察到的输出序列
x = [123, 456, 789, 1023]  # 示例数据，实际需要真实输出

# 计算候选模数 m
T1 = (x[2] - x[1])^2 - (x[3] - x[2]) * (x[1] - x[0])
T2 = (x[3] - x[2])^2 - (x[4] - x[3]) * (x[2] - x[1])  # 如果有更多数据
m_candidate = gcd(T1, T2)
print("恢复的模数 m =", m_candidate)

# 恢复 a
a = ((x[2] - x[1]) * inverse_mod(x[1] - x[0], m_candidate)) % m_candidate
# 恢复 c
c = (x[1] - a * x[0]) % m_candidate
print("恢复的乘数 a =", a)
print("恢复的增量 c =", c)

Ⅱ.已知参数(a,c,m)和部分输出（高位）

$记u_i为高k位,e_i为低s位，有：$

$u_{i+1} \cdot 2^{s} + e_{i+1} = a(u_i \cdot 2^{s} + e_i) + c \pmod m$

$整理得：$

$a e_i - e_{i+1} = (u_{i+1} - a u_i) \cdot 2^{s} - c \mod m$

$记 D_i = (u_{i+1} - a u_i) \cdot 2^{s} - c，则存在整数 k_i 使得：$

$a e_i - e_{i+1} - k_i m = D_i$

$构造向量：$

$\mathbf{v} = (e_0, e_1, \dots, e_t, k_0, \dots, k_{t-1}, 1)$

$放大因子K=2^S,构造矩阵：$

from sage.all import *
import random

# 参数设置
bits = 128  # 内部状态位数
m = random_prime(2^bits, lbound=2^(bits-1))
a = random.randint(2, m-1)
c = random.randint(2, m-1)
x0 = random.randint(0, m-1)

print(f"真实参数: m={m}, a={a}, c={c}, x0={x0}")

# 模拟截断输出（只保留高 bits-trunc 位）
trunc = 40  # 被截断的低位比特数
s = trunc  # 未知的低位比特数
k = bits - trunc  # 已知的高位比特数

def truncate(x):
    return x >> s  # 保留高位

# 生成观测序列
seq_len = 10  # 观测数量
x = [0] * seq_len
u = [0] * seq_len
x[0] = x0
u[0] = truncate(x[0])
for i in range(1, seq_len):
    x[i] = (a * x[i-1] + c) % m
    u[i] = truncate(x[i])

print("观测到的高位 u_i:", u)

# 攻击：构造格
d = seq_len - 1  # 方程数量（从 i=0 到 i=d-1）
K = 2^s  # 放大因子

# 构建矩阵 B，维度 (d+1) x (d+1)
B = []
for i in range(d):
    row = [0] * (d+1)
    row[i] = K * m
    B.append(row)

# 最后一行：系数为 K*a, K*a^2, ..., K*a^d, K
last_row = []
for i in range(1, d+1):
    # 注意：我们利用关系 e_i ≈ a^i e_0 + ...，这里简化构造
    last_row.append(K * pow(a, i, m))
last_row.append(K)
B.append(last_row)

B = matrix(ZZ, B)

# LLL规约
L = B.LLL()

# 寻找短向量并恢复 e0
found = False
for row in L:
    if abs(row[-1]) == K:
        # 根据向量形式恢复 e0
        # 这里假设短向量形式为 [K*e1, K*e2, ..., K*ed, K*e0?]
        # 注意构造不同，恢复方式不同，这里仅示例
        candidate_e0 = row[-2] // K  # 需要根据具体构造调整
        if 0 <= candidate_e0 < 2^s:
            candidate_x0 = (u[0] << s) + candidate_e0
            # 验证候选
            test_x = candidate_x0
            match = True
            for i in range(1, seq_len):
                test_x = (a * test_x + c) % m
                if truncate(test_x) != u[i]:
                    match = False
                    break
            if match:
                print(f"成功恢复 x0 = {candidate_x0}")
                found = True
                break

if not found:
    print("攻击失败，可能需要更多数据或调整构造")

参考🤓：

https://tover\.xyz/p/LLL\-attack\-equation/

https://happy\-superman\.github\.io/2024/08/02/2024\-08\-02\-%E6%A0%BC%E5%AF%86%E7%A0%81%E7%9B%B8%E5%85%B3/

https://dexterjie\.github\.io/2024/07/29/%E8%83%8C%E5%8C%85%E5%AF%86%E7%A0%81/\#Lattice1