2024年8月13日，美国商务部批准了三项联邦信息处理标准（FIPS），正式开启了密码学的新纪元。这不是一次普通的标准更新——这三项标准指定了能够抵御量子计算机攻击的密钥建立和数字签名方案。为什么这次更新如此重要？因为当今保护互联网安全的RSA和椭圆曲线密码（ECC），在未来足够强大的量子计算机面前将不堪一击。

一个困扰密码学界的预言

1994年，贝尔实验室的数学家Peter Shor发表了一篇论文，提出了一个能在量子计算机上运行的多项式时间算法，用于分解大整数和计算离散对数。这个算法直接威胁到了当时和现在几乎所有公钥密码系统的安全基础。

RSA的安全性依赖于大整数分解的困难性。给定两个大素数 $p$ 和 $q$，计算它们的乘积 $N = p \cdot q$ 很容易，但从 $N$ 反推 $p$ 和 $q$ 却被认为在经典计算机上极其困难。对于2048位的RSA密钥，使用目前最强大的超级计算机分解需要超过宇宙年龄的时间。然而，Shor算法改变了这个等式——它能在多项式时间内完成分解，将破解时间从"宇宙年龄"缩短到"数小时"。

Shor算法的核心是量子傅里叶变换（QFT）和周期查找。给定要分解的整数 $N$，算法首先选择一个小于 $N$ 的随机整数 $a$，然后构造函数 $f(x) = a^x \mod N$。这个函数具有周期性，其周期 $r$ 与 $N$ 的因子密切相关。量子傅里叶变换能够高效地找到这个周期，进而通过经典计算得到 $N$ 的因子。

破解RSA需要多少量子比特？

这是业界最关心的问题之一，答案取决于我们讨论的是逻辑量子比特还是物理量子比特。

目前的量子计算机使用的都是物理量子比特，它们极易受到环境噪声的干扰，错误率很高。要实现可靠的量子计算，需要将多个物理量子比特组合成一个容错的逻辑量子比特。根据不同的纠错方案，一个逻辑量子比特可能需要1000个甚至更多的物理量子比特来构建。

对于破解RSA-2048，不同研究给出了不同的估计：

  • 2003年Beauregard的论文指出需要 $2n+3$ 个逻辑量子比特，即4099个逻辑量子比特
  • 2021年Gidney和Eker的详细分析表明，使用约2000万个物理量子比特可以在8小时内破解RSA-2048
  • 2025年Google的最新研究将这个数字降低到了约100万个物理量子比特

作为对比，IBM目前最大的量子计算机有超过1000个物理量子比特，但仍无法运行Shor算法来破解任何有意义的密码。量子计算仍处于"含噪声中等规模量子"（NISQ）时代，距离容错量子计算还有相当距离。

然而，一个被称为"先存储后解密"（Harvest Now, Decrypt Later, HNDL）的攻击模式让时间变得紧迫。攻击者可以现在截获并存储加密数据，等待未来量子计算机成熟后再进行解密。对于那些需要长期保密的数据（如国家机密、医疗记录、知识产权），威胁已经存在。

对称密码的命运：Grover算法

Shor算法威胁的是公钥密码，对称密码的情况如何？

Grover算法提供了对无结构搜索问题的二次加速。对于密钥长度为 $n$ 位的对称密码，经典暴力破解需要 $2^n$ 次尝试，而Grover算法将其减少到 $2^{n/2}$ 次。这意味着AES-128的安全性降低到了 $2^{64}$ 级别，AES-256降低到 $2^{128}$ 级别。

好消息是，这个威胁相对容易应对——只需将密钥长度加倍。AES-256在面对量子计算机时仍能提供 $2^{128}$ 的安全边际，足以抵御 foreseeable future 的攻击。因此，NIST明确表示现有对称密码算法（如AES、SHA-2、SHA-3）在量子时代仍然安全，只需确保使用足够的密钥长度。

后量子密码的技术路线图

后量子密码学（Post-Quantum Cryptography, PQC）的目标是设计能在经典计算机上运行、同时能抵御量子计算机攻击的密码算法。根据底层数学问题的不同，PQC算法分为几大类：

基于格的密码学

