知识库 / 后量子密码学：从量子威胁到 NIST 标准化的新密码体系

后量子密码学：从量子威胁到 NIST 标准化的新密码体系

密码学概念 · 2026-06-10

概述

1994 年，贝尔实验室的 Peter Shor 发表了一篇论文，从根本上改变了密码学的未来走向。他证明了一旦大规模容错量子计算机问世，当前互联网安全所依赖的 RSA、Diffie-Hellman 和椭圆曲线密码学（ECC）将被高效破解——不是被更快地破解，而是被多项式时间破解。

这意味着什么？一个 2048 位的 RSA 密钥，经典计算机需要数十亿年才能分解，而一台足够强大的量子计算机只需数小时。更令人不安的是，攻击者可以现在存储加密通信，等量子计算机成熟后再解密——"先收集、后解密"（Harvest Now, Decrypt Later）策略已经不是一个理论假设。

后量子密码学（Post-Quantum Cryptography, PQC）正是为应对这一威胁而生。与量子密钥分发（QKD）不同，PQC 不需要量子硬件，它基于经典计算机上可运行、但量子计算机也无法高效求解的数学问题。2024 年 8 月，美国国家标准与技术研究院（NIST）正式发布了首批三项 PQC 标准，标志着密码学正式进入后量子时代。

量子计算对密码学的威胁

Shor 算法的原理

Shor 算法的核心是将整数分解和离散对数问题转化为量子傅里叶变换可求解的周期查找问题。

CODE
经典计算复杂度 vs 量子计算复杂度：

┌─────────────────────┬──────────────────────┬─────────────────────┐
│ 问题                 │ 经典最优算法          │ Shor 量子算法        │
├─────────────────────┼──────────────────────┼─────────────────────┤
│ n-bit 整数分解       │ O(exp(n^(1/3)))      │ O(n³)               │
│ n-bit 离散对数       │ O(exp(n^(1/3)))      │ O(n³)               │
│ 椭圆曲线离散对数      │ O(2^(n/2))           │ O(n³)               │
└─────────────────────┴──────────────────────┴─────────────────────┘

关键洞察：Shor 算法之所以能工作，是因为它能利用量子叠加态同时评估指数级数量的候选解，再通过量子干涉放大正确答案。这不是"更快的暴力搜索"，而是一种结构性优势——它利用了 RSA/ECC 底层数学问题的代数周期性。

受影响的算法范围

量子计算对密码学的影响是不对称的：

  • 致命威胁（Shor 算法可解）：RSA、Diffie-Hellman、DSA、ECDSA、EdDSA、ECDH
  • 显著威胁（Grover 算法加速）：AES、SHA-256 等对称算法——安全强度减半（AES-256 降至 128 位安全性）
  • 基本不受影响：一次性密码本（OTP）、信息论安全的方案
Grover 算法对对称算法的影响可以通过加倍密钥长度来应对——从 AES-128 升级到 AES-256 即可。但公钥密码面临的威胁是根本性的：不是"需要更长的密钥"，而是"整个数学框架不再安全"。

"先收集、后解密"的现实威胁

这不是未来的问题。NSA 在 2015 年即宣布计划迁移到抗量子算法。欧盟 ENISA 将 PQC 迁移列为最高优先级。问题的紧迫性在于：

  • 加密数据的保质期：政府机密数据需要保密 50 年以上，医疗数据需要终身保密
  • 量子计算机的时间线：虽然大规模容错量子计算机尚未出现，但进展在加速
  • 迁移周期：从标准发布到全面部署通常需要 10-15 年（参考 RSA 到 ECC 的迁移）

后量子密码学的四大技术路线

NIST 从 2016 年开始了 PQC 标准化竞赛，共收到 69 个初始提案，经过多轮筛选，最终收敛到四大数学基础不同的技术路线。这种多样性是有意为之——如果某一天某个路线被攻破，其他路线仍能提供保护。

CODE
┌─────────────────────────────────┐
                    │     后量子密码学技术路线           │
                    └───────────────┬─────────────────┘
           ┌────────────┬──────────┼──────────┬─────────────┐
           ▼            ▼          ▼          ▼             
    ┌────────────┐ ┌─────────┐ ┌────────┐ ┌──────────┐
    │  格密码     │ │哈希签名  │ │编码密码 │ │多变量密码  │
    │ Lattice    │ │Hash-based│ │Code-based│ │Multivariate│
    └────────────┘ └─────────┘ └────────┘ └──────────┘
         │              │          │           │
    NIST 首选      最保守的方案  密钥较大     签名短
    数学基础最强    安全性证明最久 解码困难     公钥大

