2. ML-DSA算法原理深入
ML-DSA（Module-Lattice-Based Digital Signature Algorithm）是NIST后量子密码标准化中用于数字签名的核心算法，其标准编号为FIPS 204。理解ML-DSA不能只停留在"它能签名"这一层面，而需要看清它建立在什么样的数学困难问题之上、密钥如何生成、签名如何构造、验证如何判定，以及它与早期Dilithium提交版本之间的关系。本节围绕这些内容展开，并在最后给出参数集选择的实践依据。
一、格密码基础：ML-DSA依赖的困难问题
ML-DSA的安全性建立在模格（module lattice）上的两个经典困难问题之上：MLWE（Module Learning With Errors，模容错学习）和MSIS（Module Short Integer Solution，模短整数解）。直观地说，MLWE问题是指：给定矩阵 A 和向量 t = A·s₁ + s₂，其中 s₁、s₂ 是系数很小的秘密向量，攻击者要从 (A, t) 中恢复 s₁、s₂ 是困难的；MSIS问题则要求在一个模格中寻找一个非零的短向量，同样被认为是计算困难的。
ML-DSA的密钥生成依赖MLWE，签名安全性依赖MSIS。这里的"模"指的是运算在多项式环 R_q = Z_q[X]/(X^n + 1) 上进行，q 为模数，n 为多项式次数。ML-DSA采用模块结构：把 k×l 个多项式组成矩阵，每个元素都是环 R_q 中的多项式，这样既保持了安全性又控制了密钥和签名的尺寸。与纯LWE相比，模块化结构让参数调节更灵活；与NTRU格相比，它避免了额外的结构假设。
二、密钥生成流程
密钥生成的核心是构造一对满足 A·s₁ + s₂ = t 的向量。具体步骤如下（以ML-DSA-65为例，n=256，q=8380417，k=6，l=5）：
- 生成种子：选取32字节随机种子 ξ，通过SHAKE-256扩展出 ρ、ρ′、K 三个值。
- 展开矩阵 A：用 ρ 作为种子，通过SHAKE-256的拒绝采样生成 k×l 个多项式，组成矩阵 A ∈ R_q^{k×l}。矩阵 A 是公开的，任何人都能重新计算。
- 采样秘密向量：用 ρ′ 采样 s₁ ∈ R_q^l 和 s₂ ∈ R_q^k，每个系数都取自一个很小的范围（如 [-4, 4]），保证它们是"短"向量。
- 计算公钥向量：计算 t = A·s₁ + s₂，再拆分为高位 t₁ 和低位 t₂（t = t₁·2^d + t₂），其中 t₁ 公开、t₂ 保密。
- 输出密钥：公钥 pk = (ρ, t₁)，私钥 sk = (ρ, K, t₀, s₁, s₂)，其中 t₀ 是 t 的低位部分，用于签名时重构完整 t。
这里的关键设计是：公钥只暴露 t 的高位，低位被截断，这进一步增加了攻击者从公钥恢复秘密的难度。私钥中保留 K 用于签名时的确定性随机化，保证同一消息在不同签名中不会泄露额外信息。
三、签名与验证流程
ML-DSA采用"Fiat-Shamir with Aborts"范式，签名过程是一个带拒绝采样的循环。签名者需要反复尝试，直到产生的签名满足范数约束为止。具体流程如下：
- 计算消息摘要：μ = H(tr ‖ M)，其中 tr 是公钥的哈希，M 是待签消息。
- 采样掩码向量：从种子 ρ′ 和随机数 κ 采样 y ∈ R_q^l，系数范围受限于 γ₁。
- 计算承诺：w = A·y，将 w 拆分为高位 w₁ 和低位 w₀。
- 计算挑战：c̃ = H(μ ‖ w₁)，将 c̃ 扩展为挑战多项式 c，其系数很小（取自 {-1,0,1} 或类似小集合）。
- 计算响应：z = y + c·s₁，并检查 z 的范数是否超过 γ₁ - β。若超过，则拒绝并回到第2步重新采样。
- 计算提示：h = MakeHint(-c·t₀, w - c·s₂ + c·t₀)，用于验证时恢复 w₁。若 h 的汉明重量超过 ω，同样拒绝重来。
- 输出签名：σ = (c̃, z, h)。
验证者拿到 (M, σ, pk) 后，先重算 μ 和 c，再计算 w′ = A·z - c·t₁·2^d，然后用 h 恢复 w₁′，最后检查 c̃ 是否等于 H(μ ‖ w₁′)，以及 z 和 h 的范数是否在允许范围内。全部通过则签名有效。
四、与Dilithium的关系
ML-DSA并非凭空出现，它直接脱胎于CRYSTALS-Dilithium。Dilithium是NIST后量子密码竞赛第三轮的入围方案，2022年被选为数字签名标准化的基础。FIPS 204在Dilithium 3.1版本的基础上做了少量调整：主要是将随机化签名的默认行为、域分隔符的编码方式以及部分哈希函数的调用细节规范化，使标准更易于实现和互操作。因此，在开发实践中，很多库（如liboqs、PQClean）中Dilithium的实现与ML-DSA高度相似，但不能直接混用——两者的签名格式和哈希输入编码存在差异，跨实现验证会失败。开发时应明确使用标注为"ML-DSA"或"FIPS 204"的接口，而不是旧版Dilithium接口。
五、参数集选择
FIPS 204定义了三个参数集，对应不同的安全强度和性能开销：
| 参数集 | NIST安全级别 | 公钥大小 | 签名大小 | 典型适用场景 |
|---|---|---|---|---|
| ML-DSA-44 | 2（约128位经典安全） | 1312 字节 | 2420 字节 | 资源受限设备、嵌入式、对带宽敏感的协议 |
| ML-DSA-65 | 3（约192位经典安全） | 1952 字节 | 3309 字节 | 通用场景默认选择，TLS、代码签名、文档签名 |
| ML-DSA-87 | 5（约256位经典安全） | 2592 字节 | 4627 字节 | 高价值长期签名、根CA、固件签名 |
选择时主要权衡三点：安全等级、签名与公钥尺寸、签名/验证的计算开销。ML-DSA-65在安全性和尺寸之间取得较好平衡，是多数应用的推荐起点；若系统需要与AES-128级别对齐且带宽紧张，可选ML-DSA-44；若签名需要长期有效（如十年以上）或用于信任锚，应选ML-DSA-87。需要注意的是，ML-DSA的签名尺寸远大于ECDSA（约64字节），在协议设计中必须提前预留报文空间，避免因签名膨胀导致分片或握手失败。