【密码学百科】格基后量子方案：ML-KEM（Kyber）与 ML-DSA（Dilithium）深度解析

2024 年 8 月 13 日，美国国家标准与技术研究院（NIST）正式发布了三项后量子密码学联邦信息处理标准：FIPS 203（ML-KEM）、FIPS 204（ML-DSA）和 FIPS 205（SLH-DSA）。这一里程碑事件标志着长达八年的后量子密码标准化竞赛的主体阶段落幕，也宣告格基密码（Lattice-based Cryptography）正式成为后量子时代公钥密码学的基石。在这三项标准中，前两项——密钥封装机制 ML-KEM（Module-Lattice-based Key-Encapsulation Mechanism，原 CRYSTALS-Kyber）与数字签名算法 ML-DSA（Module-Lattice-based Digital Signature Algorithm，原 CRYSTALS-Dilithium）——均构建在模格（Module Lattice）上的困难问题之上，共享相同的代数框架和底层运算原语。

本文将从格困难问题的数学基础出发，逐步深入 ML-KEM 和 ML-DSA 的算法内部结构，剖析数论变换（Number Theoretic Transform, NTT）等核心运算的实现细节，讨论 Fujisaki-Okamoto 变换和 Fiat-Shamir with Aborts 等关键密码学构造的设计逻辑，分析安全性证明的核心假设，并探讨工程实现中的优化策略与当前的部署进展。

一、从 LWE 到 Module-LWE

格与格问题

格（Lattice）是 n 维欧几里得空间中由一组线性无关的基向量通过整系数线性组合生成的离散点集。形式化地说，给定基矩阵 B = [b_1, b_2, …, b_n]，格 L(B) = { Bx : x ∈ Z^n }。格上的计算困难问题是后量子密码学最重要的安全根基之一。其中，最短向量问题（Shortest Vector Problem, SVP）要求在给定格中找到一个非零的最短格向量；最近向量问题（Closest Vector Problem, CVP）则要求找到格中离给定目标点最近的格向量。这两个问题在最坏情况下都是 NP 困难的，而更重要的是，目前尚无已知的量子算法能对它们提供超多项式加速——Shor 算法的离散对数/因子分解技巧在格问题的结构上找不到着力点。

LWE 问题

带误差学习问题（Learning with Errors, LWE）由 Oded Regev 于 2005 年提出，它将格困难问题转化为一个更适合构建密码方案的形式。LWE 问题的核心是：给定一个随机矩阵 A ∈ Z_q^{m×n}、一个秘密向量 s ∈ Z_q^n 和一个小误差向量 e ∈ Z_q^m（各分量按离散高斯分布或中心二项分布采样），求解者得到 (A, b = As + e mod q)，需要恢复 s 或区分 b 与均匀随机向量。Regev 证明了 LWE 问题在平均情况下的困难性可以归约到格上最坏情况的近似 SVP 问题——这一最坏情况到平均情况的归约是格基密码学最深刻的理论成果之一。

Ring-LWE 与 Module-LWE

原始 LWE 的公钥尺寸为 O(n^2)，在实际参数下过于庞大。为缩小密钥尺寸，学者们引入了代数结构。环上带误差学习问题（Ring-LWE）将矩阵替换为分圆多项式环 R_q = Z_q[x]/(x^n + 1) 中的单个元素，公钥尺寸降至 O(n)，但也带来了额外的代数结构——攻击者可能利用环的特殊性质（如理想格的子结构）发起针对性攻击。

模格上带误差学习问题（Module-LWE, MLWE）在 LWE 和 Ring-LWE 之间取得了精巧的平衡。MLWE 在 R_q 上定义一个 k×k 的矩阵 A，秘密和误差均为 R_q^k 中的向量。当 k = 1 时退化为 Ring-LWE；当多项式次数 n = 1 时退化为标准 LWE。通过调节 k 和 n 两个维度，MLWE 既保留了环结构带来的高效多项式乘法，又因为 k > 1 的矩阵结构稀释了环的代数特殊性，在实践中被认为比纯 Ring-LWE 更为保守。NIST 最终选定的 ML-KEM 和 ML-DSA 都建立在 MLWE 之上，多项式次数固定为 n = 256，模数 q = 3329（ML-KEM）或 q = 8380417（ML-DSA），通过 k = 2, 3, 4 的选取提供不同安全级别。

二、ML-KEM 算法结构

