3. 格密码数学基础最小集

ML-DSA 的数学基础看起来庞杂，但落到签名工程，真正每天要打交道的只有五件工具：模 q 多项式环、NTT 变换、拒绝采样、中心二项分布、无穷范数与压缩舍入。本节不追求数学完备，只回答一个问题：这五件工具各自解决签名流程中的哪个具体问题，以及实现时哪些参数和边界必须盯住。

一、模 q 多项式环：签名运算的“容器”

ML-DSA 的所有向量、矩阵、多项式都生活在环 Rq = Zq[X]/(Xn+1) 中。以 ML-DSA-65 为例，n = 256，q = 8380417（一个 23 位素数，且 q ≡ 1 mod 512）。这意味着：

  • 每个多项式是 256 个系数，系数取值在 [0, q-1]；
  • 乘法不是普通多项式乘法，而是“先乘再模 X256+1”，即 X256 = -1，高次项折回时带负号；
  • q ≡ 1 mod 512 保证存在 512 次单位根，NTT 才能把 256 点多项式乘法降到 O(n log n)。

工程上要牢记：系数是模 q 的整数，不是浮点数。所有加减乘都必须做模约减，且约减结果要落在规范区间。签名验证失败最常见的低级原因，就是某处漏了模约减或用了错误的代表元。

二、NTT 变换：把多项式乘法变成点乘

直接做 256 次多项式乘法需要约 65536 次系数乘加，而 NTT 把它变成“变换—点乘—逆变换”三步。ML-DSA 使用负循环 NTT，把 X256+1 分解为 128 个二次不可约因式，因此 NTT 输出是 128 个二次多项式，而不是 256 个独立点值。这一点与 Kyber 的 NTT 结构不同，实现时不能直接套用 Kyber 代码。

关键参数：ζ 是 512 次本原单位根，ζ256 = -1。NTT 中每层蝶形运算都要乘对应的 ζ 幂次，最后逆变换要乘 n-1 mod q。工程上通常预计算 ζ 的幂表，避免运行时反复求幂。

实现提示：NTT 的输入系数应先做“中心化”处理，即把 [0, q-1] 映射到 [-q/2, q/2]，这样蝶形运算中的中间值不会溢出 32 位有符号整数。ML-DSA 参考实现中大量使用 int32_t 做 NTT，正是这个原因。

三、拒绝采样：把均匀随机变成“形状正确”的随机

签名中需要生成系数服从特定分布的多项式，但底层只有均匀随机字节。拒绝采样的做法是：从均匀随机比特流中取候选值，若落在目标分布允许的范围内就接受，否则丢弃并重新取。ML-DSA 中至少有两处用到拒绝采样：

  1. 采样 Ã 矩阵：用 SHAKE128 扩展种子，得到均匀系数，但要求系数落在 [0, q-1]，超出则拒绝；
  2. 采样 y 和 c：y 的系数服从中心二项分布，c 的系数是 {-1, 0, 1} 上的挑战多项式，都需要按分布拒绝。

拒绝采样的代价是“不确定的循环次数”。工程上必须保证：随机源可重复、拒绝逻辑无分支泄漏、循环有上界保护。ML-DSA 规范中给出了明确的采样算法和拒绝条件，实现时应逐条对照，不要自行简化。

四、中心二项分布：让签名噪声“够小又够随机”

ML-DSA 中 y、s1、s2 等秘密向量的系数服从中心二项分布 Bη，η = 2 或 4。采样方法是：取 2η 个均匀比特，分成两组各 η 个，分别数 1 的个数，再相减。结果落在 [-η, η]，概率质量函数为二项分布。

为什么不用高斯分布？因为中心二项分布只需均匀比特就能精确采样，不需要查表或浮点运算，天然适合常数时间实现。η 越大，噪声越大，安全性越高，但签名尺寸和拒绝概率也越大。ML-DSA-44 用 η = 2，ML-DSA-65/87 用 η = 4，这是安全性与效率的折中。

五、无穷范数与压缩舍入：签名“合格线”的判定工具

