CRYSTALS-Kyber：基于格的 KEM

CRYSTALS-Kyber（NIST 在 FIPS 203 中将其更名为 ML-KEM）是一种基于模-LWE 的密钥封装机制（KEM）。它可以替代 RSA 和 ECDH 进行密钥交换，并以实用的性能提供抗量子能力。

KEM 会封装共享密钥：发送方生成随机密钥 K，使用接收方的公钥对其加密（封装），生成密文 C。接收方使用私钥对 C 进行解封装，以恢复 K。整个过程无需交互式密钥交换。

Kyber 在环 R_q = Z_q[x]/(x^256+1) 上使用模-LWE，其中 q=3329。维度 k=2（Kyber-512）、k=3（Kyber-768）、k=4（Kyber-1024）。相应的安全强度约为 128、192 和 256 位。推荐的默认参数是 k=3（Kyber-768）。

根据种子 ρ（可扩展）生成矩阵 A ∈ R_q^{k×k}。从中心二项分布中采样秘密值 s 和噪声 e（系数较小）。公钥为 (ρ, t=As+e)，私钥为 s。噪声 e 很小，但可以防止攻击者从公钥中恢复 s。

要向公钥持有者发送共享秘密（ρ, t），请从噪声分布中采样 r、e1、e2。计算 u = A^T r + e1，v = t^T r + e2 + round(q/2)*m，其中 m 是一个随机的 256 位消息。共享密钥 K = KDF(m)。密文 = (u, v)。

使用私钥 s：计算 m' = decompress(v - s^T u) = decompress(t^T r + e2 + round(q/2)*m - s^T(A^T r + e1))。噪声项会近似抵消，剩下的结果为 m'≈m。计算 K = KDF(m')。解封装失败的概率为 < 2^{-139}。

Kyber-768：公钥 1184 字节，私钥 2400 字节，密文 1088 字节，共享密钥 32 字节。相比之下，ECDH-P256 的公钥为 65 字节，密文为 32 字节。Kyber 的大小约为其 15 倍，但可以抵抗量子攻击。它仍然很快：在现代 CPU 上，封装加解封装耗时 < 1 ms。

环 R_q = Z_q[x]/(x^256+1) 中的多项式乘法使用数论变换（NTT），这是 FFT 在模运算中的对应形式。NTT 将多项式乘法的复杂度从 O(n^2) 降低到 O(n log n)。选择 q=3329 是因为它对 n=256 具有良好的 NTT 特性。

在 PQC 迁移期间，请使用混合密钥交换：组合 ECDH 和 Kyber。共享密钥 = KDF(ECDH_output || Kyber_output)。安全性要求攻击者同时破解两者：经典攻击者无法破解任一者；量子攻击者可以破解 ECDH，但无法破解 Kyber。TLS 1.3 草案（IETF RFC 8446）支持混合 KEM。

简单实现中的 Kyber 解封装并非常数时间——拒绝采样步骤会泄露时序信息。参考实现使用常数时间 NTT 和压缩密文比较。请使用 NIST 提交的参考代码或经过审计的库实现。

NIST 于 2024 年 8 月发布了 FIPS 203（ML-KEM）。Chrome 于 2023 年在 TLS 1.3 中加入了 Kyber 支持。Cloudflare、Google 和 AWS 正在部署 ECDH+Kyber 混合方案。OpenSSL 3.x 已加入 ML-KEM 支持。LibSSH 和 WireGuard 的实现正在开发中。

哪个 NIST 标准文档对 CRYSTALS-Kyber 进行了标准化？

Kyber（ML-KEM）是基于模-LWE 的 KEM，用于替代 ECDH。密钥大小约为 1 KB；NTT 运算速度快；能够抵抗量子攻击。迁移期间应将其与 ECDH 组成混合方案进行部署。它已在 FIPS 203 中标准化。下一节：CRYSTALS-Dilithium 和 Falcon 签名方案。