一、基于格的密码学（Lattice-based Cryptography）

格密码是当前 PQC 领域最活跃、最成熟的方向，NIST 首批三个标准中的两个（ML-KEM 和 ML-DSA）都基于格密码。

#### 格的基本定义

格（Lattice） 是 n 维欧几里得空间中离散点的集合，可以理解为"高维空间中无限延伸的网格"。

形式上，给定 n 个线性无关的向量 b₁, b₂, ..., bₙ ∈ ℝⁿ，由它们生成的格为：

CODE
L = { a₁b₁ + a₂b₂ + ... + aₙbₙ | a₁, a₂, ..., aₙ ∈ ℤ }

这些向量构成格的一组基（basis）。同一个格可以有无数组不同的基——好基（短向量、近似正交）和坏基（长向量、高度倾斜）之间的区别，正是格密码安全性的核心。

#### 两个核心困难问题

最短向量问题（SVP, Shortest Vector Problem）：给定一个格，找到其中最短的非零向量。

最近向量问题（CVP, Closest Vector Problem）：给定一个格和一个目标点，找到格中离目标点最近的点。

对于随机格，这两个问题在经典和量子计算模型下都被认为是困难的——没有已知的量子算法能比经典算法提供超多项式加速。

#### LWE 问题：从格到密码的桥梁

直接从 SVP/CVP 构造密码系统效率不高。2005 年，Regev 提出了容错学习问题（Learning With Errors, LWE），为格密码打开了实用化的大门。

LWE 问题的定义：

CODE
给定：
  - 一个随机矩阵 A ∈ Z_q^{m×n}
  - 一个秘密向量 s ∈ Z_q^n
  - 一个小的噪声向量 e ∈ Z_m（从离散高斯分布采样）
  - 公开值 b = As + e (mod q)

问题：从 (A, b) 恢复 s

直觉理解：如果没有噪声 e，这就是一个简单的线性方程组，可以高斯消元求解。但加上小的噪声后，问题变得极其困难——因为噪声的"方向"是随机的，无法通过代数方法消除。

Ring-LWE 是 LWE 在多项式环上的变体，将矩阵乘法替换为多项式乘法，大幅提升了效率（密钥更小、运算更快）。CRYSTALS-Kyber（ML-KEM）和 CRYSTALS-Dilithium（ML-DSA）都基于 Ring-LWE 或其变体 Module-LWE。

#### Module-LWE：安全与效率的平衡

NIST 标准采用的是 Module-LWE，它是 LWE 和 Ring-LWE 的推广。可以理解为：

  • LWE：完全通用的格问题，安全但效率低
  • Ring-LWE：利用代数结构加速，效率高但结构更多（可能有未知攻击面）
  • Module-LWE：介于两者之间，在 Z_q[x]/(x^n+1) 的 k 维模块上操作
CODE
安全性：LWE > Module-LWE > Ring-LWE
效率：  Ring-LWE > Module-LWE > LWE

选择 Module-LWE 是一种审慎的折中——保留足够的代数结构以获得实用效率，同时避免 Ring-LWE 可能存在的特殊攻击。

二、基于哈希的密码学（Hash-based Cryptography）

哈希签名是 PQC 中历史最长、信心最强的方向。

#### Merkle 签名方案（1979）

Ralph Merkle 在 1979 年就提出了基于哈希函数的签名方案，比 RSA 还早。其核心思想极其优雅：

CODE
一次性签名（OTS） → Merkle 树 → 多次签名

   PK（Merkle 根）
      │
    ┌─┴─┐
   H   H          ← 第二层
  ┌┴┐ ┌┴┐
  H H H H        ← 第一层（叶子节点）
  │ │ │ │
 sk₀sk₁sk₂sk₃    ← 一次性私钥
  • 生成 2ⁿ 个一次性密钥对
  • 将公钥作为叶子节点构建 Merkle 树
  • Merkle 根作为主公钥
  • 签名时：使用一个一次性密钥 + 认证路径
  • 验证时：通过认证路径验证到 Merkle 根
#### SPHINCS+ → SLH-DSA（FIPS 205）

原始的 Merkle 签名只能签名有限次。SPHINCS（2015）通过引入超树（Hypertree）结构解决了这个问题——多层 Merkle 树组成的树状结构，每个叶子节点又是一棵子树的根。