ML-KEM 是一个密钥封装机制（Key-Encapsulation Mechanism, KEM），其功能是在两个通信方之间协商一个共享密钥（Shared Secret）。与传统的公钥加密不同，KEM 不直接加密任意消息，而是封装一个随机产生的密钥——这一设计范式大幅简化了安全性证明，并天然适配混合加密（Hybrid Encryption）的使用场景。

参数集

ML-KEM 定义了三个参数集：

其中 k 决定模格的模块维度，η₁ 和 η₂ 分别控制密钥生成和加密阶段的噪声幅度（采用中心二项分布 CBD_η），d_u 和 d_v 是压缩参数。所有参数集的底层多项式环均为 R_q = Z_q[x]/(x^256 + 1)，q = 3329。

KeyGen（密钥生成）

密钥生成算法 ML-KEM.KeyGen() 的执行过程如下：

1. 采样一个 32 字节的随机种子 d，以及一个 32 字节的随机值 z（用于隐式拒绝）。
2. 利用可扩展输出函数（XOF，基于 SHAKE-128）从种子 d 确定性地生成 k×k 的矩阵 Â（在 NTT 域中表示）。
3. 采样 k 个秘密多项式 s_i 和 k 个误差多项式 e_i，各系数服从 CBD_η₁ 分布。
4. 计算 ŝ = NTT(s) 和 ê = NTT(e)，然后在 NTT 域中计算 t̂ = Â ◦ ŝ + ê。
5. 公钥 ek = (t̂, ρ)（其中 ρ 是生成 Â 的种子），解密密钥 dk = (ŝ, ek, H(ek), z)。

这里有一个重要的设计细节：矩阵 Â 本身并不存储在公钥中，而是通过种子 ρ 在使用时即时生成。这一策略将公钥中矩阵的存储开销从 k^2 · n · ⌈log q⌉ 位压缩至仅 256 位，是 ML-KEM 密钥尺寸远小于标准 LWE 方案的关键原因之一。

Encaps（封装）

封装算法 ML-KEM.Encaps(ek) 的执行过程如下：

1. 采样一个 32 字节的随机消息 m。
2. 计算 (K, r) = G(m ‖ H(ek))，其中 G 是基于 SHA3-512 的哈希函数，K 是最终共享密钥，r 是确定性随机性。
3. 使用 r 作为随机性执行内部 CPA 加密：采样向量 r、e₁ 和标量 e₂（噪声分量），计算密文 (u, v)。
4. 具体地，u = NTT⁻¹(Â^T ◦ NTT(r)) + e₁，v = NTT⁻¹(t̂^T ◦ NTT(r)) + e₂ + ⌈q/2⌋ · m。
5. 对 u 和 v 分别进行 d_u 位和 d_v 位的压缩，输出密文 c = (Compress(u), Compress(v))。
6. 返回 (K, c)。

压缩操作 Compress_d(x) = ⌊(2^d / q) · x⌉ mod 2^d 是一种有损量化：它将 Z_q 中的元素映射到 d 位整数空间，在丢弃低位信息的同时大幅缩减密文体积。解压操作 Decompress_d(x) = ⌊(q / 2^d) · x⌉ 则执行反向映射，但无法完全恢复原值——产生的量化噪声需要被解密过程中的纠错余量所吸收。

Decaps（解封装）

解封装算法 ML-KEM.Decaps(dk, c) 的执行过程如下：

1. 对密文 c 进行解压，恢复近似的 u’ 和 v’。
2. 计算 m’ = Compress_1(v’ - NTT⁻¹(ŝ^T ◦ NTT(u’)))。这一步的本质是：v’ 中包含 t^T · r + e₂ + ⌈q/2⌋ · m 的近似值，而 s^T · u’ 近似于 s^T · A^T · r + s^T · e₁ = t^T · r - e^T · r + s^T · e₁，两者相减后噪声项被大幅抵消，⌈q/2⌋ · m 的信号被保留——只要总噪声不超过 ⌊q/4⌋，1 位压缩即可正确恢复 m 的每一个系数。
3. 利用恢复出的 m’ 重新执行封装过程（重新加密），得到密文 c’。
4. 若 c’ = c，则输出 K = G(m’ ‖ H(ek))；否则输出 K’ = J(z ‖ c)（隐式拒绝，详见第四节）。

解密正确性的核心在于噪声预算（Noise Budget）：所有噪声分量（秘密-误差交叉项 e^T · r、s^T · e₁、e₂、以及压缩/解压引入的量化误差）的叠加绝对值必须小于 ⌊q/4⌋ ≈ 832。ML-KEM 的参数选择确保了解密失败概率极低——ML-KEM-768 的失败概率约为 2^(-164)，远低于安全性所需的上界。

