CRYSTALS-Kyber 密钥封装算法原理详解

引言

CRYSTALS-Kyber 是 NIST 后量子密码学标准中的核心密钥封装机制（Key Encapsulation Mechanism, KEM），于 2024 年正式发布。作为 TLS 1.3 未来版本中 ECDHE 的潜在替代方案，理解 Kyber 的工作原理对于安全工程师至关重要。本文将深入解析 Kyber 的数学基础和工作流程。

1. 为什么需要后量子 KEM？

传统 TLS 1.3 使用 ECDHE（椭圆曲线 Diffie-Hellman）进行密钥交换，其安全性基于有限域上离散对数问题的困难性。

量子计算机的 Shor 算法能在多项式时间内解决：

整数分解问题（RSA 密钥）
离散对数问题（ECDSA、ECDHE 密钥）

这意味着：一旦拥有足够大规模的量子计算机，当前基于 RSA 和 ECC 的密钥交换将不再安全。

后量子密码学（Post-Quantum Cryptography, PQC）应运而生——设计能够抵御量子攻击的经典算法。NIST 于 2024 年正式发布后量子密码学标准，CRYSTALS-Kyber 正是其中的核心算法。

2. 格理论基础

Kyber 的安全性建立在**格理论（Lattice-based Cryptography）**之上。

什么是格？

格（Lattice）是 n 维空间中一组线性无关向量的整数线性组合。用数学语言描述：

给定 n 个线性无关的向量 b₁, b₂, …, bₙ ∈ ℝⁿ，格 L 是这些向量的所有整数线性组合的集合：

1

L = { Σᵢ aᵢbᵢ | aᵢ ∈ ℤ }

格困难问题

格密码学的安全性基于以下困难问题：

问题	描述
SVP	最短向量问题（Shortest Vector Problem）：在格中找到最短的非零向量
CVP	最近向量问题（Closest Vector Problem）：给定一个目标向量，找到格中最近的向量
SIS	短整数解问题（Short Integer Solution）
LWE	带错误的学习问题（Learning With Errors）

这些问题的困难性在于：即使使用量子计算机，也没有已知的有效算法能在合理时间内解决这些问题。

3. Module-LWE 问题

Kyber 的核心安全基础是 Module-LWE（模块格上带错误的学习问题）。

LWE 问题

原始 LWE 问题定义如下：

给定矩阵 A ∈ ℤₚ^(n×m)、向量 b = As + e ∈ ℤₚ^m，其中：

s ∈ ℤₚ^n 是秘密向量
e ∈ ℤₚ^m 是小随机误差向量（“噪声”）

LWE 问题：已知 (A, b)，难以恢复 s。

Module-LWE

Module-LWE 是 LWE 的模块化版本，将向量组织成矩阵：

1

b = A·s + e (mod q)

其中：

A ∈ ℤ_q^(k×k)：公开的"矩阵"
s ∈ ℤ_q^k：秘密向量
e ∈ ℤ_q^k：噪声向量
q：一个大素数（Kyber 使用 q = 3329）

为什么 Module-LWE 更高效？

相比原始 LWE，Module-LWE 在保持安全性的同时大幅减少了密钥和密文的大小——这是实用密码系统的关键指标。

4. Kyber 参数与安全性

Kyber 提供三个安全级别：

算法	安全性级别	典型对应
Kyber-512	安全强度 ≈ AES-128	短期安全
Kyber-768	安全强度 ≈ AES-192	中期安全
Kyber-1024	安全强度 ≈ AES-256	长期安全

NIST 建议：

大多数场景使用 Kyber-768
高安全需求场景使用 Kyber-1024

5. Kyber 工作流程

Kyber 是一个密钥封装机制（KEM），包含三个核心算法：

5.1 密钥生成 (KeyGen)

1
2


输入：无
输出：(pk, sk) —— 公钥/私钥对

从离散高斯分布采样秘密向量 s 和噪声向量 e
生成随机矩阵 A
计算 t = A·s + e (mod q)
公钥 pk = (A, t)
私钥 sk = s

5.2 封装 (Encapsulate)

1
2


输入：接收方公钥 pk
输出：(c, K) —— 密文和共享密钥

从小分布采样随机向量 m（消息）和 r（随机噪声）
计算 u = Aᵀ·r + e₁ (mod q)
计算 v = t·r + e₂ + ⌊q/2⌋·m (mod q)
密文 c = (u, v)
从密文派生共享密钥 K

5.3 解封装 (Decapsulate)

1
2


输入：密文 c，私钥 sk
输出：共享密钥 K

