后量子密码学实战：NIST ML-KEM 与 ML-DSA 标准的算法原理与工程实现

概述

2024 年 8 月，美国国家标准与技术研究院（NIST）正式发布了三项后量子密码学（Post-Quantum Cryptography, PQC）标准：ML-KEM（原 CRYSTALS-Kyber）、ML-DSA（原 CRYSTALS-Dilithium）以及 SLH-DSA（原 SPHINCS+）。这些标准的诞生标志着密码学正式进入"后量子时代"——我们现有的 RSA、ECC 公钥体系在量子计算机面前将不堪一击，而 NIST 标准化的抗量子算法将成为下一代安全基础设施的基石。

本文将从数学基础、算法结构、性能特征到工程实现，全面剖析 ML-KEM（密钥封装机制）和 ML-DSA（数字签名）这两项核心标准，帮助工程师理解如何在实际系统中部署后量子密码学。

一、量子威胁：为什么现在就要准备？

1.1 Shor 算法的致命打击

1994 年，Peter Shor 证明了一个令整个信息安全界震惊的结论：量子计算机可以在多项式时间内分解大整数和求解离散对数问题。这意味着 RSA、ECC（椭圆曲线密码）、Diffie-Hellman、DSA 等当今互联网安全的基石，在面对足够大规模的容错量子计算机时将完全失效。

具体来说，破解 2048 位 RSA 大约需要 2000 万个量子比特（按表面码纠错计算），而当前 IBM Condor 处理器仅有 1121 量子比特。但考虑到量子硬件的指数级增长速度（量子比特数大约每 2 年翻一倍），业界普遍预计 2030-2040 年间可能出现威胁现有公钥体系的量子计算机。

1.2 "先收集后解密"攻击

密码迁移不可能一蹴而就。更可怕的是"先收集后解密"（Harvest Now, Decrypt Later）攻击模式：攻击者今天拦截并存储加密通信，等到量子计算机成熟后再解密。对于需要长期保密的数据（政府机密、医疗记录、金融数据），量子威胁已经是一个现实问题。

1.3 NIST 标准化进程

NIST 的后量子密码标准化项目始于 2016 年，经过三轮评选，从最初的 69 个候选方案中筛选出了最终标准：

标准	原名	类型	基于的数学问题
ML-KEM	CRYSTALS-Kyber	KEM（密钥封装）	模格上的 MLWE 问题
ML-DSA	CRYSTALS-Dilithium	数字签名	模格上的 MLWE + MSIS 问题
SLH-DSA	SPHINCS+	数字签名	哈希函数安全性

本文重点讲解 ML-KEM 和 ML-DSA，因为它们均基于格密码（Lattice-based Cryptography），是目前综合性能最优的后量子方案。

二、格密码的数学基础

2.1 什么是格？

在 n 维实数空间中，格（Lattice）是一组线性无关向量的整数线性组合：

L = {a₁b₁ + a₂b₂ + ... + aₙbₙ | aᵢ ∈ ℤ}

其中 b₁, ..., bₙ 是格的一组基向量。同一个格有无限多组不同的基，好的基（向量短且近似正交）与差的基（向量长且高度倾斜）在计算难度上有着天壤之别。

2.2 格上的困难问题

格密码的安全性建立在以下两个核心困难问题上：

最短向量问题（Shortest Vector Problem, SVP）：给定一组格基，找到格中最短的非零向量。在最坏情况下，SVP 在适当参数下被认为是 NP-hard 的。

容错学习问题（Learning With Errors, LWE）：给定一组形如 (aᵢ, aᵢ·s + eᵢ) 的样本，其中 aᵢ 随机均匀选取，s 是秘密向量，eᵢ 是小误差，恢复秘密向量 s 是计算不可行的。

2.3 从 LWE 到 Ring-LWE 到 Module-LWE

原始 LWE 方案中，密钥和密文都是 n×n 矩阵，计算量和存储开销巨大。后续发展出两个重要变体：

Ring-LWE（RLWE）：将矩阵运算放到多项式环 R = ℤ[x]/(xⁿ + 1) 上进行，利用 Number Theoretic Transform（NTT）将乘法复杂度从 O(n²) 降到 O(n log n)。Kyber（ML-KEM）的核心就是基于 RLWE。