SLH-DSA（Stateless Hash-Based Digital Signature Algorithm） 是 SPHINCS+ 的标准化版本（FIPS 205），其核心特征：

  • 无状态：不需要在签名后更新状态（对比 XMSS/LSS 等状态化方案）
  • 安全性仅依赖哈希函数：如果 SHA-256 安全，SLH-DSA 就安全
  • 签名较大：典型的 SLH-DSA-128f 签名约 17 KB
  • 公钥极小：仅 32 字节
为什么还需要哈希签名？ 因为格密码的安全性基于的困难问题尚未被证明等价于最坏情况下的格问题（虽然有归约，但参数选择依赖经验估计）。哈希签名的安全性证明是信息论意义上的——它不依赖任何计算假设，只依赖哈希函数的抗碰撞性。

三、基于编码的密码学（Code-based Cryptography）

#### McEliece 加密方案（1978）

McEliece 方案是 PQC 中最古老的提案——1978 年提出，至今未被攻破（原始参数下）。

核心思想基于一般解码问题（General Decoding Problem）：

CODE
私钥：一个具有高效解码算法的 Goppa 码（结构化码）
公钥： 打乱后的等价码（看起来像随机码）
加密： 将明文编码为码字，故意加入 t 个错误
解密： 用私钥的解码算法纠正错误

为什么安全？ 从随机线性码中解码是 NP-完全问题。攻击者面对的是一个"伪装成随机码"的结构化码，没有私钥就无法识别隐藏的代数结构。

为什么没被广泛采用？ 公钥极大——经典 McEliece 的公钥约 1 MB。这在 TLS 等场景中不实用。

#### HQC（Hamming Quasi-Cyclic）

2025 年 3 月，NIST 将 HQC 选为第五个标准化算法（密钥封装机制），基于编码密码学。HQC 使用准循环码结构大幅减小了公钥尺寸，是 McEliece 的现代演进。

四、基于多变量的密码学（Multivariate-based Cryptography）

#### 核心困难问题

多变量密码基于求解多变量二次多项式方程组（MQ 问题）的困难性：

CODE
给定 m 个 n 变量的二次多项式：
  f₁(x₁, ..., xₙ) = 0
  f₂(x₁, ..., xₙ) = 0
  ...
  fₘ(x₁, ..., xₙ) = 0

求解这个方程组。

MQ 问题在有限域上是 NP-完全的——即使对量子计算机也是如此。

#### 典型方案结构

多变量签名方案通常采用"油醋（Oil and Vinegar）"或"彩虹（Rainbow）"结构：

CODE
公钥：一组多变量二次多项式 P(x) = (p₁(x), ..., pₘ(x))
私钥：一个陷门——两个可逆线性变换 S, T 和一个容易求逆的中心映射 F
  P = T ∘ F ∘ S
签名：给定消息 h，计算 S⁻¹(F⁻¹(T⁻¹(h)))
验证：直接计算 P(签名) == h

Rainbow 方案曾是 NIST PQC 第三轮候选，但在 2022 被 Beullens 攻破——攻击者可以在普通工作站上用约 2 天内恢复私钥。这一事件提醒我们：PQC 的安全评估是一个持续过程。

NIST 首批标准化算法详解

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

ML-KEM（Module-Lattice-based Key Encapsulation Mechanism）基于 CRYSTALS-Kyber，用于密钥交换。

CODE
┌──────────────────────────────────────────────────────────────┐
│ ML-KEM 参数集                                                  │
├──────────────┬──────────┬──────────┬──────────┬───────────────┤
│ 参数集        │ 安全等级  │ 公钥大小  │ 密文大小  │ 共享密钥      │
├──────────────┼──────────┼──────────┼──────────┼───────────────┤
│ ML-KEM-512   │ ≈ AES-128│  800 B   │  768 B   │ 32 B          │
│ ML-KEM-768   │ ≈ AES-192│ 1,184 B  │ 1,088 B  │ 32 B          │
│ ML-KEM-1024  │ ≈ AES-256│ 1,568 B  │ 1,568 B  │ 32 B          │
└──────────────┴──────────┴──────────┴──────────┴───────────────┘

设计哲学：ML-KEM 是一种 KEM（密钥封装机制），不是公钥加密。KEM 的工作方式是：

CODE
发起方（Initiator）              响应方（Responder）
    │                                │
    │  1. keygen() → (pk, sk)       │
    │  2. 发送 pk ──────────────────→│
    │                                │  3. encaps(pk) → (ct, ss₂)
    │  4. decaps(sk, ct) → ss₁     │
    │                                │
    │  ss₁ == ss₂ = 共享密钥         │

