CRYSTALS-Kyber.

CRYSTALS-Kyber 是一种密钥封装机制(KEM),其安全性可归约到结构化格上的 Module Learning With Errors(MLWE)问题。NIST 于 2022 年选定其为 PQC 主选 KEM,并于 2024 年 8 月将其最终确定为 FIPS 203(ML-KEM)。该标准定义了三个参数集——ML-KEM-512、ML-KEM-768 与 ML-KEM-1024——分别对应 NIST 安全类别 1、3、5;公钥长度约为 800、1184 和 1568 字节,密文长度与之相近。

在内部,一个 IND-CPA 公钥方案通过 Fujisaki–Okamoto 变换被强化为 IND-CCA2 KEM:解封装会对恢复出的消息重新加密,并拒绝任何不匹配的情形,因此被篡改的密文只会产生一个伪随机的"隐式拒绝"密钥,而不会泄露任何秘密。由于"先存储、后解密"的攻击者可能会归档当今的流量以待未来的量子计算机破解,Kyber 以混合模式部署(例如 X25519MLKEM768),攻击者必须同时攻破经典与后量子两个部分。

实现层面的安全性与数学本身同等重要。KyberSlash 披露事件(2024 年)表明,依赖秘密值、以模数 q = 3329 进行的整数除法在许多 CPU 上是变时的;对伪造密文的解封装进行计时可以恢复密钥比特。KyberSlash1 与 KyberSlash2 已在参考代码中通过用乘法替换除法完成修复(2023 年 12 月),相关修复随后传播到 liboqs、PQClean、CIRCL、AWS-LC 与 Botan。

flowchart LR
  KG[密钥生成] --> PK[公钥 pk]
  KG --> SK[私钥 sk]
  PK --> ENC[封装: 选取 m, 派生 K 与密文 c]
  ENC --> C[密文 c]
  ENC --> KS1[共享密钥 K]
  C --> DEC[用 sk 解封装并进行 FO 重加密校验]
  SK --> DEC
  DEC -->|匹配| KS2[相同的共享密钥 K]
  DEC -->|不匹配| REJ[隐式拒绝: 伪随机密钥]