三、ML-KEM 的核心运算

基于 NTT 的多项式乘法

ML-KEM 中最频繁且计算量最大的操作是 R_q 中的多项式乘法。朴素的多项式乘法需要 O(n^2) 次系数乘法，而数论变换（Number Theoretic Transform, NTT）将其降至 O(n log n)。

NTT 是离散傅里叶变换（DFT）在有限域 Z_q 上的类比。它利用了 ML-KEM 参数中一个精心选择的性质：q = 3329 = 13 · 256 + 1，使得 Z_q 中存在 256 阶本原单位根。这意味着多项式环 R_q = Z_q[x]/(x^256 + 1) 可以通过 NTT 完全分裂为 128 个形如 Z_q[x]/(x^2 - ζ^(2i+1)) 的二次因子的直积。

在实现中，ML-KEM 的 NTT 不是将多项式变换为 256 个点值，而是变换为 128 对系数——每对系数对应一个二次因子 Z_q[x]/(x^2 - ζ^(2i+1)) 中的元素。NTT 域中的”逐点乘法”实际上是 128 次二次多项式的模乘（每次涉及 4 次系数乘法和 2 次加法）。这种设计避免了需要 512 阶单位根（q - 1 = 3328 = 2^6 · 52 并不含 512 的因子），同时仍然提供了优异的运算效率。

以下是简化的 NTT 正变换和基于 NTT 的多项式乘法的 Python 实现：

# 简化的 NTT 实现（用于 ML-KEM / Kyber 的多项式乘法）
# q = 3329, n = 256, 使用 Montgomery 风格的蝶形运算

Q = 3329
N = 256

# 预计算的 NTT 旋转因子（zetas），ζ = 17 是 Z_q 中的 256 阶本原单位根
ZETAS = [1]
zeta = 17
for i in range(1, 128):
    ZETAS.append(ZETAS[-1] * zeta % Q)

def ntt(f):
    """将多项式 f（长度 256 的系数列表）变换到 NTT 域。"""
    a = list(f)
    k = 1
    length = 128
    while length >= 2:
        start = 0
        while start < N:
            z = ZETAS[k]
            k += 1
            for j in range(start, start + length):
                t = z * a[j + length] % Q
                a[j + length] = (a[j] - t) % Q
                a[j] = (a[j] + t) % Q
            start += 2 * length
        length //= 2
    return a

def inv_ntt(f):
    """将 NTT 域表示的多项式变换回系数域。"""
    a = list(f)
    k = 127
    length = 2
    while length <= 128:
        start = 0
        while start < N:
            z = ZETAS[k]
            k -= 1
            for j in range(start, start + length):
                t = a[j]
                a[j] = (t + a[j + length]) % Q
                a[j + length] = (z * (a[j + length] - t)) % Q
            start += 2 * length
        length *= 2
    inv_n = pow(128, Q - 2, Q)  # 128 的模逆元
    return [(x * inv_n) % Q for x in a]

def basemul(a0, a1, b0, b1, zeta_power):
    """NTT 域中一对系数的基乘法（对应 Z_q[x]/(x^2 - ζ) 中的乘法）。"""
    c0 = (a0 * b0 + a1 * b1 * zeta_power) % Q
    c1 = (a0 * b1 + a1 * b0) % Q
    return c0, c1

def poly_mul_ntt(f, g):
    """利用 NTT 计算两个多项式在 R_q = Z_q[x]/(x^256+1) 中的乘积。"""
    f_hat = ntt(f)
    g_hat = ntt(g)
    h_hat = [0] * N
    for i in range(64):
        z = ZETAS[64 + i]
        # 偶数组
        h_hat[4*i], h_hat[4*i+1] = basemul(
            f_hat[4*i], f_hat[4*i+1],
            g_hat[4*i], g_hat[4*i+1], z)
        # 奇数组
        h_hat[4*i+2], h_hat[4*i+3] = basemul(
            f_hat[4*i+2], f_hat[4*i+3],
            g_hat[4*i+2], g_hat[4*i+3], Q - z)
    return inv_ntt(h_hat)

压缩与解压

压缩操作将 Z_q 中的系数量化到较少位数，是 ML-KEM 控制密文尺寸的核心手段。对于 d 位压缩，Compress_d(x) = ⌊(2^d / q) · x + 1/2⌋ mod 2^d，解压 Decompress_d(y) = ⌊(q / 2^d) · y + 1/2⌋。量化引入的最大误差不超过 ⌈q / 2^(d+1)⌉。对于 ML-KEM-768 中 d_u = 10 的设置，u 向量的每个系数的量化误差上界为 ⌈3329 / 2048⌉ = 2，这一精度在噪声预算中是可以承受的。