这是目前最受关注的路线。格是向量空间中点的规则排列，相关困难问题包括最短向量问题（SVP）和最近向量问题（CVP）。

2005年，Oded Regev提出了学习与错误问题（Learning With Errors, LWE），并证明了它到格问题最坏情况的量子归约。这为格密码学提供了坚实的理论基础。给定矩阵 $A$ 和向量 $b = As + e$（其中 $s$ 是秘密向量，$e$ 是小误差向量），LWE问题要求找到 $s$。这个看似简单的问题，当参数选择适当时，被认为即使对量子计算机也是困难的。

LWE的一个变体是模LWE（Module-LWE），它在环结构上工作，可以减小密钥和密文大小，同时保持安全性。NIST选定的两个主要算法——Kyber和Dilithium——都基于Module-LWE。

基于哈希的密码学

哈希函数的抗碰撞性质不依赖于任何数论假设，这使得基于哈希的签名具有最小的安全假设。SPHINCS+采用Merkle树结构，通过组合多个一次性签名（如WOTS）构建可用多次的签名方案。

这类算法的优点是安全性基于哈希函数的基本性质，缺点是签名较大（约8-17KB）且计算较慢。

基于编码的密码学

利用纠错码的解码困难性。McEliece密码系统自1978年提出以来经受了40多年的分析，未被攻破。缺点是公钥非常大（约1MB）。HQC是另一个基于编码的KEM方案，已于2025年被NIST选为备选标准。

基于多变量的密码学

基于求解多变量多项式方程组的困难性。Rainbow算法曾是这一方向的代表，但在2022年被法国研究者攻破，凸显了密码分析的持续威胁。

基于同源的密码学

利用椭圆曲线同源图的性质。SIKE算法曾被视为有前景的候选，但在2022年被经典算法在几小时内攻破，说明了密码分析的不可预测性。

mindmap
  root((后量子密码学))
    基于格 Lattice-based
      ML-KEM (Kyber)
      ML-DSA (Dilithium)
      Falcon
      安全性: LWE/Module-LWE问题
    基于哈希 Hash-based
      SLH-DSA (SPHINCS+)
      XMSS/LMS
      安全性: 哈希函数抗碰撞性
    基于编码 Code-based
      McEliece
      HQC
      安全性: 纠错码解码问题
    基于多变量 Multivariate
      已被攻破: Rainbow
      安全性: 多变量方程求解
    基于同源 Isogeny-based
      已被攻破: SIKE
      安全性: 椭圆曲线同源

NIST标准详解：三个算法的故事

经过三轮、历时八年的筛选，NIST于2024年8月发布了三个正式标准：

FIPS 203：ML-KEM（源自CRYSTALS-Kyber）

ML-KEM（Module-Lattice-Based Key-Encapsulation Mechanism）是密钥封装机制，用于在公开信道上建立共享密钥，将替代当前的RSA密钥交换和ECDH。

ML-KEM定义了三个参数集，对应不同的安全级别：

参数集 安全级别 公钥大小 私钥大小 密文大小
ML-KEM-512 Level 1 (≈AES-128) 800 B 1632 B 768 B
ML-KEM-768 Level 3 (≈AES-192) 1184 B 2400 B 1088 B
ML-KEM-1024 Level 5 (≈AES-256) 1568 B 3168 B 1568 B

与ECC相比，公钥和密文确实更大——Curve25519的公钥仅32字节，而ML-KEM-768的公钥是1184字节。但与RSA-2048（256字节公钥）相比，这个开销仍在可接受范围内，特别是在网络带宽持续增长的背景下。

更重要的是性能。多项研究表明，ML-KEM在大多数平台上比ECDH更快。格运算主要是多项式乘法和数论变换（NTT），这些操作在现代CPU上高度优化。一项针对TLS的测试显示，Kyber密钥交换的延迟仅为ECDH的一半左右。

FIPS 204：ML-DSA（源自CRYSTALS-Dilithium）

ML-DSA（Module-Lattice-Based Digital Signature Algorithm）是数字签名标准，用于身份认证和数据完整性验证，将替代RSA和ECDSA签名。

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

