LLL 格基约化：背包密码是怎样倒下的

全文分三层：

1. 通俗理解：格、好基与坏基，背包问题
2. 实际用处：背包密码的兴衰、从侧信道泄露中恢复私钥、后量子参数选择
3. 数学原理：二维的高斯约化、LLL 的思路、背包密码与它的格攻击，附手算例子

第一层：通俗理解

1.1 格、好基与坏基

在平面上取两个向量 $b_1, b_2$，它们所有的整数组合 $a_1 b_1 + a_2 b_2$ 构成一片规则排列的点，叫格。

同一片点阵可以用不同的基来生成。比如整数格 $\mathbb{Z}^2$（所有整数坐标点）：

• 好基：$(1, 0)$ 和 $(0, 1)$，短，互相垂直；
• 坏基：$(5, 8)$ 和 $(8, 13)$，长，几乎平行。可以验证它们的整数组合恰好也能生成所有整数点（行列式 $= 5 \cdot 13 - 8 \cdot 8 = 1$）。

拿到坏基的人，很难看出"这片格里最短的向量只有长度 1"。这正是格密码的基本思路：公钥给坏基，私钥是好基（见《后量子密码》）。

1.2 背包问题

给你一堆重量各异的物品 $\{82, 123, 287, 83, 248, 373, 10, 471\}$，问：哪几件加起来恰好重 $881$？

这是子集和问题，一般情形是 NP 完全的，物品多了只能接近穷举。1978 年 Merkle 和 Hellman 据此设计了最早的公钥密码之一：挑哪几件就是明文的比特，总重量就是密文。

1.3 为什么倒下

Merkle–Hellman 为了让合法接收者能解密，在物品重量里藏了一个"暗门"结构。1982 年 Shamir 利用这种结构把它破解了；不久之后人们发现，更通用的办法是把背包问题写成一个格，秘密的比特串对应格中一个异常短的向量，LLL 一跑就出来了。

第二层：实际用处

背包密码的兴衰

LLL 在今天的用途

• 从部分泄露中恢复 ECDSA 私钥：ECDSA 的随机数 $k$ 哪怕只泄露每次签名的几个比特（比如时间侧信道），收集几百个签名后就能构造一个格，用 LLL 或 BKZ 解出私钥。这叫"隐藏数问题"（HNP）。TPM-Fail（2019）、Minerva（2019）等攻击都是这么做的。（参见《椭圆曲线》 里 $k$ 重复的极端情况。）
• Coppersmith 方法：求模多项式方程的小根，可以攻击小指数 RSA 的某些用法，或者在知道 $p$ 一半比特时分解 $n$。
• 后量子密码的参数选择：Kyber、Dilithium 的安全参数，就是按"最好的格约化算法（BKZ）要花多少时间"来估算的。LLL 在这里是"敌人"，用来衡量防线有多高。
• 密码学以外：整数关系探测（发现数学常数之间的恒等式）、整数规划、GPS 载波相位模糊度求解。

第三层：数学原理

3.1 格的定义

给定线性无关的向量 $b_1, \dots, b_n \in \mathbb{R}^m$，格为

$$L = \Big\{\sum_i a_i b_i : a_i \in \mathbb{Z}\Big\}.$$

两组基 $B$、$B'$ 生成同一个格，当且仅当 $B' = UB$，其中 $U$ 是幺模矩阵（整数矩阵，行列式 $\pm 1$），即 $U \in GL_n(\mathbb{Z})$。所以"换基"就是在群 $GL_n(\mathbb{Z})$ 里乘一个元素。

格的行列式（基本平行体的体积）$|\det B|$ 不随换基改变，是格的不变量。

3.2 二维：高斯约化，就是向量版的欧几里得算法

二维情形下有一个精确算法（Lagrange–Gauss）：反复用短向量去"削"长向量，直到削不动为止。这和求最大公因数时"大数减小数"完全是同一个思路。

3.3 LLL 的思路

高维时没有精确又高效的算法（求最短向量 SVP 是 NP 难的），LLL 做的是近似：

1. 尺寸约化：对每个 $b_i$，减去前面向量的整数倍，让它在 Gram–Schmidt 方向上的分量尽量小（就是二维高斯约化的推广）；
2. Lovász 条件：如果相邻两个向量的顺序"不好"（后一个的 Gram–Schmidt 长度比前一个短太多），就交换它们，再回到第 1 步。

可以证明它在多项式时间内结束，输出的第一个向量满足

$$\|b_1\| \le 2^{(n-1)/2} \cdot \lambda_1(L),$$

$\lambda_1$ 是真正的最短向量长度。最坏情况下这个近似因子是指数级的，但实际表现比理论好得多，在几十维时经常直接找到最短向量。更强的 BKZ 算法在 LLL 基础上分块求精确解，用时间换质量。

3.4 Merkle–Hellman 与它的格攻击

私钥：一个超递增序列 $w = (2, 3, 7, 14, 30, 57, 120, 251)$（每项大于前面所有项之和），模数 $q = 491 > \sum w_i$，乘数 $r = 41$，$\gcd(r, q) = 1$。

公钥：$b_i = r w_i \bmod q$，即 $b = (82, 123, 287, 83, 248, 373, 10, 471)$。它看上去是一般的背包，超递增结构被模乘"藏起来"了。

格攻击：构造以下面各行为基的格（最后一列是重量）：

$$\begin{pmatrix} 1 & 0 & \cdots & 0 & b_1 \\ 0 & 1 & \cdots & 0 & b_2 \\ \vdots & & \ddots & & \vdots \\ 0 & 0 & \cdots & 1 & b_n \\ 0 & 0 & \cdots & 0 & -C \end{pmatrix}$$

用明文比特 $x_i$ 作系数，把前 $n$ 行加起来再加上最后一行，得到

$$(x_1, \dots, x_n,\ \textstyle\sum x_i b_i - C) = (x_1, \dots, x_n,\ 0).$$

这是一个各分量只有 0 和 1 的极短向量，长度至多 $\sqrt{n}$；而格中其他向量通常长得多。当背包"密度"较低时，LLL 能直接找到它，比特串就是明文。

总结