量子计算与密码学：Shor 算法对 RSA 的威胁与后量子密码学迁移

量子计算正从理论物理走向工程现实。当谷歌宣称实现"量子霸权"、IBM 推出千量子比特处理器时，密码学界早已开始为一场静默的革命做准备：现有的 RSA、ECC 等公钥密码体系，在足够强大的量子计算机面前将不堪一击。

一、Shor 算法：RSA 的终结者

1994 年，贝尔实验室的 Peter Shor 提出了一种量子算法，可以在多项式时间内完成两个经典计算难题：

• 大整数质因数分解（RSA 的安全基础）
• 离散对数求解（ECC、Diffie-Hellman 的安全基础）

经典算法分解一个 2048 位的 RSA 模数需要数百万年，而 Shor 算法在理论上只需数小时——前提是拥有足够稳定的量子计算机。其核心思想是利用量子傅里叶变换（QFT）快速找到周期，将因数分解转化为周期查找问题。

Shor 算法的关键步骤

1. 随机选择与 N 互质的整数 a
2. 用量子电路构造函数 f(x) = a^x mod N
3. 通过量子叠加态同时计算所有 x 的函数值
4. 应用量子傅里叶变换提取周期 r
5. 经典后处理：若 r 为偶数，gcd(a^(r/2) ± 1, N) 即为因子

二、Grover 算法：对称密码的"平方根加速"

与 Shor 算法的指数级加速不同，Grover 算法提供的加速较为温和——将无序搜索的复杂度从 O(N) 降至 O(√N)。这意味着：

• AES-128 的有效安全性降至 64 位（需迁移至 AES-256）
• SHA-256 的抗碰撞性降至 128 位（需迁移至 SHA-384/512）

虽然威胁不如 Shor 算法紧迫，但 Grover 算法对所有对称密码和哈希函数都是普适性的威胁，必须在安全规划中予以考虑。

三、后量子密码学（PQC）：构建量子安全的防线

后量子密码学的目标是设计即使在量子计算机存在的情况下仍然安全的密码算法。目前主流的技术路线包括：

1. 格密码（Lattice-based Cryptography）

基于高维格中的最短向量问题（SVP）和学习 with 错误问题（LWE）。代表方案：

• Kyber：密钥封装机制（KEM），已被 NIST 选为标准化算法（ML-KEM）
• Dilithium：数字签名方案（ML-DSA），基于模块格上的短整数解问题

2. 哈希签名（Hash-based Signatures）

基于哈希函数的抗碰撞性，安全性证明严格。代表方案：

• SPHINCS+（SLH-DSA）：无状态哈希签名，NIST 标准化
• XMSS/LMS：有状态签名，已用于固件更新等场景

3. 编码密码（Code-based Cryptography）

基于纠错码的译码困难性。代表方案：

• Classic McEliece：NIST 第四轮候选，密钥尺寸较大但安全性历史悠久

4. 多变量密码（Multivariate Cryptography）

基于多变量二次方程组求解的困难性，签名速度快，但密钥尺寸较大。

四、NIST 后量子密码标准化进程

美国国家标准与技术研究院（NIST）自 2016 年启动后量子密码标准化项目，经过多轮评估，已于 2024 年正式发布三项标准：

五、量子密钥分发（QKD）：物理层的安全保障

与 PQC 的软件/算法路线不同，量子密钥分发利用量子力学原理（如海森堡测不准原理、量子不可克隆定理）实现信息论安全：

• BB84 协议：最经典的 QKD 方案，使用光子的偏振态编码
• E91 协议：基于量子纠缠的密钥分发
• 中国"墨子号"卫星：2017 年实现 1200 公里级别的星地量子密钥分发

QKD 的局限性在于需要专用光纤/卫星链路，且传输距离受限，更适合骨干网和高安全场景，难以替代互联网规模的 PQC 部署。

六、企业迁移路线图：现在就应该开始

量子威胁并非遥不可及。攻击者可能已经在收集加密流量（"先收集，后解密"策略），等待量子计算机成熟后解密历史数据。企业应立即启动迁移规划：

阶段一：加密资产盘点（0-6 个月）

• 识别所有使用 RSA/ECC 的系统、证书、协议
• 评估数据敏感度和保留期限
• 建立加密敏捷性（Crypto Agility）架构

阶段二：混合部署试点（6-18 个月）

• 在 TLS 1.3 中启用混合密钥交换（X25519 + Kyber768）
• 试点 ML-DSA 代码签名
• 更新 HSM/KMS 支持 PQC 算法

阶段三：全面迁移（18-36 个月）

• 替换所有面向长期的数字证书
• 升级 VPN、SSH、数据库加密
• 淘汰不支持 PQC 的遗留系统

七、结语：密码学的范式转移

量子计算对密码学的冲击，堪比 20 世纪 70 年代公钥密码学的诞生。从对称密码到公钥密码，再到后量子密码，密码学始终在"攻击-防御"的博弈中演进。

对于开发者和安全工程师而言，理解量子威胁的本质、跟踪 NIST 标准化进展、提前布局加密敏捷性，是未来十年最重要的技术储备之一。量子时代不会一夜之间到来，但准备工作必须从现在开始。

关键要点：

• Shor 算法使 RSA/ECC 在量子计算机面前失效，迁移窗口正在收窄
• 格密码（Kyber/Dilithium）是 NIST 首选的后量子方案
• 混合部署（经典 + PQC）是过渡期的最佳实践
• 加密敏捷性架构是长期安全的基础设施