ML-DSA 数字签名算法深度解析：从 FIPS 204 到后量子签名的标准化之路

概述

ML-DSA（Module-Lattice-Based Digital Signature Algorithm，基于模块格的数字签名算法）是美国国家标准与技术研究院（NIST）于 2024 年 8 月 13 日发布的首个后量子数字签名标准，定义于 FIPS 204《Module-Lattice-Based Digital Signature Standard》¹。

ML-DSA 基于 CRYSTALS-Dilithium 算法（由里昂大学、拉德堡德大学等机构联合设计），其安全性依赖于模块格（Module Lattice）上的学习误差问题（Module Learning With Errors, MLWE）的困难性。与 RSA 和 ECDSA 不同，ML-DSA 被设计为能够抵抗拥有大规模量子计算机的攻击者。

标准化背景

NIST 后量子密码标准化历程

NIST 自 2016 年起启动后量子密码标准化进程：

FIPS 204 与原始 Dilithium 的区别

ML-DSA 基于 Dilithium Version 3.1²，但包含多项关键修改：

• 安全级别 5 的安全增强：将私钥随机种子（ρ'）和消息代表（μ）的长度从 384 位增加到 512 位，纠正在第三轮提交中发现的安全漏洞——SHAKE256 的 384 位输出在碰撞攻击下可能使 Category 5 参数只能达到 Category 4 安全水平³
• Hedged 签名机制：默认引入额外随机性（256 位 rnd 字符串），在随机数生成器故障时仍保持安全性
• 域名分离（Domain Separation）：在外部函数（签名和验签）与内部函数之间引入域名分离，增强协议组合安全性
• Hint 检查修复：修复了在初始公开草案中遗漏的 hint 解包输入验证，确保强存在不可伪造性

算法数学基础

模块格与困难问题

ML-DSA 的安全性建立在以下困难问题上：

多项式环定义：

$$R_q = \mathbb{Z}_q[X]/(X^{256} + 1)$$ $$T_q = \mathbb{Z}_q^{256} \text{（NTT 表示）}$$

其中 $q = 8380417$ 是模数，多项式次数 $n = 256$。NTT（数论变换）将 $R_q$ 中的多项式乘法转化为 $T_q$ 中对应分量（逐系数）的乘法，大幅提升计算效率。

MLWE 问题：

给定随机矩阵 $\mathbf{A} \in R_q^{k \times l}$，短秘密向量 $\mathbf{s}_1 \in R_q^l$ 和短误差向量 $\mathbf{s}_2 \in R_q^k$，计算： $$\mathbf{t} = \mathbf{A}\mathbf{s}_1 + \mathbf{s}_2$$

敌手在仅知道 $(\mathbf{A}, \mathbf{t})$ 的情况下恢复 $\mathbf{s}_1, \mathbf{s}_2$ 是计算上不可行的。

Fiat-Shamir with Aborts 范式

ML-DSA 采用带有拒绝采样的 Fiat-Shamir 范式构建签名方案，核心思想是：

• 签名者承诺一个掩码向量 $\mathbf{y}$，计算承诺 $\mathbf{w} = \mathbf{A}\mathbf{y}$
• 通过哈希函数从承诺中提取挑战值 $c$
• 签名者计算响应 $\mathbf{z} = \mathbf{y} + c\mathbf{s}_1$
• 拒绝采样：若 $\mathbf{z}$ 的范数过大（可能泄露私钥信息），则重新选择 $\mathbf{y}$ 并重复步骤 1-3
• 输出签名 $(\mathbf{z}, c, \mathbf{h})$，其中 $\mathbf{h}$ 是帮助验签方恢复高位的 hint 向量

参数体系

安全参数族

FIPS 204 定义了三组参数集，对应三个 NIST 安全强度等级：

密钥与签名尺寸

算法结构

密钥生成

