目录
简介
ML-KEM（Module-Lattice-Based Key-Encapsulation Mechanism）是由美国国家标准与技术研究院（NIST）在 2024 年发布的 FIPS 203 标准定义的后量子密钥封装机制。
什么是 KEM？
KEM（密钥封装机制） 是一种密码学原语，允许两方通过公开信道建立共享密钥。与传统的密钥交换算法（如 Diffie-Hellman）不同，KEM 是非对称的：
- 一方：生成公私钥对，将公钥发布
- 另一方：用公钥生成密文和共享密钥，发送密文
- 第一方：用私钥从密文恢复共享密钥
最终双方得到相同的共享密钥，可用于后续的对称加密。
为什么需要 ML-KEM？
经典密码学的问题：
- ECDSA（椭圆曲线数字签名算法）基于离散对数问题
- RSA 基于因子分解问题
- 这两个问题都被 Shor 算法（量子算法）破解
量子计算威胁：
- 理论上，量子计算机可以快速计算离散对数
- 即使现在加密的数据也会被未来的量子计算机解密
- 这被称为"收集现在，解密未来"攻击
ML-KEM 的优势：
- 基于格的 学习误差（LWE） 问题
- 即使对量子计算机也很困难
- 被认为是真正的后量子安全（Post-Quantum Safe）
核心概念
1. 格论基础
格（Lattice） 是高维空间中的离散点的规则排列。在密码学中，我们使用多项式环上的格。
多项式环: R_q = Z_q[x]/(x^256 + 1)
- Z_q: 模 q 的整数（q = 3329）
- x^256 + 1: 多项式约束条件
- 每个元素是一个 256 次多项式，系数在 [0, 3328]
2. 学习误差（LWE）问题
LWE 问题的定义：
给定：
- 矩阵 A（随机生成）
- 向量 t = A·s + e（mod q）
- s：秘密向量
- e：小噪声向量
问题：从 (A, t) 恢复 s
难度：
- 没有已知的多项式时间算法可以求解
- 最快的已知算法（BKW）需要 2^0.292n 次操作
- 对于 n=768（ML-KEM-768），这大约是 2^224 次操作——无法实现
3. ML-KEM 的三个参数集
FIPS 203 定义了三个参数集，安全性和性能依次递减：
| 参数集 | 安全等级 | 公钥大小 | 私钥大小 | 密文大小 | 密钥大小 |
|---|---|---|---|---|---|
| ML-KEM-512 | 128 bits | 800 字节 | 1632 字节 | 768 字节 | 32 字节 |
| ML-KEM-768 | 192 bits | 1184 字节 | 2400 字节 | 1088 字节 | 32 字节 |
| ML-KEM-1024 | 256 bits | 1568 字节 | 3168 字节 | 1568 字节 | 32 字节 |
数学原理
ML-KEM-768 的详细流程
参数说明：
- 维度：3（矩阵大小为 3×3）
- 多项式阶：256（每个多项式有 256 个系数）
- 模数：q = 3329
- 展开后维数：3 × 256 = 768
第一步：密钥生成（KeyGen）
输入：随机种子 z (256 比特)
输出：公钥 ek (1184 字节) 和 私钥 dk (2400 字节)
步骤：
1. 从 z 展开种子
ρ || σ := G(z) [G 是 SHA3-512]
2. 生成公开矩阵 A (3×3 的多项式矩阵)
A := XOF(ρ, i, j) [XOF 是 SHAKE128]
3. 生成秘密向量 s (3 维，每个分量是 256 次多项式)
s_i ← CBD(η₁) [CBD 是中心二项分布，η₁=2]
||s||_∞ ≤ 2
4. 生成噪声向量 e (同样维度和分布)
e_i ← CBD(η₁)
5. NTT 变换（Number Theoretic Transform）
ŝ := NTT(s) [将 s 变换到 NTT 域]
ê := NTT(e)
6. 计算公钥
t̂ := ·ŝ + ê [矩阵乘法在 NTT 域中进行]
7. 序列化
公钥 ek = Encode_12(t̂) || ρ
私钥 dk = Encode_12(ŝ) || Encode_4(ê) || ek || H(ek)
关键点：
- 私钥中保存了 ŝ、ê 和公钥副本
- ê 很重要：解密时需要它用于隐式拒绝机制
- 所有计算在 NTT 域中进行（加速）
第二步：加密（Encapsulation）
输入：公钥 ek (1184 字节)
输出：密文 c (1088 字节) 和 共享密钥 K (32 字节)
步骤：
1. 从公钥恢复矩阵 A
从 ek 解析出 t̂ 和 ρ
重建 A := XOF(ρ, i, j)
2. 生成加密时的噪声向量
r ← CBD(η₁) [第一个噪声向量]
e₁ ← CBD(η₂) [第二个噪声向量，η₂=1]
e₂ ← CBD(η₂) [第三个噪声向量]
3. NTT 变换
r̂ := NTT(r)
4. 计算密文的第一部分（u）
u := NTT^{-1}(Â^T · r̂) + e₁
[Â^T 是矩阵 A 的转置]
[NTT^{-1} 变换回系数域]
5. 计算密文的第二部分（v）
v := NTT^{-1}(t̂^T · r̂) + e₂ + Decompress(m̂, 1)
[m̂ 是消息比特，Decompress 将其扩展到多项式高位]
6. 序列化密文
密文 c = Encode_4(u) || Encode_5(v)
7. 生成共享密钥
K := H(m̂) [H 是 SHA3-256]
关键概念：
- 内部消息 m̂ 不是用户数据，而是系统内部生成的 256 比特随机值
- 密文 c 是 (u, v) 对，共 1088 字节
- 共享密钥 K 来自消息的哈希
第三步：解密（Decapsulation）
输入：私钥 dk (2400 字节) 和 密文 c (1088 字节)
输出：共享密钥 K' (32 字节)
步骤：
1. 从密文解析
u := Decode_4(u_bytes)
v := Decode_5(v_bytes)
û := NTT(u)
2. 恢复消息向量 w
w := v - NTT^{-1}(ŝ^T · û)
[使用秘密向量 ŝ 和 秘密噪声 ê]
[这是解密的关键：只有有 ŝ 的人才能计算这个]
3. 从 w 提取消息比特
m̂' := Compress(w, 1)
[Compress 是量化操作：]
[ 如果 w 的系数接近 q/2，则比特为 1]
[ 如果接近 0，则比特为 0]
4. 一致性检查（隐式拒绝）
计算 u' = Encode_4(NTT^{-1}(Â^T · NTT(r_check)))
计算 v' = Encode_5(NTT^{-1}(t̂^T · NTT(r_check)) + ...)
IF (u_bytes == u'_bytes && v_bytes == v'_bytes):
K := H(m̂') [正常路径]
ELSE:
K := PRF(z, c) [拒绝路径：返回确定性随机密钥]
5. 输出
返回 K' (32 字节)
关键概念：
- 隐式拒绝（Implicit Rejection）：如果密文不有效（被篡改），不返回错误，而是返回一个确定性的"虚假"密钥
- 这防止了针对解密失败的定时攻击
- 正常情况下，K' 应该等于 K
密钥结构与数据流
密钥组成
公钥 ek (1184 字节)：
┌─────────────────────────────────────┐
│ t̂ 的 12 比特编码 (1152 字节) │
│ ρ 种子 (32 字节) │
└─────────────────────────────────────┘
私钥 dk (2400 字节)：
┌─────────────────────────────────────┐
│ ŝ 的 12 比特编码 (1152 字节) │
│ ê 的 4 比特编码 (384 字节) │
│ ek 公钥副本 (1184 字节) │
│ H(ek) 哈希 (32 字节) │
│ (其他元数据) │
└─────────────────────────────────────┘
完整通信流程
Alice 一方：
├─ KeyGen() → (公钥 ek, 私钥 dk)
└─ 发布公钥 ek，保留 dk
Bob 一方：
├─ 收到 ek
├─ Encaps(ek) → (密文 c, 共享密钥 K)
├─ 保留 K（可用于后续加密）
└─ 发送 c 给 Alice
Alice 一方（接收端）：
├─ 收到 c
├─ Decaps(dk, c) → 共享密钥 K'
└─ K' 应该等于 K
双向通信：
Alice ─ AES-GCM(K_AB, 数据) → Bob
Bob ─ AES-GCM(K_BA, 数据) → Alice
[K 需要派生成不同方向的密钥]
安全性分析
安全性来源
1. LWE 问题的困难性
维度分析：
ML-KEM-768 的实际维度：
展开后的维数 n = 3 × 256 = 768
搜索空间：
每个系数小值范围 [-2, 2]
768 个系数 → 5^768 ≈ 2^2356 种可能
已知最快算法的复杂度：
BKW 算法：2^(0.292n) = 2^(0.292×768) ≈ 2^224
对比：
宇宙中所有原子数 ≈ 2^80
2^224 次操作绝对无法实现
2. 噪声的作用
噪声不是"破坏"，而是安全的来源：
没有噪声的情况：
t = A·s （精确线性系统）
攻击者可以用高斯消元：s = A^{-1}·t
有噪声的情况：
t = A·s + e （噪声破坏了精确解）
即使知道 A 和 t，也无法直接解出 s
因为有 e 的存在，没有唯一解
这就是 LWE 问题的本质困难
3. 与 ECC 的对比
| 特性 | ECC（椭圆曲线） | ML-KEM（格论） |
|---|---|---|
| 困难问题 | 离散对数 | 学习误差（LWE） |
| 已知最快攻击 | Pollard's rho (2^128) | BKW (2^224) |
| 量子算法 | Shor's (2^n) | Regev (2^0.5n，仍指数级) |
| 参数大小 | 256 比特 | 768 比特 |
| 后量子安全 | ❌ 否 | ✅ 是 |
为什么 ML-KEM 安全：
- 768 维是一个"魔幻数字"
- 足够高使得所有算法都变成指数级
- 但不会太大导致不可用
隐式拒绝机制
传统的 KEM 如果密文无效，会返回错误。这可能导致定时攻击：
攻击者可能发送多个密文
观察解密时间的差异
推断 s 的某些信息
解决方案：隐式拒绝
- 密文无效时不返回错误
- 而是返回一个确定性的虚假密钥
- PRF(secret, invalid_ciphertext)
- 攻击者无法区分有效/无效密文
应用场景
1. TLS 1.3 握手
现状（TLS 1.3）：
使用 ECDHE (Elliptic Curve Diffie-Hellman)
建立临时共享密钥
升级方案（草案 RFC 9440）：
Step 1: Client 发送 ML-KEM 公钥
Step 2: Server 执行 Encaps() → 得到 (c, K)
Step 3: Server 发送密文 c
Step 4: Client 执行 Decaps(c) → 得到 K'
Step 5: 双方都有 K，用于导出会话密钥
优势：
✓ 量子安全的密钥交换
✓ 对既有通信的向后兼容
2. 混合方案（ECC + ML-KEM）
为了过渡安全，许多应用使用混合方案：
交换阶段：
Step 1: ECDHE 密钥交换 → K_ecc
Step 2: ML-KEM 密钥交换 → K_mlkem
Step 3: 合并密钥 K_final = KDF(K_ecc || K_mlkem)
安全性：
- 如果 ECDHE 被破解（短期威胁），K_mlkem 仍然安全
- 如果 ML-KEM 有问题，K_ecc 作为后备
- 两个都被破解概率极低
过渡策略：
现在：使用混合方案（两个都安全）
2030-2040：逐步停用 ECC
2040+：仅使用 ML-KEM
3. VPN 和安全通信
OpenVPN、WireGuard 等可以集成 ML-KEM：
- 初始握手用 ML-KEM（量子安全）
- 定期重新协商（前向安全）
- 数据加密用 AES-GCM（高速）
4. 数字签名的补充
注意：ML-KEM 是 KEM，不是签名算法。
要实现签名功能，需要其他方案：
FIPS 204 中定义：ML-DSA（Module-Lattice-Based DSA）
FIPS 205 中定义：SLH-DSA（Stateless Hash-Based DSA）
这些可以替代 ECDSA 用于数字签名
常见问题 FAQ
Q1: ML-KEM 能直接替代 ECDSA 吗？
A: 不能。它们做的事情完全不同：
ECDSA：数字签名算法
- 用私钥签署消息
- 任何人用公钥验证
- 证明"我拥有这个私钥"
ML-KEM：密钥封装机制
- 用公钥生成密文 + 密钥
- 用私钥从密文恢复密钥
- 建立共享密钥用于对称加密
如果需要替代签名，应该用 ML-DSA（FIPS 204）。
Q2: 为什么 ML-KEM 密文这么大（1088 字节）？
A: 这是格论系统的特性：
大小比较：
ECDH 密文：32 字节
ML-KEM 密文：1088 字节
比例：34 倍
原因：
1. 多项式表示：每个系数需要位空间
2. 噪声编码：需要精确表示噪声
3. 安全参数：更大的参数 = 更强的安全性
权衡：
✓ 增加了大小（网络开销 +34x）
✓ 但获得了量子安全性
✓ 对大多数应用是可接受的
Q3: 加密解密都用 ML-KEM 算法吗？
A: 不完全正确。完整的通信流程是：
第一阶段：建立密钥（用 ML-KEM）
├─ KeyGen：生成密钥对
├─ Encaps：生成密文 + 共享密钥 K
└─ Decaps：从密文恢复共享密钥 K'
第二阶段：加密数据（用对称算法）
└─ 用 K 派生的子密钥进行 AES-GCM 加密
ML-KEM 只在密钥交换阶段使用一次
后续数据加密用更快的对称加密算法
Q4: 如果 Bob 和 Alice 都有相同的密钥 K，Bob 不就能解密 Alice 发给 Alice 的消息了吗？
A: 是的！这是重要的问题，解决方案是密钥派生：
从共享密钥 K 派生多个子密钥：
K → KDF(K, "label") → {
K_client_write: Alice → Bob
K_server_write: Bob → Alice
K_client_iv: 初始化向量（Alice）
K_server_iv: 初始化向量（Bob）
}
结果：
✓ Alice 只用 K_client_write 加密发给 Bob 的消息
✓ Bob 只用 K_server_write 加密发给 Alice 的消息
✓ 两个方向的密钥不同，互相无法解密
这是 TLS 1.3 等标准中的标准做法。
Q5: 为什么解密失败时要返回虚假密钥而不是错误？
A: 防止定时攻击：
传统做法（容易受攻击）：
IF 密文有效:
return 真实密钥 [快速返回，50ms]
ELSE:
return 错误信息 [慢速返回，100ms]
攻击者观察：
"为什么有时快有时慢？"
通过定时可以推断 s 的某些位
逐渐累积信息，破解私钥
隐式拒绝做法：
IF 密文有效:
return H(m̂) [返回真实密钥]
ELSE:
return PRF(secret, c) [返回虚假但一致的密钥]
攻击者观察：
"总是在 50ms 返回"
无法通过定时推断任何信息
这是 FIPS 203 标准中强制要求的安全特性。
Q6: 噪声 e 在生成后还保留吗？为什么很重要？
A: 是的，必须保留在私钥中：
用途 1：公钥生成
t̂ = ·ŝ + ê
ê 是公钥计算的一部分
用途 2：隐式拒绝
如果密文检查失败
使用 ê 导出的种子生成虚假密钥
PRF(z_derived_from_e, c)
用途 3：安全性
ê 是 LWE 问题的核心
没有 ê，问题就变成容易求解的线性系统
所以 ê 必须作为私钥的一部分秘密保存
Q7: K 和 K' 是什么关系？
A: 它们应该相等，但从不同一方的角度产生：
术语澄清：
K = Bob 侧执行 Encaps() 产生的共享密钥
K' = Alice 侧执行 Decaps() 产生的共享密钥
正常情况：
K = K' [两方掌握相同的密钥]
异常情况（隐式拒绝）：
K ≠ K' [只在密文无效时发生]
K' = PRF(secret, invalid_c)
为什么两个名字：
- 从通信的角度，Bob 生成 K，Alice 恢复 K'
- 从安全的角度，它们应该相等
- 名字不同是为了强调它们是"复现"的，不是传输的
Q8: ML-KEM 基于什么假设它难以破解？
A: 基于两个关键假设：
假设 1：LWE 问题的困难性
已知：
- 矩阵 A（3×3 的多项式矩阵，随机）
- 向量 t = A·s + e（mod 3329）
困难：从 (A, t) 恢复 s
证据：
- 50+ 年的研究，无多项式算法
- 归约到格的其他已知难题
- 被加密社区广泛相信
假设 2：维度是"足够高"
ML-KEM-768：n = 768
对比：
- n=512：可能在 2030-2040 被破解
- n=768：被认为安全到 2050+
- n=1024：被认为安全到 2100+
不是"向量增加枚举空间"那么简单
而是"高维格的几何特性"使问题变难
Q9: 与 ECC 的离散对数相比，LWE 问题难吗？
A: 从不同角度看：
经典计算机：
离散对数（ECC）：
- 最快算法 Pollard's rho：O(2^128) 对 256 比特密钥
- 需要 2^128 步 ≈ 不可行
LWE（ML-KEM）：
- 最快算法 BKW：O(2^224) 对 768 维
- 需要 2^224 步 ≈ 更不可行！
量子计算机：
离散对数：
- Shor 算法：O(n^3)（多项式时间！）
- 256 比特 → 2^256^3 ≈ 高度多项式
- 完全被破解！
LWE：
- Regev 算法：O(2^0.5n)（仍然指数级！）
- 768 维 → 2^384
- 量子计算机也帮不了多少
结论：
✓ 对经典计算机：LWE 似乎更难（2^224 vs 2^128）
✗ 但更重要的是：LWE 对量子计算机也难
✓ ECC 对量子计算机完全无防，这才是真正的威胁
Q10: 为什么不直接用 ML-KEM 加密用户消息？
A: 三个关键原因：
原因 1：速度
ML-KEM Encaps：10-50 微秒
AES-GCM：1GB/s（硬件加速）
对比：1GB 数据
ML-KEM：50,000 秒（无法使用）
AES-GCM：1 秒
原因 2：大小膨胀
ML-KEM 密文：1088 字节
对 32 字节消息膨胀 34 倍
对比：1GB 数据
ML-KEM 输出：34GB（无法传输）
AES-GCM 输出：1GB（开销仅 50%）
原因 3：设计目的
ML-KEM 设计用于"偶尔进行的密钥交换"
- TCP 连接建立：1 次
- 持续 10 分钟
- 传输 100MB-1GB 数据
不是用于"每条消息都加密"
标准做法：
├─ 密钥交换：ML-KEM（偶尔，量子安全）
└─ 数据加密：AES-GCM（频繁，高速）
Q11: libcrux 实现的 ML-KEM 有什么特点？
A: libcrux-ml-kem 是 FIPS 203 的参考实现之一：
特点：
1. 多平台支持
├─ Portable Rust：纯 Rust 实现，易于验证
├─ AVX2：Intel SIMD 加速（快 3-5 倍）
└─ NEON：ARM 加速（用于手机/ARM 服务器）
自动 CPU 检测，选择最优实现
2. 形式化验证
- 使用 hax 工具（Rust 到 F* 的转译器）
- F* 代码能进行定理证明
- 验证关键加密操作的正确性
3. 无 unsafe 代码
- Rust 实现中不使用 unsafe 块
- 所有内存安全由 Rust 类型系统保证
- 防止常见的 C/C++ 漏洞（缓冲区溢出等）
4. 完整的参数集支持
- ML-KEM-512、768、1024
- 三个 API：generate_key_pair、encapsulate、decapsulate
- 加上验证函数：validate_public_key、validate_private_key
用途：
✓ 工业级密钥交换库
✓ 可集成到 TLS、VPN、区块链等
✓ 经过 NIST 测试向量验证
Q12: ML-KEM 何时开始被广泛采用？
A: 时间表（预测）：
现在（2024-2026）：研究和试验
- FIPS 203 刚发布
- 学术界和安全公司评估
- 标准化 TLS 集成（RFC 9440）
- 小范围试验部署
短期（2026-2030）：混合部署
- TLS 1.3 支持 ML-KEM
- 主要浏览器/Web 服务器更新
- 混合方案：ECDHE + ML-KEM
- 许多用户已受保护
中期（2030-2040）：过渡期
- 如果量子计算机威胁成熟
加快采用速度
- 如果威胁未实现
保持保守策略
- ML-KEM 逐渐成为主流
长期（2040+）：标准配置
- 假设量子计算机存在
- ML-KEM 成为默认选择
- ECC 逐步淘汰
驱动因素：
1. 量子计算机的实际进展
2. 加密社区的信心
3. 向后兼容性需求
4. 性能优化
总结
ML-KEM 的核心价值：
- 后量子安全：对量子计算机有免疫力
- 基于成熟理论：格论研究 50+ 年
- 国际标准：FIPS 203 正式批准
- 实用性：性能和大小可接受
- 工业就绪：多个生产级实现
关键记住：
- ML-KEM 是 KEM（密钥封装），不是加密或签名算法
- 用于建立共享密钥，不直接加密用户数据
- 难度来自 768 维格的几何特性，而不是简单的"空间大小"
- 包含隐式拒绝机制防止定时攻击
- 最佳实践是与对称加密（AES-GCM）配套使用
对应用开发者：
如果你需要向后兼容地升级到后量子安全，现在就应该：
- 评估 libcrux-ml-kem 或类似库
- 实现混合方案（ECC + ML-KEM）
- 在测试网或非关键系统试验
- 为长期迁移做准备
对研究者：
ML-KEM 基于的 LWE 问题仍有开放问题：
- 量子算法是否有显著改进？
- 格基约化（lattice reduction）的实际界限是什么？
- 参数选择的安全余量是否足够？
这些问题的答案将决定后量子密码学的未来。
参考资源
- FIPS 203：https://csrc.nist.gov/pubs/fips/203/final
- libcrux 项目：https://github.com/cryspen/libcrux
- RFC 9440：TLS 1.3 with ML-KEM
- ML-DSA (FIPS 204)：格基数字签名
- SLH-DSA (FIPS 205)：基于哈希的签名（另一个后量子选项）
本文档最后更新：2026 年 5 月 29 日 作者：基于 libcrux 项目的详细研究
