340 lines
12 KiB
Markdown
Executable File
340 lines
12 KiB
Markdown
Executable File
# ML-KEM (FIPS 203) 算法详解
|
||
|
||
---
|
||
|
||
## 一、定位与层次
|
||
|
||
ML-KEM 是一种**后量子密钥封装机制**（KEM），基于 Module Learning With Errors（MLWE）困难问题。整个算法分两层：
|
||
|
||
```
|
||
┌──────────────────────────────────────────────┐
|
||
│ ML-KEM 层 (§6-7) │
|
||
│ KeyGen / Encaps / Decaps (Alg 19-21) │
|
||
│ + 内部接口 (Alg 16-18, CAVP 测试用) │
|
||
│ └─ FO 变换: G, H, J 哈希 + 隐式拒绝 │
|
||
├──────────────────────────────────────────────┤
|
||
│ K-PKE 层 (§5) │
|
||
│ KeyGen / Encrypt / Decrypt (Alg 13-15) │
|
||
│ └─ 格密码: A·s+e 噪声线性系统 │
|
||
├──────────────────────────────────────────────┤
|
||
│ 数学基础 (§4) │
|
||
│ 环 R_q = Z_q[x]/(x²⁵⁶+1), q=3329 │
|
||
│ NTT, 采样 (均匀/CBD), 编解码, 压缩 │
|
||
├──────────────────────────────────────────────┤
|
||
│ SHA-3 哈希层 (FIPS 202) │
|
||
│ KECCAK-p[1600,24], SHA3-256/512, SHAKE128/256│
|
||
└──────────────────────────────────────────────┘
|
||
```
|
||
|
||
---
|
||
|
||
## 二、数学基础
|
||
|
||
### 2.1 环 `R_q = Z_q[x]/(x^256 + 1)`
|
||
|
||
| 参数 | 值 |
|
||
|------|-----|
|
||
| 模数 `q` | **3329**（12 bit 素数） |
|
||
| 多项式次数 `n` | **256** |
|
||
| 环定义 | 系数在 `{0,1,...,3328}` 中，乘法模 `x^256+1` |
|
||
|
||
### 2.2 NTT（数论变换）
|
||
|
||
因为 `x^256 + 1` 在 `Z_q` 上分解为 128 个二次因式：
|
||
|
||
```
|
||
x^256 + 1 = Π_{i=0}^{127} (x² − ζ^{2·BitRev₇(i)+1})
|
||
```
|
||
|
||
- **NTT**（正变换）：系数表示 → NTT 域表示（128 对 (a₀, a₁)）
|
||
- **INTT**（逆变换）：NTT 域 → 系数域
|
||
- **MultiplyNTTs**：NTT 域中乘法 = 128 次独立的一次多项式乘法（Algorithm 12 `BaseCaseMultiply`）
|
||
|
||
```
|
||
NTT 域中: 多项式乘法 = O(128) 次 BaseCaseMultiply
|
||
系数域中: 多项式乘法 = O(256×256) 次模乘 ← NTT 加速
|
||
```
|
||
|
||
### 2.3 采样分布
|
||
|
||
| 算法 | 分布 | 说明 |
|
||
|------|------|------|
|
||
| **SampleNTT** (Alg 7) | 均匀分布 | SHAKE128 可扩展输出 + 拒绝采样 |
|
||
| **SamplePolyCBD** (Alg 8) | 中心二项分布 CBD_η | 从 `64η` 字节比特串计算：`x = Σ(b_{2iη+j} − b_{2iη+η+j})`，结果 mod q |
|
||
|
||
CBD_η 参数：
|
||
|
||
| η | 每系数使用比特数 | 输出范围 | PRF 输出 |
|
||
|---|---------------|---------|---------|
|
||
| 2 | 4 bit | `[-2, 2]` → mod q 后 `{3327,3328,0,1,2}` | 128 字节 |
|
||
| 3 | 6 bit | `[-3, 3]` → mod q 后 `{3326,...,0,...,3}` | 192 字节 |
|
||
|
||
CBD 的核心特性：输出值集中在 0 附近（小噪声），且无需高斯采样（硬件友好）。
|
||
|
||
### 2.4 编码与压缩
|
||
|
||
| 算法 | 功能 | 域映射 |
|
||
|------|------|--------|
|
||
| ByteEncode_d / ByteDecode_d | 整数数组 ↔ 字节数组 | `Z_m^256 ↔ B^{32d}`（d=12 时 m=q，否则 m=2^d）|
|
||
| Compress_d / Decompress_d | 压缩 / 解压 | `Z_q ↔ Z_{2^d}`，舍入到最近整数，**禁止浮点** |
|
||
|
||
压缩的数学定义：
|
||
|
||
```
|
||
Compress_d(x) = ⌈(2^d / q) · x⌋ mod 2^d
|
||
Decompress_d(y) = ⌈(q / 2^d) · y⌋
|
||
```
|
||
|
||
关键性质：
|
||
|
||
```
|
||
Compress_d(Decompress_d(y)) = y (对所有 y ∈ Z_{2^d})
|
||
Decompress_d(Compress_d(x)) ≈ x (误差很小，当 d 接近 12)
|
||
```
|
||
|
||
---
|
||
|
||
## 三、K-PKE 层（非对称加密，不可单独使用）
|
||
|
||
核心思想：**带噪声的线性方程组**。
|
||
|
||
```
|
||
私钥: s ∈ R_q^k (k 个秘密多项式)
|
||
公钥: (A, t = A·s + e)
|
||
└─ A ∈ R_q^{k×k}: 伪随机生成（种子 ρ + XOF）
|
||
└─ e ∈ R_q^k: 噪声（CBD 采样）
|
||
```
|
||
|
||
### Algorithm 13: `K-PKE.KeyGen(d)` — 密钥生成
|
||
|
||
```
|
||
输入: 随机种子 d (32 字节)
|
||
输出: ek_PKE (384k+32 B), dk_PKE (384k B)
|
||
|
||
Step 1: (ρ, σ) ← G(d || k) G = SHA3-512, 域分离用 k
|
||
Step 3-7: Â[i][j] ← SampleNTT(ρ||j||i) × k² 次
|
||
└─ Â 是 NTT 域中的矩阵（已在 NTT 域）
|
||
Step 8-11: s[i] ← SamplePolyCBD_η1(PRF_η1(σ, N++)) × k 次
|
||
Step 12-15: e[i] ← SamplePolyCBD_η1(PRF_η1(σ, N++)) × k 次
|
||
Step 16-17: ŝ ← NTT(s), ê ← NTT(e)
|
||
Step 18: t̂ ← Â ∘ ŝ + ê 矩阵乘 + 加噪声（全在 NTT 域）
|
||
Step 19-20: 序列化：ByteEncode₁₂(t̂) || ρ → ek
|
||
ByteEncode₁₂(ŝ) → dk
|
||
```
|
||
|
||
### Algorithm 14: `K-PKE.Encrypt(ek, m, r)` — 加密
|
||
|
||
```
|
||
输入: ek, 明文 m (32B), 随机数 r (32B)
|
||
输出: 密文 c
|
||
|
||
Step 2-3: 从 ek 解析 t̂ 和 ρ
|
||
Step 4-8: 用 ρ 重生成 Â（与 KeyGen 相同）
|
||
Step 9-12: y[i] ← CBD_η1(PRF_η1(r, N++)) × k
|
||
Step 13-16: e1[i] ← CBD_η2(PRF_η2(r, N++)) × k
|
||
Step 17: e2 ← CBD_η2(PRF_η2(r, N++))
|
||
Step 18: ŷ ← NTT(y)
|
||
Step 19: u ← NTT⁻¹(Âᵀ ∘ ŷ) + e1 注意：Â 转置！
|
||
Step 20: μ ← Decompress₁(ByteDecode₁(m)) 明文编码为 Z_q 多项式
|
||
Step 21: v ← NTT⁻¹(t̂ᵀ ∘ ŷ) + e2 + μ
|
||
Step 22-23: c₁ ← ByteEncode_du(Compress_du(u))
|
||
c₂ ← ByteEncode_dv(Compress_dv(v))
|
||
Step 24: c ← c₁ || c₂
|
||
```
|
||
|
||
**为什么加密能解密？**
|
||
|
||
```
|
||
解密计算: v' − sᵀ·u'
|
||
= (tᵀ·y + e2 + μ) − sᵀ·(Aᵀ·y + e1)
|
||
= (A·s + e)ᵀ·y + e2 + μ − sᵀ·Aᵀ·y − sᵀ·e1
|
||
= sᵀ·Aᵀ·y + eᵀ·y + e2 + μ − sᵀ·Aᵀ·y − sᵀ·e1
|
||
= μ + (eᵀ·y + e2 − sᵀ·e1)
|
||
≈ μ ← 噪声项很小，四舍五入恢复
|
||
```
|
||
|
||
### Algorithm 15: `K-PKE.Decrypt(dk, c)` — 解密
|
||
|
||
```
|
||
Step 5: ŝ ← ByteDecode₁₂(dk)
|
||
Step 6: w ← v' − NTT⁻¹(ŝᵀ ∘ NTT(u'))
|
||
Step 7: m ← ByteEncode₁(Compress₁(w))
|
||
```
|
||
|
||
---
|
||
|
||
## 四、ML-KEM 层（CCA 安全 KEM）
|
||
|
||
在 K-PKE（CPA 安全）基础上，通过 **Fujisaki-Okamoto 变换** 升级为 CCA 安全。
|
||
|
||
### 所用哈希函数
|
||
|
||
| 函数 | 底层 | 用途 |
|
||
|------|------|------|
|
||
| **G** | SHA3-512 | KeyGen: `(ρ,σ)←G(d‖k)`；Encaps: `(K,r)←G(m‖H(ek))`；Decaps: `(K',r')←G(m'‖h)` |
|
||
| **H** | SHA3-256 | `H(ek)` 存在 dk 中用于验证；Encaps 中参与 G 输入 |
|
||
| **J** | SHAKE256(_, 256) | **隐式拒绝**：`K̄←J(z‖c)`，当重加密密文不匹配时使用 |
|
||
|
||
### Algorithm 16: `KeyGen_internal(d, z)` — 内部密钥生成
|
||
|
||
```
|
||
dk_PKE ← K-PKE 的解密密钥 (384k B)
|
||
ek_PKE ← K-PKE 的加密密钥 (384k+32 B)
|
||
h ← H(ek_PKE) 32 B
|
||
z ← 随机 (32 B, 隐式拒绝用)
|
||
|
||
dk = dk_PKE || ek_PKE || h || z 共 768k+96 B
|
||
ek = ek_PKE 共 384k+32 B
|
||
```
|
||
|
||
### Algorithm 17/20: `Encaps(ek)` — 封装
|
||
|
||
```
|
||
Step 1: m ←$ B³² 随机 32 字节
|
||
Step 2: (K, r) ← G(m || H(ek)) K = 共享密钥, r = 加密随机数
|
||
Step 3: c ← K-PKE.Encrypt(ek, m, r)
|
||
Output: (K, c)
|
||
```
|
||
|
||
### Algorithm 18/21: `Decaps(dk, c)` — 解封装
|
||
|
||
```
|
||
Step 1-4: 解析 dk → dk_PKE, ek_PKE, h, z
|
||
Step 5: m' ← K-PKE.Decrypt(dk_PKE, c)
|
||
Step 6: (K', r') ← G(m' || h)
|
||
Step 7: K̄ ← J(z || c) 隐式拒绝密钥
|
||
Step 8: c' ← K-PKE.Encrypt(ek_PKE, m', r')
|
||
Step 9-11: if c ≠ c' then K' ← K̄ 隐式拒绝！
|
||
Output: K'
|
||
```
|
||
|
||
**隐式拒绝的作用**：如果攻击者篡改了密文：
|
||
|
||
- 解密得到 `m' ≠ m`（噪声导致）
|
||
- 重加密得到 `c' ≠ c`
|
||
- 返回 `J(z || c)` 而非 `G(m' || h)`
|
||
- 攻击者**不知道**解密失败（无显式错误），无法利用侧信道
|
||
|
||
**通信流程（7 步）**：
|
||
|
||
```
|
||
Alice Bob
|
||
───── ───
|
||
key_gen() → (ek, dk)
|
||
──── ek ────▶
|
||
encaps(ek) → (K, ct_kem)
|
||
xor_crypt(K, "hello world") → encrypted
|
||
◀─ (ct_kem, encrypted) ──
|
||
decaps(dk, ct_kem) → K'
|
||
xor_crypt(K', encrypted) → "hello world" ✓
|
||
```
|
||
|
||
---
|
||
|
||
## 五、参数集
|
||
|
||
| 参数 | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|
||
|------|-----------|-----------|-------------|
|
||
| **k**（矩阵维度） | 2 | 3 | 4 |
|
||
| **η₁**（s, e, y 噪声） | 3 | 2 | 2 |
|
||
| **η₂**（e1, e2 噪声） | 2 | 2 | 2 |
|
||
| **du**（u 压缩） | 10 | 10 | 11 |
|
||
| **dv**（v 压缩） | 4 | 4 | 5 |
|
||
| NIST 安全类别 | 1 (≈AES-128) | 3 (≈AES-192) | 5 (≈AES-256) |
|
||
|
||
### 密钥与密文大小
|
||
|
||
| 对象 | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|
||
|------|-----------|-----------|-------------|
|
||
| ek（公钥） | 800 B | 1184 B | 1568 B |
|
||
| dk（私钥） | 1632 B | 2400 B | 3168 B |
|
||
| c（密文） | 768 B | 1088 B | 1568 B |
|
||
| K（共享密钥） | 32 B | 32 B | 32 B |
|
||
|
||
---
|
||
|
||
## 六、输入检查（FIPS 203 §7）
|
||
|
||
### Encaps（§7.2）— 封装密钥检查
|
||
|
||
```
|
||
1. 类型检查: ek 长度 = 384k+32
|
||
2. 模数检查: ByteEncode₁₂(ByteDecode₁₂(ek[0:384k])) == ek[0:384k]
|
||
确保编码的值在 [0, q-1] 范围内，无模归约
|
||
```
|
||
|
||
### Decaps（§7.3）— 解封装输入检查
|
||
|
||
```
|
||
1. 密文类型检查: c 长度 = 32(du·k + dv)
|
||
2. 私钥类型检查: dk 长度 = 768k+96
|
||
3. 哈希检查: H(dk[384k:768k+32]) == dk[768k+32:768k+64]
|
||
确保 dk 中的 ek_PKE 未被篡改
|
||
```
|
||
|
||
---
|
||
|
||
## 七、Const Generic 参数映射
|
||
|
||
| Rust 参数 | 含义 | 512 | 768 | 1024 |
|
||
|-----------|------|-----|-----|------|
|
||
| `K` | 矩阵维度 | 2 | 3 | 4 |
|
||
| `ETA_BYTES` | 64·η₁ | 192 | 128 | 128 |
|
||
| `ETA2_BYTES` | 64·η₂ | 128 | 128 | 128 |
|
||
| `DU` | u 压缩 | 10 | 10 | 11 |
|
||
| `DV` | v 压缩 | 4 | 4 | 5 |
|
||
|
||
```rust
|
||
// Rust 调用示例
|
||
ml_kem::key_gen::<2, 192>(&d, &z); // ML-KEM-512
|
||
ml_kem::encaps::<2, 192, 128, 10, 4>(&ek, &m); // ML-KEM-512
|
||
ml_kem::decaps::<2, 192, 128, 10, 4>(&dk, &c); // ML-KEM-512
|
||
```
|
||
|
||
---
|
||
|
||
## 八、算法依赖关系图
|
||
|
||
```
|
||
Algorithm 19 key_gen ──────────────┐
|
||
Algorithm 20 encaps ───────────────┤
|
||
Algorithm 21 decaps ───────────────┤
|
||
▼
|
||
Algorithm 16 keygen_internal ──────┐
|
||
Algorithm 17 encaps_internal ──────┤
|
||
Algorithm 18 decaps_internal ──────┤
|
||
▼
|
||
Algorithm 13 K-PKE.KeyGen ─────────┐
|
||
Algorithm 14 K-PKE.Encrypt ────────┤
|
||
Algorithm 15 K-PKE.Decrypt ────────┤
|
||
▼
|
||
Algorithm 7 SampleNTT ────────────┐
|
||
Algorithm 8 SamplePolyCBD ────────┤
|
||
Algorithm 9 NTT ──────────────────┤
|
||
Algorithm 10 INTT ─────────────────┤
|
||
Algorithm 11 MultiplyNTTs ─────────┤
|
||
Algorithm 12 BaseCaseMultiply ─────┤
|
||
Algorithm 5 ByteEncode ───────────┤
|
||
Algorithm 6 ByteDecode ───────────┤
|
||
Algorithm 1 Compress ─────────────┤
|
||
Algorithm 2 Decompress ───────────┤
|
||
Algorithm 3 BitsToBytes ──────────┤
|
||
Algorithm 4 BytesToBits ──────────┤
|
||
▼
|
||
G / H / J / PRF (SHA-3)
|
||
│
|
||
KECCAK-p[1600,24]
|
||
```
|
||
|
||
---
|
||
|
||
## 九、安全性概要
|
||
|
||
| 攻击类型 | K-PKE (CPA) | ML-KEM (CCA) |
|
||
|----------|------------|-------------|
|
||
| 选择明文攻击 (CPA) | ✓ 安全 | ✓ 安全 |
|
||
| 选择密文攻击 (CCA) | ✗ 不安全 | ✓ 安全（FO 变换） |
|
||
| 量子攻击 | 基于 MLWE 困难假设 | 同上 + FO 在 QROM 下安全 |
|
||
|
||
**MLWE 安全性**：区分 `(A, A·s+e)` 和 `(A, u)`（u 均匀随机）的计算困难度 ≈ 格上最短向量问题（SVP），已知无高效量子算法。
|