2. ML-KEM数学基础

ML-KEM（FIPS 203）的安全性建立在格上困难问题之上，而它的全部运算都发生在两个代数结构中：模整数环 Z_q 和多项式环 R_q = Z_q[X]/(X^n+1)。理解这两个结构以及它们之间的转换（NTT），是读懂密钥生成、封装与解封装流程的前提。本节按“模运算 → 多项式环 → NTT → 采样 → 压缩 → 噪声与失败概率”的顺序展开，并给出可复算的教学示例。

一、模运算：一切系数的取值域

ML-KEM 使用模数 q = 3329，多项式次数 n = 256。所有系数都是 Z_q 中的元素，即取值 0..3328。加减乘除（除即乘逆元）都在模 q 下进行。例如 3300 + 100 = 3400 ≡ 71 (mod 3329)；2 × 2000 = 4000 ≡ 671 (mod 3329)。

工程实现中常使用“中心表示”：把 0..3328 映射到 -1664..1664，即大于 q/2 的值减去 q。这样噪声系数（通常很小）与乘积结果的正负号更直观。需要注意：参照约定必须全文一致——本节及图示中，中心表示定义为“若 a > 1664，则取 a - 3329”，否则保持原值。

二、多项式环 R_q 与乘法代价

环 R_q 的元素是次数小于 256 的多项式，系数在 Z_q 中，乘法后对 X^256 + 1 取模。这个“减一”的模多项式使 X^256 ≡ -1，因此两个多项式相乘时，高次项会以负号折叠回低次项。朴素卷积需要约 n² = 65536 次模乘，对嵌入式设备偏重；ML-KEM 因此采用 NTT 把多项式乘法降到 O(n log n)。

三、NTT：把卷积变成点乘

NTT（数论变换）是有限域上的 FFT。因为 q - 1 = 3328 = 2^8 × 13，Z_q 中存在 256 次本原单位根，所以可以对 256 个系数做完整的 NTT。变换后，两个多项式在 NTT 域中逐点相乘，再逆变换回来，就等价于环上的乘法。

ML-KEM 实际使用的是“不完全 NTT”：把 256 个系数分成 128 组，每组 2 个系数，对应 128 个二次剩余对。这样做的原因是 X^256+1 在 Z_q 上分解为 128 个二次不可约因式，NTT 域中的每个“点”其实是一个二次多项式。工程上常把 NTT 写成 7 层蝶形运算，每层使用预计算的旋转因子 ζ 的幂。

四、采样：噪声从哪来

ML-KEM 需要两类采样。第一类是中心二项分布 CBD_η，用于生成秘密向量 s 和误差向量 e。CBD_η 的取值是 -η..η，概率随偏离 0 而下降。以 η = 2 为例，系数由 4 个随机比特两两相减得到：a = b₀ + b₁，b = b₂ + b₃，输出 a - b。这样每个系数取值 -2..2，且分布接近离散高斯，但采样只需均匀比特，便于恒定时间实现。

第二类是均匀采样，用于生成矩阵 A。做法是把 3 字节（24 比特）拆成两个 12 比特候选值，若小于 q = 3329 则接受，否则丢弃并继续读取。这就是拒绝采样，保证输出在 Z_q 上严格均匀。

五、压缩与解压缩

为了减小密文体积，ML-KEM 对部分多项式做压缩。压缩函数定义为：

Compress_d(x) = ⌊(2^d / q) · x⌉ mod 2^d
Decompress_d(y) = ⌊(q / 2^d) · y⌉

其中 ⌊·⌉ 表示四舍五入到最近整数。以 d = 10 为例，2^10 = 1024，压缩把 0..3328 映射到 0..1023，每个值约代表 3.25 个原始值。解压缩再放大回 Z_q，但会引入最多约 q/2^(d+1) 的误差。这个误差会叠加到解密噪声上，是失败概率分析中必须计入的一项。

六、噪声增长与解密失败概率

解封装时，接收方计算 m' = Decompress(Compress(v - sᵀu))。展开后，噪声项大致为 eᵀr + e₂ + 压缩误差。CBD_η 的系数方差约为 η/2，两个多项式相乘后噪声会随项数增长。ML-KEM 通过选择 η = 2（ML-KEM-512）或 η = 3（ML-KEM-768/1024），并配合压缩位数 d_u = 10, d_v = 4，把单次解密的失败概率压到约 2⁻¹³⁹ 量级。这个数字不是“零”，但在密码学意义上可忽略。

掌握以上六个环节后，就能理解 ML-KEM 为什么能在 q = 3329、n = 256 这样“小”的参数下同时获得高效运算和可证明的安全性：模运算提供有限域，多项式环提供代数结构，NTT 提供快速乘法，采样提供噪声，压缩控制体积，而噪声分析保证解密失败概率足够低。