Shor 算法与 Grover 算法详解

量子计算机并非只是更快地运行经典算法——它们利用量子叠加和干涉，以指数级更快的速度解决某些问题。两种算法威胁着大多数已部署的密码系统：Shor 算法（破解 RSA/ECC）和 Grover 算法（削弱对称密码和哈希算法）。

Shor 算法（1994 年）可以在量子计算机上以多项式时间解决整数分解和离散对数问题。它会直接破解 RSA（基于因数分解）、Diffie-Hellman（模 p 的离散对数）以及 ECDH/ECDSA（椭圆曲线离散对数）。

Shor 算法的关键组成部分是量子傅里叶变换（QFT）——DFT 的量子版本，速度呈指数级提升。在寻找周期时，QFT 可以确定 f(x) = a^x mod N 的周期，并通过 GCD 推导出 N 的因数。

要分解 N： (1) 随机选择 a < N，并检查 gcd(a,N)=1。 (2) 使用 QFT 找到 f(x)=a^x mod N 的周期 r。 (3) 在较高概率下，gcd(a^{r/2}±1, N) 可以得到一个非平凡因数。经典步骤的复杂度为 O(log N)；量子寻找周期的复杂度为 O((log N)^3)，属于多项式时间。

经典因数分解的最佳算法是 GNFS，复杂度为亚指数级 O(exp((64/9 log N)^{1/3} log log N)^{2/3}))。容错量子计算机上的 Shor 算法复杂度为多项式级 O((log N)^3)。破解 RSA-2048 需要约 4000 个逻辑量子比特和约 10^9 次门操作。如今的 NISQ 计算机只有约 1000 个含噪量子比特，尚未构成威胁。

Grover 算法（1996 年）可以对无结构搜索提供平方级加速。对于包含 N 个项目的搜索空间，经典算法需要 O(N) 次查询，而 Grover 算法只需要 O(√N) 次查询。应用于密码学时，它可以在 O(2^{n/2}) 而不是 O(2^n) 的复杂度下破解 n 位对称密钥。

AES-128 的经典安全强度为 2^128，Grover 算法会将其降至 2^64，因此无法抵御大型量子计算机。AES-256 的安全强度从 2^256 降至 2^128，仍然安全。解决办法是将对称密钥长度加倍。SHA-256 的抗碰撞强度从 2^128 降至 2^85（生日攻击加 Grover 算法）。SHA-256 的原像安全强度从 2^256 降至 2^128，仍然可以接受。

当前的 NISQ 量子计算机（IBM Heron：133 个量子比特；Google Sycamore：70 个量子比特）规模太小且噪声太大，无法执行具有密码学意义的计算。估计需要到 2035—2050 年，容错量子计算机才可能破解 RSA-2048。先收集、后解密攻击已经构成当前威胁。

攻击者如今收集并存储加密流量。等量子计算机可用后，他们会对这些流量进行追溯解密。因此，长期有效的机密（例如政府机密数据和医疗记录）如今就已经面临风险。对于此类数据，PQC 迁移必须立即开始。

格问题（LWE、SIS）、基于编码的问题（McEliece）、基于哈希的签名（SPHINCS+）以及多变量问题，目前都没有已知的多项式时间量子算法。这些问题构成了 NIST 后量子标准的基础。

NIST 的 PQC 标准（ML-KEM、ML-DSA、SLH-DSA）已于 2024 年定稿。各组织应当：清点当前密码学的使用情况，识别需要长期保存的数据，并优先为密钥交换部署 PQC（由于先收集、后解密攻击，密钥交换最为紧迫）。签名迁移相对没有那么紧迫。

Grover 算法对 AES-128 有什么影响？

Shor 算法（多项式时间）可以破解 RSA、DH 和 ECC。Grover 算法（平方级加速）会使对称密钥的强度减半。解决办法是迁移到 NIST 的 PQC 标准（基于格）。下一节：CRYSTALS-Kyber KEM。