ML-DSA.KeyGen():
  1. 生成随机种子 ξ ∈ {0,1}^256
  2. 扩展种子：生成 (ρ, ρ', K) = G(ξ)，其中 G 是 SHAKE256
  3. 生成矩阵 A = ExpandA(ρ) ∈ R_q^{k×l}
  4. 生成秘密向量 s₁ = ExpandS(ρ') ∈ R_q^l，系数范围 [-η, η]
  5. 生成秘密向量 s₂ = ExpandS(ρ') ∈ R_q^k，系数范围 [-η, η]
  6. 计算 t = A·s₁ + s₂
  7. 对 t 进行 Power2Round 分解：t = t₁·2^d + t₀，其中 t₁ 为高位，t₀ 为低位
  8. 公钥 pk = (ρ, t₁)
  9. 私钥 sk = (ρ, K, tr, s₁, s₂, t₀)

其中：

• ρ 是矩阵 A 的种子
• ρ' 是秘密向量的种子（512 位）
• K 是 hedging 随机种子
• tr = H(pk) 是公钥的哈希值（512 位）
• d = 13 是分解参数

签名

ML-DSA.Sign(sk, M, ctx):
  1. 解析 sk = (ρ, K, tr, s₁, s₂, t₀)
  2. 计算 μ = H(tr || M || ctx)  （消息代表，512 位）
  3. 生成随机数 rnd（默认 256 位随机，确定性模式下为 0）
  4. 计算 ρ' = H(K || rnd || μ)  （实际使用的私钥随机种子）
  5. 进入拒绝采样循环：
     a. 生成掩码向量 y = ExpandMask(ρ', κ)，系数范围 [-γ₁, γ₁]
     b. 计算 w = A·y
     c. 提取 w 的高位 w₁ = HighBits(w)
     d. 计算挑战 c̃ = H(μ || w₁)
     e. 从 c̃ 中采样挑战 c = SampleInBall(c̃)，恰好有 τ 个系数为 ±1
     f. 计算响应 z = y + c·s₁
     g. 检查拒绝条件：若 ‖z‖∞ ≥ γ₁ - β，则拒绝并重新循环
     h. 计算 r₀ = LowBits(w - c·s₂)
     i. 检查拒绝条件：若 ‖r₀‖∞ ≥ γ₂ - β，则拒绝并重新循环
  6. 计算 hint h = MakeHint(z, w - c·s₂ + c·t₀)
  7. 输出签名 σ = (z, h, c̃)

拒绝采样是 ML-DSA 签名的核心机制。期望的循环次数为：

• ML-DSA-44：约 4.25 次
• ML-DSA-65：约 5.1 次
• ML-DSA-87：约 3.85 次

验签

ML-DSA.Verify(pk, M, σ, ctx):
  1. 解析 pk = (ρ, t₁)，σ = (z, h, c̃)
  2. 检查 ‖z‖∞ < γ₁ - β，否则拒绝
  3. 检查 h 中 1 的个数 ≤ ω，否则拒绝
  4. 计算 μ = H(H(pk) || M || ctx)
  5. 从 c̃ 中采样挑战 c = SampleInBall(c̃)
  6. 计算 w₁' = UseHint(h, A·z - c·t₁·2^d)
  7. 验证 c̃ == H(μ || w₁')，若相等则接受，否则拒绝

验签不需要知道私钥，仅使用公钥和签名即可验证。

核心算法组件

NTT（数论变换）

NTT 是 ML-DSA 高效实现的关键。它将 $R_q$ 中的多项式乘法转化为 $T_q$ 中对应分量的逐系数乘法：

$$\text{NTT}(w) = (w(\zeta^0), w(\zeta^1), \ldots, w(\zeta^{255})) \in T_q$$

其中 $\zeta = 1753$ 是模 $q$ 下的 512 次单位根。

NTT 将多项式乘法的复杂度从 $O(n^2)$ 降低到 $O(n \log n)$，使 ML-DSA 在实际部署中可行。

拒绝采样

ML-DSA 使用三种拒绝采样算法：

Hint 机制

Hint 是 ML-DSA 签名压缩的关键技术。签名者计算： $$h = \text{MakeHint}(z, w - c \cdot s_2 + c \cdot t_0)$$

验签者使用 hint 恢复 $w_1$ 的高位： $$w_1' = \text{UseHint}(h, A \cdot z - c \cdot t_1 \cdot 2^d)$$

Hint 允许验签方在不传输完整 $w_1$ 的情况下恢复挑战值，显著减小签名尺寸。

安全性分析

安全属性

ML-DSA 满足以下安全属性：

• 强存在不可伪造性（SUF-CMA）：敌手无法伪造对任何消息的签名，即使该消息已被签名过
• 抗量子计算攻击：基于 MLWE 问题的困难性，目前没有已知的量子算法能在多项式时间内破解
• 前向安全：即使私钥泄露，之前的签名仍然有效（这是数字签名的固有属性）

已知攻击与安全性估计

实现安全注意事项

• 恒定时间实现：所有涉及私钥的操作必须在恒定时间内完成，防止时间侧信道攻击
• 随机数质量：必须使用 NIST SP 800-90A 批准的随机数生成器
• 私钥保护：私钥必须安全存储，防止物理和逻辑泄露
• Hint 解包验证：必须验证 hint 输入的格式正确性，防止强存在不可伪造性被破坏

与其他签名算法对比

性能特征

适用场景

• ML-DSA-44：适用于需要中等安全级别且对签名尺寸有一定容忍度的场景
• ML-DSA-65：NIST 推荐的主流安全级别，平衡了安全性和性能
• ML-DSA-87：适用于需要最高安全级别的场景，但签名尺寸较大

标准化与合规

FIPS 204 合规要求

根据 FIPS 204 第 6 节，美国联邦政府部门和机构在设计公钥签名系统时，必须使用以下标准之一：

• FIPS 204（ML-DSA）
• FIPS 205（SLH-DSA）
• FIPS 186-5（传统签名）
• NIST SP 800-208（基于哈希的签名）

验证计划

NIST 的密码模块验证计划（CMVP）将对 ML-DSA 实现进行合规验证：

• 验证信息：https://csrc.nist.gov/projects/cmvp
• 示例值：https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values

总结

ML-DSA 代表了数字签名技术的重大进步。作为首个标准化的后量子签名算法，它通过模块格上的困难问题提供了可证明的量子安全性。尽管其密钥和签名尺寸大于经典算法，但通过 NTT 等高效算法，ML-DSA 在实际部署中已经可行。

随着量子计算技术的快速发展，ML-DSA 及其替代方案（SLH-DSA、FN-DSA）将成为未来数字签名基础设施的核心组件。企业和组织应尽早开始规划从经典签名向后量子签名的迁移。

相关实践

• 后量子 TLS 混合密钥交换实战：https://gm.okpki.com/blog/post-quantum-tls-hybrid-key-exchange
• 后量子密码学知识库总览：https://gm.okpki.com/wiki/post-quantum-cryptography-overview
• FIPS 203 ML-KEM 标准深度解读：https://gm.okpki.com/wiki/fips-203-ml-kem-kyber-standard

参考来源

• NIST FIPS 204: Module-Lattice-Based Digital Signature Standard — ML-DSA 官方规范
• CRYSTALS-Dilithium Algorithm Specifications (Version 3.1) — Dilithium 算法规范
• NIST Post-Quantum Cryptography Standardization — NIST 后量子密码标准化主页
• NIST Releases First 3 Finalized Post-Quantum Encryption Standards — NIST 官方新闻稿
• IETF: Security Considerations for ML-DSA — IETF ML-DSA 安全考虑草案
• EUROCRYPT 2009: Fiat-Shamir with Aborts — ML-DSA 理论基础
• NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes — 基于哈希的签名方案参考