从密文中提取 u 和 v
计算 K’ = v - s·u (mod q)
从 K’ 派生共享密钥
对比 K’ 和 K，验证密钥正确性

工作流程图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


接收方 KeyGen                    发送方 Encapsulate
┌─────────────┐                 ┌─────────────────────┐
│  生成 (pk,  │                 │  收到 pk            │
│      sk)    │                 │  采样 m, r          │
│     sk ← s  │                 │  计算 u = Aᵀr + e₁  │
│  pk = (A,t) │  ─────pk─────→  │  计算 v = tr + e₂   │
└─────────────┘  (公开)          │       + ⌊q/2⌋·m    │
                                 │  c = (u, v)        │
                                 │  派生 K             │
                                 └─────────┬───────────┘
                                           │ c
                                           ↓
                                 ┌─────────────────────┐
                                 │  Decapsulate        │
                                 │  K' = v - su        │
                                 │  派生 K             │
                                 └─────────────────────┘

6. 安全性分析

6.1 量子电阻

Kyber 的安全性依赖于：

Module-LWE 问题的困难性：没有已知的量子算法能够有效解决
格困难问题：SVP、CVP 在量子计算机上仍是困难问题

6.2 混合部署

当前主流做法是混合部署（Hybrid）：

同时运行传统 ECDHE + 后量子 Kyber
攻击者必须同时破解两种算法才能解密

这是当前 TLS 和 SSH 部署的推荐策略。

7. 实际使用

⚠️ 注意：以下功能需要特定版本的 OpenSSL 和 OpenSSH。

OpenSSL（需要 3.2+ 版本）

OpenSSL 3.0.x 系列尚未内置 PQC 算法支持。预计在 OpenSSL 3.2+ 版本中添加 ML-KEM 和 ML-DSA 的原生支持。

1
2
3
4
5
6


# 查看支持的 KEM 算法（需要 OpenSSL 3.2+）
openssl list -kem-algorithms

# 生成 ML-KEM-768 密钥对（需要 OpenSSL 3.2+）
openssl genpkey -algorithm ML-KEM-768 -out kem_private.pem
openssl pkey -in kem_private.pem -pubout -out kem_public.pem

当前环境（OpenSSL 3.0.20）不支持 ML-KEM：

1
2


$ openssl list -kem-algorithms
RSA, rsaEncryption

OpenSSH（需要 9.9+ 版本）

OpenSSH 从 9.9 版本开始原生支持 mlkem768x25519-sha256 混合密钥交换。OpenSSH 10.0（2025年4月发布）将其作为默认算法。

当前环境（OpenSSH 9.2）不支持 mlkem768x25519：

1
2


$ ssh -V
OpenSSH_9.2p1 Debian-2+deb12u10

如需使用后量子 KEX，可升级到 OpenSSH 9.9+ 并使用：

1
2
3
4
5


# 查看 SSH 连接的密钥交换算法
ssh -vv user@host 2>&1 | grep "KEX算法"

# 手动指定后量子 KEX（需要 OpenSSH 9.9+）
ssh -o KexAlgorithms=mlkem768x25519-sha256 user@host

8. 总结

CRYSTALS-Kyber（现称 ML-KEM）是 NIST 后量子密码学标准的核心算法：

数学基础：基于 Module-LWE 问题的困难性
安全性：提供 AES-128/192/256 对应的安全强度
性能：相比传统 ECDHE，密钥和密文更紧凑
部署：已在 OpenSSH 9.9+、OpenSSL 3.2+ 中支持

随着量子计算的发展，提前了解并部署后量子密码学算法将是安全工程师的重要任务。

参考来源

NIST Post-Quantum Cryptography Standardization: https://csrc.nist.gov/projects/post-quantum-cryptography
CRYSTALS-Kyber Specification: https://pq-crystals.org/kyber/
RFC 9180: Hybrid Public Key Encryption (HPKE)

引言#

1. 为什么需要后量子 KEM？#

2. 格理论基础#

什么是格？#

格困难问题#

3. Module-LWE 问题#

LWE 问题#

Module-LWE#

4. Kyber 参数与安全性#

5. Kyber 工作流程#

5.1 密钥生成 (KeyGen)#

5.2 封装 (Encapsulate)#

5.3 解封装 (Decapsulate)#

工作流程图#

6. 安全性分析#

6.1 量子电阻#

6.2 混合部署#

7. 实际使用#

OpenSSL（需要 3.2+ 版本）#

OpenSSH（需要 9.9+ 版本）#

8. 总结#

参考来源#

引言