Module-LWE（MLWE）：介于 LWE 和 Ring-LWE 之间，使用 Rᵏ 上的模（k 个多项式环的直和）。相比 RLWE，MLWE 在安全性和灵活性之间取得更好平衡：模块化结构允许通过调整安全级别参数（k=2,3,4）来缩放安全强度，同时保留大部分 RLWE 的计算效率。

2.4 模数选择与 NTT 友好性

ML-KEM 和 ML-DSA 都选用 q = 8380417（即 2²³ - 2¹³ + 1）作为模数。这是一个 NTT 友好的素数，满足 q ≡ 1 (mod 2n)，允许在 n 次单位根存在的条件下执行快速数论变换。

具体来说，对于 n=256，选取的本原根 ζ 满足 ζ²⁵⁶ ≡ -1 (mod q)，从而支持 256 点 NTT 和逆 NTT，使多项式乘法达到 O(n log n) 的复杂度。

三、ML-KEM 深度解析

3.1 算法概览

ML-KEM（Module-Lattice-Based Key Encapsulation Mechanism）是一个密钥封装机制（KEM），用于在不安全信道上安全地共享对称密钥。它与 ECDH 的角色类似，但具备抗量子能力。

ML-KEM 提供三个安全等级：

参数集	安全等级	n	k	η	du	dv	等效对称安全
ML-KEM-512	1（≈AES-128）	256	2	3	10	4	128-bit
ML-KEM-768	3（≈AES-192）	256	3	2	10	4	192-bit
ML-KEM-1024	5（≈AES-256）	256	4	2	11	5	256-bit

3.2 密钥生成（KeyGen）

1. 随机生成种子 d（32 字节）和 z（32 字节）
2. 使用随机预言机 G(d) 扩展出 (ρ, σ) = G(d)，其中 ρ 用于生成矩阵 Â，σ 用于采样秘密
3. 通过 NTT 域上的均匀采样生成公共矩阵 A（k×k 个多项式，每个在 NTT 域表示）
4. 从中心二项分布 Bη 中采样秘密向量 s 和误差向量 e（各 k 个多项式）
5. 计算 t = ·s + e（矩阵-向量乘法，在 NTT 域）
6. 公钥 pk = (t, ρ)，私钥 sk = (s, z, H(pk), pk)

关键设计点：矩阵 A 并非直接存储（那样太大），而是通过种子 ρ 在 NTT 域即时生成。这种"伪随机矩阵"技术大幅压缩了公钥尺寸。

3.3 封装（Encapsulation）

1. 随机生成消息 m（32 字节）
2. 计算 (K̄, r) = G(H(pk) || m) —— 绑定消息到公钥哈希
3. 从 Bη 采样随机向量 r' 和误差 (e₁, e₂)
4. 计算 u = Âᵀ·r' + e₁，v = tᵀ·r' + e₂ + Decode(m)
5. 计算共享密钥 K = KDF(K̄ || H(c))
6. 密文 c = (u, v)，共享密钥 K

3.4 解封装（Decapsulation）