噪声采样

ML-KEM 使用中心二项分布（Centered Binomial Distribution, CBD）而非离散高斯分布来采样噪声。CBD_η 的定义为：采样 2η 个独立均匀比特 (a_1, …, a_η, b_1, …, b_η)，输出 Σa_i - Σb_i。CBD 的输出范围为 [-η, η]，其方差为 η/2。选择 CBD 而非高斯分布的关键理由是：CBD 的采样仅涉及随机比特的异或和计数操作，天然免疫时序侧信道——不存在依赖于采样值的条件分支或浮点运算。

四、Fujisaki-Okamoto 变换在 ML-KEM 中的应用

从 CPA 安全到 CCA 安全

ML-KEM 的内核是一个 IND-CPA 安全的公钥加密方案（PKE）：攻击者无法区分同一公钥下两条不同消息的密文。然而，在实际应用中，我们需要更强的 IND-CCA2 安全性（Indistinguishability under Adaptive Chosen-Ciphertext Attack）——攻击者即使拥有解密预言机，也无法获取关于目标密文的任何信息。CPA 安全到 CCA 安全之间的鸿沟是巨大的：CPA 安全的方案可能在面对密文篡改时完全崩溃。

Fujisaki-Okamoto（FO）变换是弥合这一鸿沟的经典工具。其核心思想优雅而简洁：在封装时，使用消息 m 的哈希值作为加密随机性——这使得加密过程变为确定性的；在解封装时，先解密恢复 m’，再用 m’ 重新加密，将得到的密文与收到的密文进行比对。若一致，说明密文确实由合法封装过程产生，输出正确的共享密钥；若不一致，则密文遭到了篡改。

隐式拒绝

ML-KEM 中的 FO 变换采用了隐式拒绝（Implicit Rejection）策略：当重新加密校验失败时，算法不会返回错误标志，而是输出一个伪随机的密钥 K’ = J(z ‖ c)，其中 z 是解密密钥中保存的随机值，c 是收到的密文。攻击者无法区分 K’ 与合法密钥——因为 J 是一个伪随机函数（基于 SHAKE-256），且 z 对攻击者完全保密。

隐式拒绝的安全意义是深远的。显式拒绝（返回 ⊥）会向攻击者泄漏一比特信息——“你提交的密文无效”——在某些场景下，攻击者可以利用这一比特的反馈逐步提取秘密密钥（类似于 Bleichenbacher 对 RSA PKCS#1 v1.5 的著名攻击）。隐式拒绝从根本上封堵了这条信息泄漏通道：无论攻击者提交什么密文，他总是会得到一个看起来合法的密钥，但这个密钥除了对该特定密文以外不包含任何有用信息。

安全性归约

经过 FO 变换后，ML-KEM 的 IND-CCA2 安全性可以紧致地归约到底层 CPA-PKE 的 IND-CPA 安全性，以及所使用的哈希函数 G、H、J 在随机预言机模型（Random Oracle Model, ROM）中的安全性。具体来说，任何对 ML-KEM 的 CCA 攻击者 A，都可以被转化为一个对底层 CPA-PKE 的 CPA 攻击者 B，使得 B 的优势与 A 的优势仅相差可忽略的量。在量子随机预言机模型（QROM）中，Kuchta 等人的工作进一步证明了类似的紧致归约，确保了 ML-KEM 在量子攻击者面前的安全性。

五、ML-DSA 算法结构

ML-DSA 是一个数字签名方案，其安全性同样基于 MLWE 问题，但采用了与 ML-KEM 截然不同的构造范式——Fiat-Shamir with Aborts。

参数集

ML-DSA 定义了三个参数集：

其中 q = 8380417 = 2^23 - 2^13 + 1，多项式次数 n = 256。这个模数的选择同样是精心设计的：q ≡ 1 (mod 512)，使得 Z_q 中存在 512 阶本原单位根，NTT 可以将 R_q 完全分裂为 256 个一次因子的直积（与 ML-KEM 的 128 个二次因子不同）。

KeyGen（密钥生成）

1. 采样随机种子 ξ（32 字节）。
2. 从 ξ 确定性地生成矩阵 Â ∈ R_q^{k×l}（NTT 域）。
3. 采样秘密向量 s₁ ∈ R_q^l 和 s₂ ∈ R_q^k，各系数均匀分布在 [-η, η]。
4. 计算 t = As₁ + s₂。
5. 将 t 分解为高位 t₁ 和低位 t₀：t = t₁ · 2^d + t₀。
6. 公钥 pk = (ρ, t₁)，秘密密钥 sk = (ρ, K, tr, s₁, s₂, t₀)，其中 tr = H(pk)。

