3. ML-KEM算法规范精读
ML-KEM（FIPS 203）把整个密钥封装机制拆成三个确定性算法：KeyGen、Encaps、Decaps。三者共享同一套底层结构——参数集（k、n=256、q=3329、η₁、η₂、dᵤ、dᵥ）、NTT 域上的多项式运算、以及基于 SHAKE 的 XOF/PRF。理解规范的关键，不是记住每个函数名，而是看清“哪些量是输入、哪些量是内部状态、哪些量最终被编码进密文或密钥”。
一、KeyGen：从随机种子到 (ek, dk)
KeyGen 的输入是一个 32 字节随机种子 d（以及可选的 z，用于隐式拒绝）。规范内部先做种子扩展：(ρ, σ) ← G(d ‖ k)，其中 G 是 SHA3-512，k 是参数集标识。ρ 是 32 字节的矩阵种子，σ 是 32 字节的噪声种子。
矩阵生成由 SampleNTT 完成：对 A 的每个元素 A[i][j]，取 XOF(ρ, j, i) 输出的字节流，按 12 位一组解析，若值小于 q 则接受，否则丢弃并继续取字节，直到填满 256 个系数。注意索引顺序是 (j, i) 而非 (i, j)，这是规范中容易写错的一处。
错误向量采样由 SamplePolyCBD_η 完成：从 PRF(σ, N) 取 64η 字节，按 η 位一组拆成 2η 个系数，两两相减得到中心二项分布采样。η₁ 用于 s 和 e，η₂ 用于 e₁、e₂。随后 s、e 进入 NTT 域，计算 t̂ = Â ∘ ŝ + ê。
输出编码：ek = ByteEncode₁₂(t̂) ‖ ρ，dk = ByteEncode₁₂(ŝ) ‖ ek ‖ H(ek) ‖ z。其中 H 是 SHA3-256，z 用于 Decaps 的隐式拒绝分支。
二、Encaps：从 ek 与随机消息到 (K, c)
Encaps 输入是 ek 和 32 字节随机消息 m。先计算 (K, r) ← G(m ‖ H(ek))，K 是 32 字节共享密钥，r 是 32 字节加密随机性。随后用 SamplePolyCBD_η₁ 从 r 采样 y，用 SamplePolyCBD_η₂ 从 r 采样 e₁、e₂。
核心计算是 u = NTT⁻¹(Âᵀ ∘ ŷ) + e₁，v = NTT⁻¹(t̂ᵀ ∘ ŷ) + e₂ + Decompress₁(m)。这里 Âᵀ 表示转置，m 先经 Decompress₁ 映射到多项式系数，再叠加到 v 上。最后压缩：c₁ = Compress_dᵤ(u)，c₂ = Compress_dᵥ(v)，密文 c = c₁ ‖ c₂。
三、Decaps：从 dk 与 c 恢复 K
Decaps 输入是 dk 和密文 c。先从 dk 中拆出 ŝ、ek、H(ek)、z。对 c 解压得到 u′、v′，计算 m′ = Compress₁(Decode₁(v′ − NTT⁻¹(ŝᵀ ∘ NTT(u′))))。然后重加密：(K′, r′) ← G(m′ ‖ H(ek))，用 r′ 重新生成密文 c′。若 c = c′，输出 K′；否则输出 J(z ‖ c)，即隐式拒绝。
四、参数与编码速查
| 参数 | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|---|---|---|---|
| k | 2 | 3 | 4 |
| η₁ / η₂ | 3 / 2 | 2 / 2 | 2 / 2 |
| dᵤ / dᵥ | 10 / 4 | 10 / 4 | 11 / 5 |
| ek 字节 | 800 | 1184 | 1568 |
| dk 字节 | 1632 | 2400 | 3168 |
| c 字节 | 768 | 1088 | 1568 |
编码规则：ByteEncode_d 把多项式系数按 d 位打包，ByteDecode_d 反向还原；Compress_d 做 round(2^d / q · x) mod 2^d，Decompress_d 做 round(q / 2^d · y)。所有舍入都采用“四舍五入到最近整数，平局取偶”的规则，实现时必须与规范一致，否则 Decaps 会因 c′ ≠ c 而误触发拒绝。
把三个算法放在一起看，会发现它们共享同一套“种子→采样→NTT→编码”的流水线，区别只在于输入种子来源和最终输出形态。KeyGen 用 d 生成长期密钥，Encaps 用 m 生成一次性密钥和密文，Decaps 则用 dk 中的 ŝ 做一次“解密+重加密”的一致性校验。真正需要逐字节对齐规范的，是 SampleNTT 的拒绝采样边界、SampleCBD 的位拆分顺序、以及 Compress 的舍入规则——这三处一旦偏差，Decaps 的 c′ 就会与 c 不等，导致合法密文被误判为篡改。