相比传统公钥加密，KEM 的接口更简单、更安全——避免了Padding Oracle 等攻击。ML-KEM 使用Fujisaki-Okamoto（FO）变换将一个被动的 CPA 安全方案提升为主动的 CCA 安全方案。

ML-KEM vs ECDH 对比：

CODE
┌──────────────────┬──────────────────┬──────────────────┐
│ 维度              │ ECDH (X25519)    │ ML-KEM-768       │
├──────────────────┼──────────────────┼──────────────────┤
│ 公钥大小          │ 32 字节           │ 1,184 字节       │
│ 密文/封装大小     │ 32 字节           │ 1,088 字节       │
│ 共享密钥          │ 32 字节           │ 32 字节          │
│ 安全假设          │ ECDLP             │ Module-LWE       │
│ 抗量子            │ ❌                │ ✅               │
│ 计算速度          │ 极快（~100μs）    │ 快（~200μs）     │
└──────────────────┴──────────────────┴──────────────────┘

注意：ML-KEM 的公钥和密文确实比 X25519 大很多（约 30-40 倍），但在 TLS 握手的数据量中仍然可接受。

FIPS 204：ML-DSA（数字签名）

ML-DSA（Module-Lattice-based Digital Signature Algorithm）基于 CRYSTALS-Dilithium，是 NIST 标准化的主要后量子签名方案。

CODE
┌──────────────────────────────────────────────────────────────────┐
│ ML-DSA 参数集                                                     │
├──────────────┬──────────┬──────────┬──────────┬──────────────────┤
│ 参数集        │ 安全等级  │ 公钥大小  │ 签名大小  │ 密钥生成时间      │
├──────────────┼──────────┼──────────┼──────────┼──────────────────┤
│ ML-DSA-44    │ ≈ AES-128│ 1,312 B  │ 2,420 B  │ ~0.1 ms          │
│ ML-DSA-65    │ ≈ AES-192│ 1,952 B  │ 3,293 B  │ ~0.2 ms          │
│ ML-DSA-87    │ ≈ AES-256│ 2,592 B  │ 4,595 B  │ ~0.3 ms          │
└──────────────┴──────────┴──────────┴──────────┴──────────────────┘

ML-DSA 的核心设计：

ML-DSA 使用"承诺-挑战-响应"（Commit-Challenge-Response）范式，这是 Schnorr 签名的后量子推广：

CODE
签名者（知道秘密 s）：
  1. 随机选择掩码向量 r
  2. 计算承诺 t = A·r（A 是公钥矩阵）
  3. 计算挑战 c = H(μ ‖ t₁)（μ 是消息，t₁ 是 t 的高位）
  4. 计算响应 z = r + c·s
  5. 使用拒绝采样调整 z 使其不泄露 s 的信息