Sign（签名）

签名算法是 ML-DSA 最复杂的部分，其核心是一个拒绝采样（Rejection Sampling）循环：

1. 计算消息哈希 μ = H(tr ‖ M)。
2. 初始化计数器 κ = 0。
3. 循环开始：采样掩码向量 y ∈ R_q^l，每个系数均匀分布在 [-γ₁ + 1, γ₁]。
4. 计算 w = Ay。
5. 将 w 的每个系数分解为高位 w₁ 和低位 w₀。
6. 计算挑战哈希 c̃ = H(μ ‖ w₁)，然后从 c̃ 确定性地导出挑战多项式 c ∈ R_q（恰好有 τ 个系数为 ±1，其余为零）。
7. 计算 z = y + c · s₁。
8. 拒绝检查：若 z 的任一系数的绝对值 ≥ γ₁ - β，或者 w - c · s₂ 的低位部分的任一系数绝对值 ≥ γ₂ - β，则递增 κ，回到步骤 3 重新采样。
9. 计算提示向量 h（Hint Vector），用于帮助验证者在不知道 s₂ 的情况下从 Az - ct 的高位恢复 w₁。
10. 若 h 中非零元素个数超过上界 ω，同样拒绝并重试。
11. 输出签名 σ = (c̃, z, h)。

Verify（验证）

1. 从公钥恢复 Â 和 t₁。
2. 计算 μ = H(tr ‖ M)。
3. 从 c̃ 导出挑战多项式 c。
4. 计算 w’ = Az - c · t₁ · 2^d。
5. 利用提示向量 h 从 w’ 恢复 w₁’。
6. 验证 c̃ = H(μ ‖ w₁’) 且 z 的系数均满足范围约束。

验证过程的计算量远小于签名——不需要拒绝采样循环，只需一次矩阵-向量乘法和一次哈希比对。

六、ML-DSA 的 Fiat-Shamir with Aborts

为什么需要拒绝采样

ML-DSA 的签名过程中，z = y + c · s₁ 这一步会在 z 中泄漏关于秘密 s₁ 的信息：如果攻击者收集足够多的签名 (c_i, z_i)，就可以通过统计分析估计出 c_i · s₁ 的均值，进而恢复 s₁。拒绝采样（Rejection Sampling）正是为了消除这一信息泄漏：只有当 z 的分布”看起来”与 y 的原始分布（在 [-γ₁ + 1, γ₁] 上的均匀分布）足够接近时，签名才被接受并输出。具体地，如果 z 的某个系数因 c · s₁ 的叠加而偏移到了 [-γ₁ + 1, γ₁] 范围之外或接近边界，就触发拒绝。

从概率论的角度看，这一过程可以用 Lyubashevsky 的离散拒绝采样引理来严格分析：经过拒绝采样后，输出的 z 的统计分布与不依赖于 s₁ 的参考分布之间的统计距离是可忽略的。代价是签名需要平均重复若干次才能成功——对于 ML-DSA-65，平均迭代次数约为 5.1 次。

挑战生成

挑战多项式 c 是 Fiat-Shamir 范式的核心组件：它将交互式证明中验证者的随机挑战替换为对消息和承诺（w₁）的哈希值。c 被约束为恰好有 τ 个非零系数（均为 ±1），这一稀疏结构确保了 c · s₁ 的系数幅度可控——每个系数的绝对值至多为 τ · η = β。这一上界 β 直接进入拒绝采样的判定条件，也是安全参数设计的关键约束。

提示向量

提示向量 h 是 ML-DSA 中一个精巧的工程设计。在验证过程中，验证者需要恢复签名时 w = Ay 的高位 w₁，但验证者只能计算 Az - ct = A(y + cs₁) - ct = Ay + c(As₁ - t) = Ay - cs₂，即 w - cs₂。由于 cs₂ 的低位分量可能导致 w - cs₂ 与 w 的高位函数产生不同的进位（类似十进制中 49 + 2 = 51 改变了十位），提示向量 h 精确记录了哪些系数位置发生了这种进位，使验证者能正确恢复 w₁。h 是一个二元向量（仅含 0 和 1），其非零元素个数由签名参数 ω 上界——这一约束限制了签名尺寸，同时也是安全性分析的一部分。

七、安全性分析

Core-SVP 困难性

