4. Kyber KEM工程实现

Kyber 是 NIST PQC 标准中 ML-KEM（FIPS 203）的基础算法，其工程实现围绕三个核心操作展开：密钥生成（KeyGen）、封装（Encaps）和解封装（Decaps）。与教科书式的 RSA/ECC 不同，Kyber 的安全性建立在 MLWE（Module Learning With Errors）问题上，其实现涉及多项式环运算、NTT 加速、拒绝采样、压缩编码等多个工程细节。本节从代码实现角度，梳理 Kyber 的完整数据流与关键优化点。

一、参数集与数据结构

Kyber 提供三个安全等级的参数集，工程实现中通常用宏或模板参数区分：

其中 N=256 是多项式次数，q=3329 是模数，k 是模块维度。所有多项式运算都在环 R_q = Z_q[X]/(X^256+1) 上进行。工程上通常定义 poly 结构体存储 256 个 int16_t 系数，polyvec 存储 k 个多项式。

二、密钥生成流程

KeyGen 的核心是生成矩阵 A 和误差向量，并计算公钥 t = A·s + e。具体步骤：

1. 用 32 字节随机种子 d 通过 SHAKE-256 扩展出种子 ρ 和 σ；
2. 用 ρ 通过 XOF 生成矩阵 A（k×k 个多项式），每个多项式系数在拒绝采样下均匀分布于 Z_q；
3. 用 σ 通过 CBD（中心二项分布）采样生成秘密向量 s 和误差向量 e，系数范围由 η 决定；
4. 对 s 和 e 做 NTT 变换，得到 ŝ 和 ê；
5. 计算 t̂ = ·ŝ + ê（NTT 域下的点乘与加法）；
6. 公钥 pk = (t̂ 编码 || ρ)，私钥 sk = (ŝ 编码 || pk || H(pk) || z)。

注意：NTT 域下的乘法是逐点相乘，这是 Kyber 性能优化的关键。编码时 t̂ 和 ŝ 的系数需要压缩到 12 位（因为 q=3329 需要 12 位表示），按字节打包。

三、封装与解封装

封装方收到公钥 pk 后：

1. 随机生成 32 字节消息 m，计算 m 的哈希 H(m)；
2. 用 H(m) 和 pk 的哈希做 G 函数（SHA3-512），得到共享密钥 K 和随机数 r；
3. 用 r 重新生成矩阵 A（转置）和误差向量 y、e1、e2；
4. 计算 u = NTT⁻¹(Âᵀ·ŷ) + e1，v = NTT⁻¹(t̂ᵀ·ŷ) + e2 + Decompress(m)；
5. 对 u 和 v 做压缩编码，得到密文 c = (Compress(u) || Compress(v))。

解封装方收到密文 c 后：

1. 解压缩得到 u' 和 v'；
2. 计算 m' = Decompress(v' - NTT⁻¹(ŝᵀ·NTT(u')))；
3. 用 m' 重新封装得到 c'，比较 c 与 c' 是否相等；
4. 若相等输出 K，否则输出 K̄ = H(z || c)（隐式拒绝）。

四、NTT 优化与拒绝采样

Kyber 的 NTT 是负循环卷积 NTT，长度为 256，模数 3329。工程实现中通常预计算 ζ 的幂次表（zetas[128]），采用 Cooley-Tukey 蝶形运算，7 层循环完成变换。关键优化包括：

• 惰性归约：蝶形运算中先做乘法再统一取模，减少模运算次数；
• Montgomery 乘法：用 Montgomery 约减替代除法，QINV = 62209 是 q⁻¹ mod 2¹⁶；
• 预计算旋转因子：zetas 表在编译期生成，避免运行时计算。

拒绝采样用于从 XOF 输出中生成均匀多项式。Kyber 采用 12 位采样：每次取 3 字节，拆成两个 12 位整数 d1、d2，若 d1 < q 则接受，否则拒绝。代码中通常用 csubq 做条件减法，避免分支预测失败。

五、压缩编码实现

压缩编码是 Kyber 密文体积优化的关键。对于 du=10 的情况，每个系数压缩到 10 位，4 个系数打包成 5 字节。实现时用 compress 函数：

// 压缩：x -> round(2^d / q * x) mod 2^d
uint16_t compress(uint16_t x, int d) {
    uint32_t t = ((uint32_t)x << d) + KYBER_Q/2;
    t /= KYBER_Q;
    return t & ((1 << d) - 1);
}

// 解压缩：y -> round(q / 2^d * y)
uint16_t decompress(uint16_t y, int d) {
    return ((uint32_t)y * KYBER_Q + (1 << (d-1))) >> d;
}

打包时按位拼接，注意小端序。Kyber 的密文编码顺序是：先 u（k 个多项式，每个 du 位），再 v（dv 位）。

六、工程实现要点与常见陷阱

在实际编码中，有几个容易出错的点值得注意：

• NTT 域与标准域的混淆：KeyGen 中 s 和 e 需要先做 NTT 再参与点乘，而 u 和 v 的计算中 ŷ 是 NTT 域，但最终结果需要 NTT⁻¹ 回到标准域再加 e₁、e₂。混淆域会导致解密失败。
• 矩阵 A 的转置：Encaps 中使用 Âᵀ，而 KeyGen 中使用 Â。实现时通常用同一个 XOF 生成矩阵，通过索引交换实现转置，避免重复采样。
• 压缩舍入方向：compress 中的 + q/2 和 decompress 中的 + 2^(d-1) 是四舍五入的关键，漏掉会导致解密时 m' 偏差超过容错范围。
• 字节序：Kyber 所有多字节整数均采用小端序，打包时需注意。