参数集 安全级别 公钥大小 私钥大小 签名大小
ML-DSA-44 Level 2 1312 B 2560 B 2420 B
ML-DSA-65 Level 3 1952 B 4032 B 3293 B
ML-DSA-87 Level 5 2592 B 4896 B 4595 B

与ECDSA（P-256）的64字节签名相比，ML-DSA-65的3293字节签名确实大了很多。这对于带宽受限的场景是挑战，但对于大多数互联网应用（TLS证书、代码签名）仍是可接受的。

ML-DSA采用了Fiat-Shamir with Aborts的技术，通过在签名过程中检查某些条件并在不满足时重新采样来保证安全性。这种设计使得签名过程非常高效，验证速度也很快。

FIPS 205：SLH-DSA（源自SPHINCS+）

SLH-DSA（Stateless Hash-Based Digital Signature Algorithm）提供了另一种签名方案选择。它基于哈希函数的安全性，不依赖任何数论假设，被视为最保守的选择。

SLH-DSA的签名较大，根据参数集不同，签名大小在7856字节到49856字节之间。但它有两个重要优势：

  1. 最小安全假设：安全性仅依赖于底层哈希函数的抗碰撞性
  2. 无需额外研究：哈希签名理论已成熟，不需要信任新的数学困难问题

对于需要最高安全保证的场景（如长期归档、关键基础设施），SLH-DSA是重要的备选方案。

还在路上的Falcon

FIPS 206将标准化Falcon算法，这是一种基于NTRU格的签名方案。Falcon的特点是签名更小（约666字节）、公钥更小（约897字节），比Dilithium更适合带宽受限的场景。

但Falcon的实现复杂度较高，特别是需要一种称为"快速傅里叶采样"的技术来生成高斯分布的随机数。这增加了实现难度和潜在的安全风险，因此NIST选择先发布Dilithium和SPHINCS+，同时继续完善Falcon的标准化工作。

迁移的工程挑战

从传统密码迁移到后量子密码不是简单的"替换算法"，而是一项系统工程。

混合部署：过渡期的最佳实践

在PQC算法尚未经过充分密码分析的情况下，业界普遍推荐采用混合方案——同时使用传统算法和PQC算法，两者都必须成功才算成功。

例如，TLS 1.3的混合密钥交换可能同时使用X25519和ML-KEM-768：

客户端生成: x25519_private_key, mlkem_private_key
客户端发送: x25519_public_key || mlkem_public_key

服务端生成: x25519_private_key, mlkem_private_key
服务端发送: x25519_public_key || mlkem_public_key

共享密钥 = KDF(x25519_shared || mlkem_shared)

即使其中一个算法被攻破，另一个仍然保护数据安全。Google、Cloudflare、Amazon等公司已在生产环境中部署了这种混合方案。

密钥和证书管理的变革

PQC算法的密钥和签名更大，对现有的密钥管理系统和证书格式构成挑战：

  • X.509证书需要支持更大的公钥和签名
  • 硬件安全模块（HSM）需要更新固件
  • 证书链的总体大小增加，可能影响TLS握手延迟

NIST正在更新相关标准（如SP 800-57）以指导密钥管理实践。

密码敏捷性：面向未来的架构

“密码敏捷性”（Cryptographic Agility）指系统快速切换密码算法的能力。这次迁移让业界意识到，将特定算法硬编码到系统中是多么危险的设计。

密码敏捷的架构要求：

  1. 协议层：支持算法协商和版本号
  2. 实现层：使用抽象的密码接口而非具体算法
  3. 数据层：存储格式包含算法标识符
  4. 运维层：具备密钥轮换和证书更新的自动化能力

这种架构增加了初始复杂度，但为未来的算法升级（以及可能的紧急替换）铺平了道路。

时间表：从现在到2035年

NIST在2024年11月发布的过渡规划给出了明确的时间线：

  • 2030年：传统公钥密码（RSA、ECDSA）将被标记为"弃用"（deprecated），不推荐用于新系统
  • 2035年：传统公钥密码将被"禁止"（disallowed），必须迁移到PQC

NSA已要求美国国家安全系统在2035年前完成迁移。其他国家也在制定类似计划——英国国家网络安全中心（NCSC）制定了到2035年完成迁移的路线图，加拿大政府也设定了2031年完成高优先系统迁移的目标。