ML-KEM 和 ML-DSA 的安全性最终归约到 MLWE 问题的困难性，而 MLWE 的困难性又与格上近似 SVP 的困难性紧密相关。密码学界通常使用 core-SVP（或称 BKZ cost model）来估计格攻击的计算成本：假设攻击者使用 BKZ-β 算法（目前最优的格基约简算法族）来求解 SVP，则所需的经典计算量约为 2^{0.292β}，量子计算量约为 2^{0.265β}（使用 Grover 加速的格筛法）。

对于 ML-KEM-768，对应的 MLWE 实例的格维度为 d = k · n = 768，BKZ 块维度 β 约为 630 至 660（取决于具体的攻击策略和估计模型），对应的经典 core-SVP 安全级别约为 183 至 193 比特，量子 core-SVP 安全级别约为 166 至 175 比特。这些数值高于 NIST Level 3 所要求的 AES-192 等价安全级别（143 比特量子安全性）。

格估计器

NIST 后量子密码标准化过程中广泛使用了格估计器（Lattice Estimator，由 Martin Albrecht 等人开发维护的开源工具）来评估 MLWE/MLWR 参数的具体安全强度。格估计器综合考虑了所有已知的格攻击策略——包括原始攻击（Primal Attack）、对偶攻击（Dual Attack）、混合攻击（Hybrid Attack）以及针对环/模结构的特殊攻击——并输出每种攻击的预估计算成本。值得注意的是，2023 年 Ducas 和 van Woerden 对对偶攻击中”几何级数假设”（Geometric Series Assumption）的修正，使得部分旧的安全估计需要重新评估，但 ML-KEM 和 ML-DSA 的参数选择留有足够的安全余量，修正后的估计仍然满足目标安全级别。

侧信道考量

格基方案的侧信道安全性是工程部署中的重要考量。ML-KEM 的解封装过程涉及秘密密钥 ŝ 与密文的乘法运算，若实现不当，可能通过功耗分析（Power Analysis）或电磁辐射分析泄漏密钥信息。ML-DSA 的签名过程中，拒绝采样的循环次数本身就是一个潜在的时序侧信道——如果攻击者能测量签名耗时，就可能推断出与秘密相关的信息。FIPS 203 和 FIPS 204 标准文本明确要求所有实现必须使用常量时间（Constant-Time）操作，禁止依赖于秘密数据的条件分支和内存访问模式。此外，ML-KEM 的隐式拒绝机制也要求解封装的两条执行路径（校验成功和校验失败）在时间和功耗特征上不可区分。

八、实现优化

NTT 实现

NTT 是 ML-KEM 和 ML-DSA 中计算占比最高的操作（在 ML-KEM 的封装和解封装中占总计算量的 60% 至 70%）。高效实现的关键在于：

Barrett/Montgomery 模约简。 Z_q 中的乘法后需要对 q 取模，整数除法是昂贵的操作。Barrett 约简通过预计算 q 的倒数的定点近似值，将除法转换为乘法和移位；Montgomery 约简则通过选择一个 2 的幂次 R（通常 R = 2^16），将模运算转化为关于 R 的运算，避免了除法。ML-KEM 的参考实现中大量使用 Montgomery 约简，因为 NTT 蝶形运算中的乘法天然适配 Montgomery 形式。

蝶形运算的排列。 Cooley-Tukey 型（用于正向 NTT）和 Gentleman-Sande 型（用于逆向 NTT）蝶形运算的选择影响数据访问模式和旋转因子的预计算方式。ML-KEM 参考实现采用 Cooley-Tukey 正向变换和 Gentleman-Sande 逆向变换的组合，以确保输入和输出都是自然顺序（避免位逆序排列的开销）。

AVX2/NEON 向量化加速

在 x86-64 平台上，AVX2 指令集提供 256 位宽的 SIMD 寄存器，可以同时处理 16 个 16 位整数。ML-KEM 的系数宽度（12 位用于未压缩值，小于 16 位）恰好可以打包到 16 位通道中。Peter Schwabe 和 Roberto Avanzi 等人的 AVX2 优化实现展示了惊人的性能：ML-KEM-768 的完整封装操作（KeyGen + Encaps）在现代 x86-64 处理器上仅需约 20 万时钟周期，解封装约 22 万时钟周期——与 X25519 椭圆曲线 Diffie-Hellman 在同一数量级。

在 ARM 平台上，NEON 指令集提供 128 位宽的 SIMD 寄存器，可同时处理 8 个 16 位整数。虽然向量宽度是 AVX2 的一半，但 ARM 处理器通常有更多的 NEON 流水线单元。在 Apple M 系列和 AWS Graviton 等高端 ARM 处理器上，ML-KEM-768 的性能表现同样优异。