签名生成后，必须检查 y 和 c·s1 等中间量的系数是否“太大”。ML-DSA 用无穷范数 ||·||∞ 衡量：一个多项式的无穷范数是其所有系数绝对值的最大值。若 ||z||∞ ≥ γ1 - β，则拒绝并重新采样。γ1 是 y 的系数上界，β 是 c·s1 的范数上界。

压缩舍入则用于签名和验证的“对齐”：把系数按 2d 或 γ2 的倍数取整，只保留高位。这样签名只需传输高位，验证时再恢复近似值。ML-DSA 中 Power2Round、Decompose、HighBits、LowBits 四个函数就是干这个的。它们的边界条件非常容易写错，建议直接用规范中的伪代码逐行翻译。

ML-DSA 签名工程五件数学工具 · 数据流与判定关系 模 q 多项式环 R_q = Z_q[X]/(X²⁵⁶+1) n=256, q=8380417 NTT 变换 多项式乘法 → 点乘 128 个二次因式 拒绝采样 均匀比特 → 目标分布 Ã 矩阵 / y / c 系数向量 点乘结果 中心二项分布 B_η, η=2 或 4 2η 个均匀比特相减 采样 y / s₁ / s₂ 的系数分布 无穷范数 ‖·‖∞ max |系数| 判定 ‖z‖∞ < γ₁-β 生成 z = y + c·s₁ 压缩舍入 Power2Round / Decompose HighBits / LowBits 通过判定后 ‖z‖∞ 超界 → 拒绝，重新采样 y 签名 σ = (c, z, h) z 压缩后传输，验证端恢复近似值 高位输出 关键参数（ML-DSA-65） n=256, q=8380417, η=4 γ₁=2¹⁹, γ₂=(q-1)/32, β=196 图例 数据流 拒绝回路

六、五件工具如何串成一条签名链

把上面五件工具按签名流程串起来，就是一条清晰的数据流：

  1. 在环 Rq 中定义 Ã、s1、s2；
  2. 用拒绝采样从种子扩展出 Ã 和 y；
  3. 用中心二项分布采样 s1、s2；
  4. 用 NTT 加速 ÷y 和 ÷s1 的乘法；
  5. 计算 w = ÷y，c = H(w, μ)，z = y + c·s1；
  6. 用无穷范数检查 ‖z‖∞ 是否小于 γ1 - β，不满足则回到第 2 步；
  7. 用压缩舍入把 z 和 w 的高位提取出来，形成签名 (c, z, h)。

验证端则反向操作：用 c 和 z 重建 w'，再用压缩舍入的 HighBits 比较是否一致。整个过程中，NTT 负责速度，拒绝采样和中心二项分布负责“形状”，无穷范数和压缩舍入负责“合格线”。

常见误区：把 NTT 当成“可选的优化”。在 ML-DSA 中，NTT 是规范的一部分，签名格式和验证逻辑都依赖 NTT 的负循环结构。如果实现时改用普通多项式乘法，虽然数学上等价，但无法与标准测试向量对齐，也无法通过互操作性测试。

七、最小参数表（以 ML-DSA-65 为例）

工具关键参数工程关注点
模 q 多项式环n=256, q=8380417模约减、中心化、X²⁵⁶=-1 折回
NTTζ 为 512 次本原单位根预计算幂表、int32 中间值、逆变换乘 n⁻¹
拒绝采样SHAKE128 扩展循环上界、常数时间、可重复随机源
中心二项分布η=42η 比特分组、popcount 相减
无穷范数γ₁=2¹⁹, β=196判定条件 ‖z‖∞ < γ₁-β
压缩舍入γ₂=(q-1)/32, d=13Power2Round、Decompose 边界

这张表就是签名工程中需要反复核对的“最小集”。把这五件工具的输入输出、边界条件和参数含义弄清楚，后续实现 NTT 蝶形、采样循环、范数判定和压缩舍入时，就不会在数学层面迷失方向。

← 上一章 📖 返回目录 下一章 →