中国的后量子密码进展

中国在PQC领域也在积极推进。2023年12月，国家密码管理局发布公告，征集抗量子密码协议的设计方案，要求提供至少2种抗量子密码协议（如TLS、IPsec、SSH）的设计方法，参数需满足128、192、256比特的量子安全强度。

2025年6月，新华社报道中国专家将牵头制定数据通信领域全球首个抗量子网络安全协议国际标准，表明中国正在积极参与PQC的国际标准化工作。

国内研究者也在算法层面有所贡献。一些中国团队参与了Kyber和Dilithium的设计工作，同时也在探索基于其他数学问题的PQC方案。

量子计算的真实进展

在评估PQC迁移的紧迫性时，需要了解量子计算的最新进展。

IBM的量子路线图显示，他们计划在2029年交付具备约200个逻辑量子比特的容错量子计算机。Google也制定了类似的路线图，目标是2029年实现有用的容错量子计算。

然而，从"有用的容错量子计算"到"能运行Shor算法破解RSA"，中间还有巨大的工程鸿沟。目前Shor算法在量子计算机上成功分解的最大数字是21——这不是笔误，就是数字21。要破解RSA-2048，需要数量级的跨越。

一个更精确的估计来自2025年初的分析：如果当前趋势持续，能够破解RSA-2048的量子计算机可能在2030年左右出现，误差约两年。这个估计存在很大不确定性，取决于量子纠错技术的突破速度。

我们应该担心吗？

对于不同场景，答案不同：

需要长期保密的数据：现在就应该考虑PQC保护。医疗记录、商业机密、国家安全信息可能有几十年甚至更长的保密期。如果攻击者现在截获这些数据，未来可能解密。

短期有效的数据：不必过度恐慌。大多数网络会话、API通信的数据只有短期价值，等到量子计算机成熟时已无意义。但仍需提前规划，因为迁移需要时间。

关键基础设施：应优先迁移。电网、金融系统、通信基础设施的升级周期长，一旦部署需要稳定运行多年，提前迁移可以避免"技术债"积累。

结语：一场没有终点的竞赛

后量子密码学的标准化不是终点，而是起点。密码分析从未停止——即使是经过多年审查的算法，也可能被发现新的弱点。2022年SIKE和Rainbow的被攻破就是提醒。

同时，量子计算也在快速进步。容错量子计算的实现可能比预期更早，也可能更晚。后量子密码迁移需要在"过早投入"和"为时已晚"之间找到平衡。

对于技术决策者，最佳策略是：

  1. 现在开始盘点：识别系统中所有使用密码的地方
  2. 评估风险：根据数据的保密期限和系统的重要性确定迁移优先级
  3. 设计敏捷架构：确保系统能够快速切换密码算法
  4. 采用混合方案：在新系统中同时部署传统算法和PQC算法
  5. 持续跟踪：关注NIST的后续标准化工作和密码分析进展

密码学的历史告诉我们，最危险的是那些我们还不知道自己不知道的事情。保持警惕、保持敏捷，是在这个不确定时代保护数据安全的最佳策略。

参考资料

  1. NIST. (2024). Post-Quantum Cryptography FIPS Approved. NIST CSRC.
  2. Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484-1509.
  3. Regev, O. (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. STOC ‘05.
  4. Gidney, C., & Eker, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433.
  5. NIST. (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard.
  6. NIST. (2024). FIPS 204: Module-Lattice-Based Digital Signature Standard.
  7. NIST. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard.
  8. NIST. (2024). Transition to Post-Quantum Cryptography Standards (NIST IR 8547).
  9. Bos, J., et al. (2018). CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM. IEEE EuroS&P.
  10. Avanzi, R., et al. (2017). CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Cryptology ePrint Archive.
  11. Bernstein, D. J., et al. (2015). SPHINCS: Practical Stateless Hash-Based Signatures. EUROCRYPT 2015.
  12. Moody, D. (2022). Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. NIST IR 8413.
  13. IBM. (2025). IBM Quantum Roadmap.
  14. NCSC. (2025). Roadmap for the migration to post-quantum cryptography.