常量时间要求

常量时间实现的核心原则是：所有依赖于秘密数据的操作必须使用位运算（AND、OR、XOR、移位）而非条件分支来实现。具体到 ML-KEM 和 ML-DSA 的实现中，以下操作需要特别注意：

• 比较操作（如 FO 变换中的密文比对）必须使用逐字节异或后求或的方式，而非 memcmp（后者可能在发现第一个不同字节时提前返回）。
• CBD 采样中的求和操作应使用查表或 popcount 指令，避免循环计数。
• ML-DSA 签名中的拒绝采样条件判断必须确保无论是否拒绝，执行路径的时间特征一致——通常通过”先计算两种结果，再用常量时间选择掩码选取”的模式实现。

内存占用

对于资源受限的嵌入式平台（如 ARM Cortex-M4），内存占用是关键约束。ML-KEM-768 的参考实现的栈空间需求约为 2.5 KB（不含公钥/密钥存储），这一数值对于主流微控制器来说是可接受的。优化策略包括：在线生成矩阵 Â 的各行（逐行流式生成，避免同时存储整个矩阵）；将 NTT 变换与采样操作交错进行以复用缓冲区；使用压缩格式存储秘密密钥。pqm4 项目（ARM Cortex-M4 上的后量子密码库）是这一领域的标杆实现。

ML-KEM 与 ML-DSA 参数速查表

在进入部署讨论之前，以下速查表汇总了 ML-KEM 三个参数集和 ML-DSA 三个参数集的密钥尺寸、密文/签名尺寸与性能数据（性能数据基于 Intel Core i7-13700K + AVX2 优化实现）：

ML-KEM（FIPS 203）——密钥封装机制

ML-DSA（FIPS 204）——数字签名算法

与经典方案的尺寸对比

审视这张速查表，一个结论是清晰的：从经典密码到后量子密码，密钥和签名尺寸的膨胀是真实的——ML-KEM-768 的公钥是 X25519 的 37 倍，ML-DSA-65 的签名是 Ed25519 的 51 倍——但对于绝大多数现代网络应用而言，这个增幅完全在可承受范围内。一个 TLS 握手多传输 1 到 2 KB 的数据，在宽带网络上几乎无感。然而，当你把视线转向资源受限的物联网设备——比如一个只有 16 KB RAM、通过 LoRa 以 0.3 kbps 速率通信的传感器节点——这些”可以忽略”的额外字节就成了不可逾越的障碍。后量子迁移的真正挑战，不在数据中心里那些有充裕带宽和算力的服务器上，而在网络边缘那些最脆弱、最难升级、却往往部署周期最长的设备上。

九、部署现状

浏览器与 CDN 的混合 KEM

2023 年 8 月，Google Chrome 浏览器在 TLS 1.3 握手中实验性地启用了 X25519Kyber768Draft 混合密钥交换——将传统的 X25519 椭圆曲线 Diffie-Hellman 与 ML-KEM-768 组合使用。混合方案的设计理念是”双保险”：即使格基方案在未来被发现有未预见的弱点，X25519 仍然提供传统安全性；反之，即使大规模量子计算机问世，ML-KEM-768 仍然提供后量子安全性。Cloudflare 同步在其全球边缘网络上部署了对该混合方案的支持，使得数以亿计的 TLS 连接开始享受后量子保护。2024 年标准正式发布后，Chrome 已过渡到基于最终标准的 X25519MLKEM768 组合。

实际测试数据显示，混合 KEM 对 TLS 握手延迟的影响微乎其微。ML-KEM-768 的公钥（1184 字节）和密文（1088 字节）虽然比 X25519 的 32 字节大得多，但在现代网络环境下，这些额外字节几乎不增加可感知的延迟。Google 的大规模 A/B 测试表明，启用混合 KEM 后，TLS 握手的 P50 延迟增加不到 0.5 毫秒。

云服务集成

AWS Key Management Service（KMS）于 2024 年宣布支持后量子 TLS，使得客户与 KMS 之间的通信可以受到后量子密钥交换的保护。Signal 通信协议在 2023 年引入了 PQXDH（Post-Quantum Extended Diffie-Hellman）密钥协商机制，将 ML-KEM-768 与 X25519 组合，为端到端加密通信提供后量子安全的前向保密性。Apple 的 iMessage 在 2024 年的 PQ3 协议升级中同样采用了类似的混合方案。

开源生态

