ML-KEM（模块格基密钥封装机制）科普指南

 

目录

1. 简介
2. 核心概念
3. 数学原理
4. 密钥结构与数据流
5. 安全性分析
6. 应用场景
7. 常见问题 FAQ

---

简介

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 的核心价值：

1. 后量子安全：对量子计算机有免疫力
2. 基于成熟理论：格论研究 50+ 年
3. 国际标准：FIPS 203 正式批准
4. 实用性：性能和大小可接受
5. 工业就绪：多个生产级实现

关键记住：

• ML-KEM 是 KEM（密钥封装），不是加密或签名算法
• 用于建立共享密钥，不直接加密用户数据
• 难度来自 768 维格的几何特性，而不是简单的"空间大小"
• 包含隐式拒绝机制防止定时攻击
• 最佳实践是与对称加密（AES-GCM）配套使用

对应用开发者：

如果你需要向后兼容地升级到后量子安全，现在就应该：

1. 评估 libcrux-ml-kem 或类似库
2. 实现混合方案（ECC + ML-KEM）
3. 在测试网或非关键系统试验
4. 为长期迁移做准备

对研究者：

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 项目的详细研究