1. 从密文中提取 u, v
2. 计算 m' = v - sᵀ·u（去掉掩码后恢复消息）
3. 重新封装验证：计算 (K̄', r') = G(H(pk) || m')，验证 u, v 是否一致
4. 验证通过则返回 K = KDF(K̄' || H(c))
5. 验证失败则返回 K = KDF(z || H(c)) —— 隐式拒绝，防止时序攻击

隐式拒绝机制（Implicit Rejection）是 ML-KEM 的重要安全设计：解封装失败时不返回错误，而是用私钥中的种子 z 派生一个伪随机密钥。这防止了 FO（Fujisaki-Okamoto）变换中的密文分布偏差被攻击者利用，同时避免了时序侧信道泄露。

3.5 FO 变换：从 CPA 到 CCA2 安全

ML-KEM 的安全性证明基于 FO 变换，将一个 IND-CPA 安全的公钥加密方案提升为 IND-CCA2 安全的 KEM。核心思路是：

• 加密时，不直接加密明文，而是加密一个随机值（明文作为确定性函数的输入）
• 解密时，恢复随机值后重新加密验证——如果密文被篡改，重新加密结果必然不同
• FO 变换的量子安全版本（QROM 下的 Uₘ† 变换）保证了在量子随机预言机模型下的安全性

3.6 性能实测数据

在 Intel Core i7-12700（Cortex-A78 级别）上的典型性能：

操作	ML-KEM-512	ML-KEM-768	ML-KEM-1024
KeyGen	~85k cycles	~125k cycles	~175k cycles
Encaps	~95k cycles	~140k cycles	~190k cycles
Decaps	~100k cycles	~145k cycles	~200k cycles
公钥大小	800 B	1,184 B	1,568 B
密文大小	768 B	1,088 B	1,568 B

与 ECDH P-256 对比：ML-KEM-768 的公钥是 ECDH P-256 的约 36 倍，但计算速度在同一量级内。对于 TLS 等协议来说，这个开销是可接受的——尤其是对比量子威胁的严重性。

四、ML-DSA 深度解析

4.1 算法概览

ML-DSA（Module-Lattice-Based Digital Signature Algorithm）是 NIST 标准化的后量子数字签名方案。与 ML-KIM 不同，它基于 Fiat-Shamir with Aborts 范式——一种将身份认证协议转化为签名的通用方法。

ML-DSA 参数集：

参数集	安全等级	k	l	η	τ	γ₁	γ₂
ML-DSA-44	2	4	4	2	39	2¹⁷	(q-1)/88
ML-DSA-65	3	6	5	4	49	2¹⁹	(q-1)/32
ML-DSA-87	5	8	7	2	60	2¹⁹	(q-1)/32

4.2 Fiat-Shamir with Aborts 范式

传统 Fiat-Shamir 签名方案可能产生非零知识泄露的秘密信息。Dilithium 引入"拒绝采样"（Rejection Sampling）解决：

1. 密钥生成：生成短秘密向量 s₁, s₂，计算公钥 t = A·s₁ + s₂

2. 签名：随机选取掩码 y，计算 w = A·y；从 H(w || msg) 派生挑战 c；计算 z = y + c·s₁

3. 拒绝条件：如果 z 的范数超过阈值（防止泄露 s₁），则丢弃重试

4. 验证：检查 z 的范数是否在界内，且 c == H(A·z - c·t || msg)

关键在于 z = y + c·s₁。由于 y 是随机选取的，z 的分布与 s₁ 独立（在拒绝条件下），因此签名不会泄露秘密密钥的信息。

4.3 工程优化

ML-DSA 在工程实现上有几处精妙优化：

种子扩展：与 ML-KEM 类似，通过种子即时生成矩阵 A，而不是存储完整矩阵。

NTT 变换：所有多项式运算在 NTT 域进行，将 O(n²) 的乘法降为 O(n)。

压缩函数：签名中包含多项式的高位部分（丢弃低位以减小尺寸），验证时通过缩放重建。γ₁ 和 γ₂ 参数控制压缩率与安全性的平衡。

Hint 机制：验证时需要知道哪些系数在压缩过程中发生了溢出。签名包含一个"hint"（ρ₀），指示溢出位置，使验证者能正确重建 w。

4.4 性能与尺寸

操作	ML-DSA-44	ML-DSA-65	ML-DSA-87
签名大小	2,420 B	3,293 B	4,595 B
公钥大小	1,312 B	1,952 B	2,592 B
Sign 速度	~200k cycles	~300k cycles	~450k cycles
Verify 速度	~65k cycles	~85k cycles	~110k cycles

与 ECDSA P-256 对比，ML-DSA 签名大小大了约 30 倍，但验证速度远超 RSA-2048。在 TLS 证书链整体开销中，这通常是可以接受的（证书总大小仍在 KB 级别）。

五、工程实现要点

5.1 恒定时间实现

后量子密码学对侧信道攻击极其敏感。ML-KEM 和 ML-DSA 必须恒定时间实现，否则攻击者可以通过计时、功耗分析等方式恢复密钥。

核心原则：

• 所有分支必须基于恒定时间的比较函数（如逐字节比较后位运算合并）
• 采样使用恒定时间的 CDF 反转或 Knuth-Yao 算法
• NTT 运算中避免秘密依赖的内存访问模式

5.2 NTT 实现优化

NTT（数论变换）是后量子密码的性能关键。典型优化包括：

• Cooley-Tukey 蝶形运算：自顶向下分解，原地计算
• Gentleman-Sande 蝶形运算：自底向上合并，不同的访存模式适合不同场景
• 预计算旋转因子：将 ζ 的各次幂预计算并查表，避免重复模幂
• 延迟约减：在蝶形运算中积累多个值后一次性模约减，减少模运算次数
• AVX2/NEON 向量化：利用 SIMD 并行处理多个系数

5.3 内存安全

ML-KEM 和 ML-DSA 的私钥必须严格保护。工程中需注意：

• 私钥材料使用 mlock/mprotect 锁定，防止被交换到磁盘
• 使用后立即 memset_s/explicit_bzero 清零敏感数据
• 使用带内存保护的语言（如 Rust）实现核心密码学组件
• 考虑使用 TEE（可信执行环境）或 HSM（硬件安全模块）保护高价值密钥

5.4 混合模式部署

过渡期内，NIST 建议在 TLS 等协议中采用混合模式（Hybrid Mode），同时使用经典算法和后量子算法：

TLS 1.3 混合密钥交换:
共享密钥 = KDF(ECDH_共享密钥 || ML-KEM_共享密钥)

这样即使后量子算法存在未知漏洞，经典算法仍提供安全保障。反之亦然。目前 Chrome 116+ 已默认启用 X25519Kyber768 混合密钥交换。

六、实际部署案例

6.1 Google Chrome

Chrome 116 起，默认在 TLS 握手中启用 X25519Kyber768 混合方案（X25519 + ML-KEM-768）。这意味着每次 HTTPS 连接都在同时执行经典 ECDH 和后量子 KEM。

6.2 Apple iMessage

Apple 在 iOS 17.4 中引入了 PQ3 协议，使用 ML-KEM 保护 iMessage 通信。PQ3 的设计目标是达到"Level 3"安全级别——即使密钥泄露，也能通过持续密钥更新保护消息的前向安全和后向安全。

6.3 Cloudflare

Cloudflare 在其网关和内部基础设施中部署混合 TLS，并支持通过 API 为边缘证书申请后量子签名。Cloudflare 的工程师提出了"Ouroboros"方案，将后量子签名的开销分散到多次连接中。

6.4 中国商用密码标准

中国在后量子密码标准化方面也有积极布局：

• 国家密码管理局 2025 年发布了基于格的 SM9 后量子扩展方案研究稿
• 中国科研团队在 CRYSTALS 系列的优化上发表了多篇高水平论文
• 国内多个 CA 机构已开始测试后量子证书链

七、未来展望

7.1 Streamlined NIST Standards

NIST 于 2025 年启动了第四轮评估，关注基于编码的 KEM 方案（如 Classic McEliece、HQC），以 ML-KEM 之外的数学假设提供额外安全冗余。

7.2 FALCON 与 FN-DSA

FALCON 签名方案（基于 NTRU 格的短签名）在标准过程中遇到实现复杂性挑战，NIST 正在评估将其改进为 FN-DSA 标准。FALCON 的签名大小仅为 ~666 B，远小于 ML-DSA，对签名尺寸敏感的应用（如区块链）极具吸引力。

7.3 同态加密与 MPC 的结合

格密码不仅是后量子安全的基础，也是全同态加密（FHE）和安全多方计算（MPC）的核心工具。BFV、CKKS、TFHE 等 FHE 方案同样基于 RLWE/MLWE 问题，这意味着今天在 ML-KEM/ML-DSA 上的工程积累，将直接惠及未来隐私计算技术的实用化。

7.4 硬件加速

后量子密码学催生了新的硬件加速需求：

• Intel 在 Sapphire Rapids 后开始提供 AVX-512 优化的 PQC 指令扩展
• ARM 在 v9.4 中添加了 NTT 加速指令
• 多家 FPGA 厂商提供了 ML-KEM/ML-DSA 的硬件 IP 核
• ASIC 方案可满足 10G+ 线速的后量子 TLS 需求

总结

后量子密码学不再是"未来的问题"。NIST 标准 ML-KEM 和 ML-DSA 的正式发布，标志着密码学进入了一个新时代。作为工程师，我们需要：

1. 了解基础：RLWE/MLWE 问题的数学本质和安全假设

2. 评估影响：识别系统中哪些组件需要迁移到后量子安全方案

3. 采用混合模式：在过渡期部署经典+后量子混合方案

4. 关注实现安全：恒定时间实现、内存保护和侧信道防护是部署 PQC 的关键

5. 跟踪生态：浏览器、操作系统、CA 和云服务商正在快速推进支持

量子计算机或许还需要十年才能真正威胁现有密码体系，但密码迁移本身就需要十年甚至更久。今天开始关注并实践后量子密码学，是在为下一代数字基础设施的安全奠基。

---

参考: NIST FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA); CRYSTALS 团队论文; IETF drafts for PQC in TLS/X.509