fallensigh/mlkem-sync

Fork 0

Files

FallenSigh 5d86000231 add docs and test data

2026-06-27 03:53:53 +08:00

12 KiB

Executable File

Raw Permalink Blame History

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: Â[i][j] ← SampleNTT(ρ||j||i)  × k² 次
            └─ Â 是 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̂ ← Â ∘ ŝ + ê          矩阵乘 + 加噪声（全在 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:  用 ρ 重生成 Â（与 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⁻¹(Âᵀ ∘ ŷ) + e1     注意：Â 转置！
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 调用示例
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），已知无高效量子算法。

12 KiB Executable File Raw Permalink Blame History Unescape Escape