Open Quantum Safe（OQS）项目维护的 liboqs 库提供了 ML-KEM 和 ML-DSA 所有参数集的 C 语言参考实现和优化实现，并通过 oqs-provider 集成到 OpenSSL 3.x 中，使得现有基于 OpenSSL 的应用程序可以通过简单的配置变更启用后量子算法。此外，BoringSSL（Google 维护的 OpenSSL 分支）、AWS-LC（Amazon 维护的密码库）和 wolfSSL 等主流密码库均已原生支持 ML-KEM。

在编程语言层面，Go 1.23 在其标准库 crypto/mlkem 中加入了 ML-KEM 的实现；Rust 生态中的 pqcrypto 和 ml-kem crate 提供了高质量的实现；Java 的 Bouncy Castle 库同样在 2024 年加入了 FIPS 203/204 支持。

性能基准

在 Intel Core i7-13700K 处理器上（AVX2 优化实现），ML-KEM-768 的典型性能数据如下：

作为对比，RSA-2048 的密钥生成需要数百万个时钟周期，ECDH P-256 的密钥交换约需 300,000 个时钟周期。ML-KEM 在计算性能上已经具备明显优势，其主要代价是密钥和密文尺寸的增加——但如前文所述，在现代网络环境中，这一代价是完全可以承受的。

ML-DSA-65 的签名性能因拒绝采样的随机性而存在波动，平均值约为 800,000 时钟周期（约 170 μs），验证约为 300,000 时钟周期（约 62 μs）。签名尺寸（3293 字节）虽然远大于 Ed25519（64 字节），但在绝大多数应用场景中不构成瓶颈。

后量子密码学的工程部署正在以前所未有的速度推进。从浏览器到消息应用，从云服务到嵌入式设备，ML-KEM 和 ML-DSA 正在逐步融入整个数字基础设施。格基密码不仅在理论上提供了对量子计算威胁的抵抗能力，更在实践中证明了其效率和可部署性——这正是 NIST 在长达八年的评估过程中所追求的目标。

笔者认为，ML-KEM（Kyber）在 NIST 竞赛中的胜出，揭示的关于工程政治学的信息不亚于关于密码学质量的信息。在决赛圈的候选方案中，NTRU 拥有更长的学术血统（1996 年提出），SABER 在某些指标上效率更高——但 Kyber 胜在它是最保守、最被充分理解的方案。它的模格结构介于标准 LWE 和环 LWE 之间，既不过度激进也不过度保守；它的参数选择留有充裕的安全余量；它的参考实现简洁、审计友好、几乎没有边界情况。这一结果对密码学标准化有深远的启示：在标准化竞赛中，“无聊”是一种优势——评审委员会更倾向于选择一个他们完全理解的方案，而非一个他们仍在研究的方案。

一个经常被忽视的观点是，后量子参数尺寸的膨胀将制造一道新的数字鸿沟。ML-KEM-768 的公钥约 1184 字节，在 TLS 握手中几乎无感——但将视线转向资源受限的物联网世界：一个只有 64KB RAM、通过 LoRa 以 0.3 kbps 速率通信的传感器节点，仅传输一次公钥就需要约 30 秒。更糟糕的是，ML-DSA-65 的签名（3293 字节）是 Ed25519（64 字节）的 51 倍，对于需要频繁验证固件签名的嵌入式设备而言，这不是渐进式的增长，而是质变。后量子迁移的真正挑战不在数据中心，而在网络边缘那些最脆弱、最难升级、部署周期却最长的设备上——这些设备很可能在量子计算机问世时仍在运行今天的经典密码。

从工程实践来看，当前普遍采用的”混合模式”（经典 + 后量子）部署策略，表面上是一种安全的过渡措施，但它实际上暴露了一个深层的认识论困境：我们对任何单一后量子假设都没有足够的信心来独立押注。格基假设（MLWE）虽然被研究了近二十年，但与 RSA 的因子分解假设或椭圆曲线的 ECDLP 假设相比，它的学术审查历史仍然年轻。混合模式的存在本身就是密码学社区对自身知识边界的一种诚实承认——这在密码学史上是罕见的。更实际地说，混合模式还揭示了一个工程权衡：它将 TLS ClientHello 的密钥份额从 32 字节膨胀到约 1250 字节，可能导致某些中间设备（防火墙、负载均衡器）因缓冲区溢出而断开连接。混合模式不是免费午餐，它是我们为认识论上的审慎所支付的工程代价。

密码学百科系列 · 第 58 篇

← 上一篇：后量子密码总览 | 系列目录 | 下一篇：哈希基签名 →