验证者：
  1. 重新计算 c = H(μ ‖ t₁')
  2. 验证 A·z - c·t ≈ t₁'（检查 z = r + c·s 是否成立）
  3. 验证 z 的范数在合理范围内

拒绝采样（Rejection Sampling） 是 ML-DSA 的关键技术——签名者需要拒绝某些会使签名泄露私钥信息的随机值，这确保了签名的统计分布不依赖私钥。

FIPS 205：SLH-DSA（无状态哈希签名）

SLH-DSA（Stateless Hash-Based Digital Signature Algorithm）基于 SPHINCS+，是 NIST 标准化的"保守备选"。

CODE
┌──────────────────────────────────────────────────────────────────┐
│ SLH-DSA 参数集                                                    │
├────────────────┬──────────┬──────────┬──────────┬────────────────┤
│ 参数集          │ 安全等级  │ 公钥大小  │ 签名大小  │ 签名时间        │
├────────────────┼──────────┼──────────┼──────────┼────────────────┤
│ SLH-DSA-SHA2-128f│≈AES-128│  32 B    │ 17,088 B │ ~10 ms         │
│ SLH-DSA-SHA2-128s│≈AES-128│  32 B    │  7,856 B │ ~50 ms         │
│ SLH-DSA-SHA2-192f│≈AES-192│  48 B    │ 35,664 B │ ~20 ms         │
│ SLH-DSA-SHA2-256f│≈AES-256│  64 B    │ 49,856 B │ ~40 ms         │
└────────────────┴──────────┴──────────┴──────────┴────────────────┘

SLH-DSA 的签名明显比 ML-DSA 大得多，但它的安全性证明最为简洁——仅依赖哈希函数的抗碰撞性。这使它成为"最坏情况下的安全网"：即使所有格问题都被量子算法攻克，SLH-DSA 仍然安全。

算法选择策略：应用场景对比

CODE
┌────────────────────┬──────────────┬──────────────┬──────────────┐
│ 场景                │ 首选算法      │ 备选算法      │ 考虑因素      │
├────────────────────┼──────────────┼──────────────┼──────────────┤
│ TLS 握手密钥交换    │ ML-KEM       │ HQC          │ 延迟、带宽   │
│ TLS 证书签名        │ ML-DSA       │ SLH-DSA      │ 签名大小     │
│ 代码签名            │ ML-DSA       │ SLH-DSA      │ 验证速度     │
│ 固件/嵌入式签名     │ SLH-DSA      │ ML-DSA       │ 公钥大小     │
│ 区块链交易签名      │ ML-DSA       │ 基于格的短签名│ 签名大小     │
│ 长期保密（政府）    │ SLH-DSA      │ ML-DSA       │ 安全余量     │
│ 混合方案            │ ECDH+ML-KEM  │ -            │ 过渡期安全   │
└────────────────────┴──────────────┴──────────────┴──────────────┘

混合方案：过渡期的安全策略

在 PQC 迁移的过渡期，混合（Hybrid） 方案是推荐做法——同时使用经典算法和后量子算法，只要其中一个安全，通信就安全。

CODE
混合密钥交换：

  客户端                                    服务器
    │                                        │
    │── ClientHello + X25519公钥 + ML-KEM公钥 →│
    │                                        │
    │← ServerHello + X25519公钥 + ML-KEM公钥 ─│
    │                                        │
    │  共享密钥 = KDF(ECDH_ss ‖ ML-KEM_ss)   │

Cloudflare 和 Google 已经在生产环境中部署了混合 PQC 连接。X25519 + Kyber-768 的组合已成为事实标准。

为什么需要混合？ 因为 PQC 算法相对较新，可能存在未发现的实现漏洞或侧信道漏洞。混合方案确保即使 PQC 算法出现意外问题，经典算法仍能提供保护。

国密体系的量子威胁与应对

中国密码体系同样面临量子计算威胁。SM2（椭圆曲线）、SM3（哈希）、SM4（对称分组密码）中：

  • SM2：基于椭圆曲线离散对数问题（ECDLP），受 Shor 算法直接威胁
  • SM3：哈希函数，受 Grover 算法影响（安全强度减半），可通过增加输出长度应对
  • SM4：对称加密，受 Grover 算法影响（安全强度减半），SM4 的 128 位密钥在量子场景下约提供 64 位安全性——不够
中国也在积极推进 PQC 研究。2023 年，中国密码学会组织了后量子密码算法的征集和评估工作。在 GM/T 标准体系中，后量子密码的标准化工作正在推进中。

对国密应用的建议：

  • 关注 GM/T 体系中后量子密码标准的进展
  • 在关键系统设计中预留算法迁移能力
  • 考虑 SM2 + PQC 混合方案作为过渡
  • SM4 用户应评估是否需要升级到更长密钥

实施挑战

1. 密钥和签名尺寸增大

PQC 算法的数据尺寸普遍大于经典算法，这对某些场景构成挑战：

CODE
场景：TLS 证书链

RSA-2048 证书：  ~2 KB（签名 ~256 B）
ML-DSA-65 证书：  ~5 KB（签名 ~3.3 KB）
SLH-DSA 证书：    ~100 KB（签名 ~35 KB）

证书链从 ~5 KB 增长到可能 ~300 KB（如果全部使用 SLH-DSA）

2. 计算开销

虽然 PQC 算法的计算速度在快速提升，但某些场景仍有瓶颈：

  • ML-KEM 密钥生成和封装/解封装：与 ECDH 相当
  • ML-DSA 签名/验证：比 ECDSA 慢约 2-5 倍
  • SLH-DSA 签名：比 ECDSA 慢约 10-50 倍

3. 协议兼容性

TLS 1.3 的密码套件协商机制需要扩展以支持 PQC 算法。IETF 已经定义了多个 PQC 密码套件的 TLS 扩展（如 draft-ietf-tls-ml-kem-for-tls13）。

4. 侧信道防护

PQC 算法的实现同样面临侧信道攻击风险。ML-KEM 的 FO 变换需要恒定时间实现，ML-DSA 的拒绝采样也需要小心处理以避免时序泄露。

参考来源

相关实践

← 返回知识库