在经典计算机上，分解一个 2048 位的大整数需要的时间远超宇宙年龄；在量子计算机上，同样的任务可能仅需数小时。1994 年，Peter Shor 在贝尔实验室发表了一篇论文，证明量子计算机能够在多项式时间内完成整数分解（integer factorization）与离散对数（discrete logarithm）运算。次年，Lov Grover 提出了一种量子搜索算法，能将无结构搜索问题的复杂度从 O(N) 降低至 O(√N)。这两个算法被视为量子计算领域最重要的理论成果，它们从根本上动摇了现代公钥密码体系和对称密码体系的安全假设。本文将深入剖析这两个算法的数学原理、量子电路构造以及对各类密码算法的具体影响，帮助读者理解”量子威胁”究竟意味着什么。
一、Shor 算法概述
Shor 算法的核心目标是在多项式时间内完成两个数论难题：大整数分解和离散对数求解。在经典计算中，已知的最优整数分解算法是通用数域筛法（General Number Field Sieve, GNFS），其运行时间为亚指数级别 exp(O(n^{1/3} (log n)^{2/3}))，其中 n 是待分解整数的位数。对于 RSA-2048，这意味着即使调动全球所有经典计算资源，仍然无法在可接受的时间内完成分解。
Shor 算法将整数分解问题归约（reduce）为周期查找（period finding）问题，再利用量子傅里叶变换（Quantum Fourier Transform, QFT）在量子计算机上高效求解周期。整个算法的时间复杂度为 O(n^2 log n log log n)，其中 n 为输入整数的位数，这是一个真正的多项式时间算法。
从历史意义上看，Shor 算法的提出是量子计算从纯理论研究走向实际应用关注的分水岭。在此之前，量子计算机被许多人视为纯粹的学术玩具；Shor 算法证明了量子计算机至少在密码分析这一领域具有压倒性的优势。这一成果直接促使了世界各国在量子计算研发上投入巨额资金，也催生了后量子密码学（Post-Quantum Cryptography, PQC）这一新兴研究方向。
Shor 算法不仅能分解整数，还能求解有限域上的离散对数问题（Discrete Logarithm Problem, DLP）和椭圆曲线上的离散对数问题（Elliptic Curve Discrete Logarithm Problem, ECDLP）。这意味着基于 RSA、Diffie-Hellman（DH）、数字签名算法（DSA）以及椭圆曲线密码（ECC）的所有公钥密码方案在足够大的量子计算机面前都将失去安全性。
二、量子傅里叶变换
量子傅里叶变换（QFT）是 Shor 算法的核心量子子程序。它是经典离散傅里叶变换（Discrete Fourier Transform, DFT）在量子态上的对应物，但其量子电路实现仅需 O(n^2) 个量子门，而经典快速傅里叶变换（Fast Fourier Transform, FFT）需要 O(n 2^n) 次运算（注意这里的 n 指的是量子比特数，对应 N = 2^n 个基态）。
给定一个 n 量子比特的计算基态 |j⟩，QFT 将其变换为：
QFT|j⟩ = (1/√N) Σ_{k=0}^{N-1} e^{2πi jk/N} |k⟩
其中 N = 2^n。这与经典 DFT 的定义形式完全一致，区别在于 QFT 作用于量子叠加态，能够并行处理所有 2^n 个输入。
QFT 的量子电路由 Hadamard 门（Hadamard gate）和受控旋转门（controlled rotation gate）构成。对于 n 个量子比特，电路结构如下：首先对第一个量子比特施加 Hadamard 门，然后依次施加受控 R_2、R_3、……、R_n 旋转门，其中 R_k 表示相位旋转 2π/2^k；接着对第二个量子比特重复类似操作，但受控旋转门减少一个；如此递推直至最后一个量子比特只需施加一个 Hadamard 门。最后，还需要一系列 SWAP 门将量子比特顺序反转。
整个 QFT 电路所需的量子门数量为 n(n-1)/2 个受控旋转门加上 n 个 Hadamard 门，总计 O(n^2)。与经典 FFT 的 O(N log N) = O(n 2^n) 相比，QFT 在门数上实现了指数级的缩减。然而需要特别指出的是，QFT 的优势建立在量子叠加态的基础上——我们无法直接读出所有傅里叶系数，只能通过测量获得一个概率性的结果。这正是 Shor 算法巧妙之处：它将问题设计为使得测量结果中蕴含周期信息。
在近似实现中，可以省略角度小于某一阈值的受控旋转门而不显著影响最终结果的精度。Coppersmith 证明，保留 O(log n) 位精度的旋转门即可获得足够好的近似 QFT，此时门数进一步减少至 O(n log n)。
三、Shor 算法的周期查找
Shor 算法将大整数分解归约为周期查找问题的过程如下。设我们要分解合数 N。随机选择一个与 N 互素的整数 a（若 gcd(a, N) ≠ 1 则已经找到一个非平凡因子），定义函数 f(x) = a^x mod N。由欧拉定理可知，该函数是周期函数，设其周期为 r，即满足 a^r ≡ 1 (mod N) 的最小正整数 r。如果能够高效求出 r，那么：
- 若 r 为偶数，计算 a^{r/2} mod N；
- 检查 a^{r/2} ≢ -1 (mod N)；
- 若以上两个条件满足，则 gcd(a^{r/2} - 1, N) 和 gcd(a^{r/2} + 1, N) 中至少有一个是 N 的非平凡因子。
数论分析表明，随机选取 a 后以上条件成立的概率不小于 1/2，因此只需重复常数次即可以高概率成功分解 N。
量子周期查找电路使用两组量子寄存器：第一组包含约 2n 个量子比特（称为”输入寄存器”），第二组包含 n 个量子比特（称为”输出寄存器”），其中 n = ⌈log₂ N⌉。算法步骤如下：
第一步，将输入寄存器初始化为均匀叠加态。对所有量子比特施加 Hadamard 门，得到 (1/√Q) Σ_{x=0}^{Q-1} |x⟩，其中 Q = 2^{2n}。
第二步，通过量子模幂运算（modular exponentiation）计算 f(x) = a^x mod N，将结果存入输出寄存器。此时系统的量子态变为 (1/√Q) Σ_{x=0}^{Q-1} |x⟩|a^x mod N⟩。
第三步，对输入寄存器施加逆量子傅里叶变换（inverse QFT）。由于模幂函数的周期性，逆 QFT 会使得输入寄存器中与周期 r 相关的频率分量获得相长干涉（constructive interference），而与周期无关的分量相消（destructive interference）。
第四步，测量输入寄存器，得到一个接近 kQ/r（其中 k 为某个整数）的值。通过连分数展开（continued fraction expansion）算法，可以从测量结果中提取周期 r。
整个算法中计算量最大的部分是量子模幂运算。对 n 位整数进行模幂运算需要 O(n^2) 个基本量子门（使用平方-乘方法），再乘以 QFT 的 O(n^2) 门数，总的门复杂度为 O(n^3) 量级（更精确的分析给出 O(n^2 log n log log n)）。
以下 Python 代码展示了一个简化的量子周期查找经典模拟，帮助理解算法的核心逻辑：
import math
import random
from fractions import Fraction
def classical_simulate_shor(N):
"""
经典模拟 Shor 算法的周期查找过程。
在真正的量子计算机上，周期查找由 QFT 完成；
这里用经典 DFT 模拟量子测量的概率分布。
"""
if N % 2 == 0:
return 2
# 随机选择底数 a
a = random.randrange(2, N)
g = math.gcd(a, N)
if g > 1:
return g
# 模拟量子寄存器大小 Q = 2^(2n)
n = N.bit_length()
Q = 1 << (2 * n)
# 计算 f(x) = a^x mod N 对所有 x in [0, Q)
# 在量子计算机上这一步通过叠加态并行完成
fx = [pow(a, x, N) for x in range(Q)]
# 模拟逆 QFT 后的测量概率分布
# P(c) = |sum_{x: f(x)=s} exp(2*pi*i*c*x/Q)|^2 对某个 s
# 峰值出现在 c ≈ k*Q/r 处
probs = [0.0] * Q
target_s = fx[0]
matching_x = [x for x in range(Q) if fx[x] == target_s]
for c in range(Q):
amplitude = 0.0
for x in matching_x:
amplitude += math.cos(2 * math.pi * c * x / Q)
probs[c] = amplitude ** 2
# 选取概率最大的测量结果
measured_c = max(range(Q), key=lambda c: probs[c])
if measured_c == 0:
# 重试以避免平凡结果
probs[0] = 0
measured_c = max(range(Q), key=lambda c: probs[c])
# 连分数展开提取周期 r
frac = Fraction(measured_c, Q).limit_denominator(N)
r = frac.denominator
# 验证周期
if r > 0 and pow(a, r, N) == 1:
if r % 2 == 0:
half = pow(a, r // 2, N)
if half != N - 1:
p = math.gcd(half - 1, N)
q = math.gcd(half + 1, N)
if 1 < p < N:
return p
if 1 < q < N:
return q
return None
if __name__ == "__main__":
test_values = [15, 21, 35, 77, 91]
for N in test_values:
for attempt in range(10):
factor = classical_simulate_shor(N)
if factor and 1 < factor < N:
print(f"N = {N}: 找到因子 {factor}（验证: {N} = {factor} × {N // factor}）")
break
else:
print(f"N = {N}: 未能在 10 次尝试内找到因子")这段代码用经典方式模拟了量子周期查找的概率行为。在真正的量子计算机上，QFT 能在一次操作中同时对所有 Q 个振幅进行傅里叶变换，而经典模拟则需要 O(Q^2) 的时间来逐一计算每个频率分量的振幅——这正是量子计算的指数加速优势所在。
四、Shor 算法对 RSA 的影响
RSA 密码系统的安全性完全依赖于大整数分解的困难性。一个 RSA-2048 密钥意味着攻击者需要分解一个 2048 位（约 617 位十进制数字）的合数 N = p × q。在经典计算机上，这是一个不可行的计算任务；但在量子计算机上，Shor 算法可以在多项式时间内完成。
具体的量子资源需求如下。分解一个 n 位整数，Shor 算法需要约 2n + 3 个逻辑量子比特（logical qubits）。对于 RSA-2048，这意味着大约需要 4099 个逻辑量子比特。然而，逻辑量子比特与物理量子比特（physical qubits）之间存在巨大差距——为了实现容错量子计算（fault-tolerant quantum computing），每个逻辑量子比特需要通过量子纠错码（quantum error-correcting code）编码到数千甚至数万个物理量子比特上。
2021 年，Gidney 和 Ekera 发表了一项优化研究，表明使用约 2000 万个带噪声的超导量子比特，可以在约 8 小时内分解 RSA-2048。这一估计基于表面码（surface code）纠错方案，假设物理量子门的错误率约为 10^{-3}。后续研究进一步优化了资源估计：在更乐观的假设下（错误率 10^{-4}、更快的门操作时间），所需的物理量子比特数可降低至数百万量级。
当前最先进的超导量子处理器拥有约一千多个物理量子比特，且噪声水平尚未达到容错计算的门槛。主流预测认为，能够破解 RSA-2048 的量子计算机可能在 2030 年代中后期至 2040 年代出现，但技术突破可能加速这一时间线。部分研究机构认为，若离子阱（trapped-ion）或拓扑量子比特（topological qubit）等替代技术取得突破性进展，时间线可能提前五到十年。
无论确切时间点何时到来，密码学界的共识是：现在就必须开始向抗量子密码算法迁移。RSA-3072 或 RSA-4096 并不能提供根本性的保护——将密钥长度翻倍仅仅使 Shor 算法所需的量子比特数翻倍，而非指数级增长。这与经典攻击形成鲜明对比：在经典计算中，将 RSA 密钥从 1024 位增加到 2048 位会使攻击难度增加数个数量级。
五、Shor 算法对 ECC 的影响
椭圆曲线密码（ECC）的安全性基于椭圆曲线离散对数问题（ECDLP）：给定椭圆曲线上的点 P 和 Q = kP，求整数 k。经典情况下，ECDLP 比同等安全级别的整数分解问题更加困难——256 位的 ECC 密钥提供的安全性大致等同于 3072 位的 RSA 密钥。
然而，Shor 算法的变体可以同样高效地求解 ECDLP。Proos 和 Zalka 在 2003 年的分析表明，破解一个 n 位的椭圆曲线密钥大约需要 6n + O(log n) 个逻辑量子比特。对于常用的 256 位椭圆曲线（如 P-256 或 Curve25519），这意味着大约需要 1500 至 2500 个逻辑量子比特——远少于破解同等安全级别 RSA 密钥所需的量子资源。
这一不对称性意味着 ECC 在量子威胁面前实际上比 RSA 更加脆弱。虽然 ECC 在经典计算环境中因其短密钥、高效率而被广泛采用（TLS 1.3、Signal 协议、比特币等均使用 ECC），但它可能是最早被量子计算机攻破的公钥密码方案之一。
Shor 算法的影响范围不限于 RSA 和 ECC。所有基于以下困难假设的密码方案均受影响：
- 整数分解问题：RSA 加密、RSA 签名
- 有限域离散对数问题：经典 Diffie-Hellman、DSA、ElGamal
- 椭圆曲线离散对数问题：ECDH、ECDSA、EdDSA、SM2
- 双线性配对（bilinear pairing）问题：基于配对的密码方案
简而言之，当今互联网上几乎所有公钥密码基础设施（Public Key Infrastructure, PKI）在量子计算机面前都将变得不安全。这是推动后量子密码标准化的根本原因。
六、Grover 算法原理
与 Shor 算法专注于特定数论问题不同，Grover 算法解决的是一个更为通用的问题：无结构搜索（unstructured search）。假设有一个函数 f: {0, 1, …, N-1} → {0, 1}，其中恰好有一个输入 w 满足 f(w) = 1（称为”标记元素”），目标是找到 w。在经典计算中，最优策略是逐一查询，平均需要 N/2 次查询；Grover 算法将查询次数降低至 O(√N)。
Grover 算法的核心机制是振幅放大（amplitude amplification）。算法使用两个关键操作：
第一个是量子预言机（quantum oracle） O_f，它对标记元素的振幅施加一个负号翻转：O_f|x⟩ = (-1)^{f(x)}|x⟩。这一操作本身并不改变测量到各元素的概率，但它为后续步骤创造了条件。
第二个是关于均匀叠加态的反射操作（diffusion operator），也称为 Grover 扩散算子 D。其数学表达为 D = 2|ψ⟩⟨ψ| - I，其中 |ψ⟩ = (1/√N) Σ|x⟩ 是均匀叠加态，I 是单位算子。这一操作的几何意义是将量子态关于均匀叠加态进行”反射”。
算法流程如下：首先将所有量子比特初始化为均匀叠加态 |ψ⟩；然后交替施加预言机 O_f 和扩散算子 D，每次施加这一对操作称为一次”Grover 迭代”。每次迭代都会使标记元素的振幅增大，同时使其他元素的振幅减小。
从几何角度看，初始状态 |ψ⟩ 可以分解为标记元素方向和非标记元素方向的两个分量。每次 Grover 迭代相当于在这个二维子空间中旋转一个固定角度 2θ，其中 sin θ = 1/√N。经过约 (π/4)√N 次迭代后，量子态几乎完全旋转到标记元素方向，此时测量将以接近 1 的概率得到正确答案。
值得注意的是，Grover 算法不能无限迭代——超过最优迭代次数后，标记元素的振幅反而会开始减小。这一特性与经典搜索有本质区别，是量子算法的独特现象。
当存在 M 个标记元素时，Grover 算法的最优迭代次数变为约 (π/4)√(N/M)，总查询次数为 O(√(N/M))。Bennett 等人证明，对于无结构搜索问题，O(√N) 是量子计算的理论下界，因此 Grover 算法在渐近意义上是最优的。
七、Grover 对对称密码的影响
Grover 算法对对称密码（symmetric cipher）的影响是将有效安全级别减半。考虑一个密钥长度为 k 位的对称加密算法，攻击者需要在 2^k 个可能的密钥中搜索正确密钥。使用 Grover 算法，搜索复杂度降为 O(2^{k/2})，即安全级别从 k 位降至 k/2 位。
具体到常用算法：
- AES-128：经典安全级别 128 位，量子安全级别降至 64 位。64 位安全级别在当今已被认为不够安全，因此 AES-128 在量子时代将不再满足标准安全要求。
- AES-192：经典安全级别 192 位，量子安全级别降至 96 位。
- AES-256：经典安全级别 256 位，量子安全级别降至 128 位。128 位安全级别通常被认为足以抵抗量子攻击，因此 AES-256 被视为”量子安全”的对称加密选择。
- ChaCha20：使用 256 位密钥，量子安全级别为 128 位，同样被视为量子安全。
对于散列函数（hash function），Grover 算法同样产生影响。寻找散列原像（preimage）的复杂度从 O(2^n) 降至 O(2^{n/2})，其中 n 为散列输出长度。这意味着 SHA-256 的原像安全级别从 256 位降至 128 位。
散列碰撞（collision）问题更为复杂。经典的生日攻击（birthday attack）已经将碰撞搜索复杂度降至 O(2^{n/2})。在量子情况下，Brassard、Hoyer 和 Tapp 提出的 BHT 算法可以将碰撞搜索复杂度进一步降低至 O(2^{n/3})——即 N 的立方根级别。对于 SHA-256，这意味着碰撞安全级别从 128 位降至约 85 位。因此，对于需要长期碰撞抗性的应用场景，应考虑使用 SHA-384 或 SHA-512。
然而需要指出的是，Grover 算法在实际应用中面临一些限制。首先，Grover 搜索本质上是串行的——它不像经典暴力搜索那样容易并行化。经典攻击者可以使用 P 台并行计算机将搜索时间缩短为原来的 1/P，而 Grover 算法使用 P 台量子计算机只能将搜索时间缩短为原来的 1/√P。这意味着在考虑并行化后，Grover 算法的实际优势可能不如理论分析所示的那么大。其次，每次 Grover 迭代需要完成一次完整的加密运算（作为量子预言机），这对量子电路的深度和可靠性提出了极高要求。对于 AES-256，一次 Grover 搜索需要约 2^{128} 次迭代，每次迭代涉及数千个量子门——即使在高度乐观的假设下，这也需要一台在极长时间内保持相干性的量子计算机。
因此，对称密码学界的普遍建议是：将密钥长度翻倍即可有效应对 Grover 攻击。这比公钥密码系统需要完全更换算法的情况要温和得多。
八、量子资源估计
理解量子威胁的紧迫程度，需要对实际破解密码系统所需的量子资源有清晰的认识。这里涉及几个关键概念：逻辑量子比特（logical qubits）、物理量子比特（physical qubits）、T 门深度（T-gate depth）以及量子纠错开销（error correction overhead）。
逻辑量子比特是算法层面的量子比特，执行精确的量子运算。物理量子比特则是实际硬件中带有噪声的量子比特。为了实现容错计算，需要使用量子纠错码将多个物理量子比特编码为一个逻辑量子比特。目前最有前景的纠错方案是表面码（surface code），其编码率随所需纠错能力的增加而降低。
以破解 RSA-2048 为例，各项资源估计如下：
- 逻辑量子比特：约 4000 个（使用优化的 Shor 算法实现）
- 物理量子比特：约 2000 万个（假设表面码距离 d ≈ 27，物理错误率 p ≈ 10^{-3}）
- T 门数量：约 2.4 × 10^{12}（万亿级别）
- 运行时间：约 8 小时（假设门操作时间约 1 微秒、魔法态蒸馏工厂并行运行）
对于破解 ECC P-256：
- 逻辑量子比特：约 2300 个
- 物理量子比特：约 900 万个
- 运行时间：约数小时
当前量子硬件的状况与上述需求之间存在巨大鸿沟。截至目前，领先的量子计算平台包括：IBM 的超导量子处理器（约 1000 多个物理量子比特）、Google 的 Sycamore 和 Willow 系列处理器、IonQ 的离子阱处理器等。这些处理器的物理量子比特数量比破解 RSA-2048 所需的少三到四个数量级，且尚未实现真正的容错计算。
T 门深度是另一个关键瓶颈。T 门是通用量子计算中最昂贵的非 Clifford 门（non-Clifford gate），在表面码架构中需要通过魔法态蒸馏（magic state distillation）来实现，这一过程消耗大量的额外量子比特和时间。降低 T 门数量是当前量子算法优化的重要研究方向。
纠错开销方面，表面码每个逻辑量子比特需要 O(d^2) 个物理量子比特，其中码距 d 需要满足逻辑错误率低于算法所需的容错阈值。对于需要执行 10^{12} 量级 T 门的 Shor 算法，逻辑错误率需要低于 10^{-15} 左右，这要求较大的码距和较低的物理错误率。
尽管挑战巨大，量子硬件的进展速度不容忽视。过去几年中，物理量子比特数量大致以每一到两年翻倍的速度增长，错误率也在持续降低。若这一趋势延续，密码学相关的量子威胁可能在未来十到二十年内成为现实。
九、先收集后解密（Harvest Now, Decrypt Later）
即使大规模量子计算机尚未出现，量子威胁已经在影响当今的安全决策。这主要源于一种被称为”先收割，后解密”（Harvest Now, Decrypt Later, HNDL）的攻击模型。
HNDL 威胁模型描述的场景是：攻击者在当前截获并存储加密通信数据，等待未来拥有量子计算机时再进行解密。对于通过公钥密码协商的会话密钥保护的数据，一旦量子计算机能够破解密钥交换过程中使用的公钥算法，所有历史流量都将暴露。
这一威胁的严重程度取决于数据的保密期限（data lifetime）。不同类型的数据有不同的敏感期限：
- 战术军事通信：通常仅需数小时至数天的保密性
- 商业谈判信息：可能需要数月至数年的保密性
- 国家安全情报：通常需要数十年的保密性
- 个人健康记录：在个人一生中均需保密
- 核设施设计参数：可能需要保密数十年乃至更长
对于那些需要长期保密的数据，HNDL 威胁意味着它们在今天就已经处于风险之中。如果量子计算机在 15 年后出现，那么今天传输的、需要保密超过 15 年的任何数据都可能被未来的量子攻击者解密。
这种”回溯解密”的威胁对前向保密（forward secrecy）也提出了新的挑战。虽然 TLS 1.3 等现代协议支持使用临时 ECDH 密钥实现前向保密，但如果底层的椭圆曲线密钥交换被量子计算机攻破，前向保密的保证也将失效。
HNDL 模型是推动”现在就开始迁移”的最有力论据。美国国家安全局（NSA）在 2015 年发布的声明中指出，联邦政府系统应开始向抗量子密码算法过渡。美国国家标准与技术研究院（NIST）于 2016 年启动了后量子密码标准化进程，并在 2024 年发布了首批三个后量子密码标准（ML-KEM、ML-DSA 和 SLH-DSA）。
对于企业和组织而言，应对 HNDL 威胁的建议策略包括：
第一，进行密码资产清查（cryptographic inventory），识别所有使用公钥密码的系统和数据流。
第二，评估数据保密期限——对于保密需求超过 10 至 15 年的数据，应优先迁移。
第三，在密钥交换环节率先部署后量子密码算法或采用混合方案（hybrid scheme），将经典密钥交换与后量子密钥交换组合使用。
第四，制定和演练密码敏捷性（cryptographic agility）策略，确保系统能够在不进行大规模重构的情况下更换密码算法。
量子计算对密码学的冲击不是一个遥远的科幻议题，而是一个正在影响当今安全架构设计的现实挑战。Shor 算法和 Grover 算法的存在意味着我们必须以前所未有的紧迫感推进密码体系的演进。无论量子计算机的确切到来时间如何，提前做好准备的代价远低于被动应对的损失。密码学的历史告诉我们：算法的瓦解往往比预期来得更快，而迁移的过程总是比预想的更慢。现在就行动，才是最明智的选择。
十、量子算法影响与应对策略矩阵
下表从算法、受影响密码体制和应对策略三个维度，系统梳理量子计算对现有密码基础设施的冲击全景。
| 量子算法 | 攻击原理 | 受影响的密码方案 | 影响程度 | 应对策略 |
|---|---|---|---|---|
| Shor 算法 | 在多项式时间内求解大整数分解与离散对数问题 | RSA（所有密钥长度）、DSA、ECDSA、ECDH、DH、ElGamal | 致命——算法完全失效，无法通过增加密钥长度挽救 | 迁移至后量子密码方案（ML-KEM、ML-DSA 等）；过渡期采用混合模式 |
| Grover 算法 | 对无结构搜索问题提供二次加速 | AES-128（等效安全性降至 64 位）、AES-192（降至 96 位）、AES-256（降至 128 位） | 可控——将密钥长度加倍即可恢复原有安全级别 | AES-128 升级至 AES-256；对称密码体系整体保持可用 |
| Grover 算法（应用于哈希） | 对碰撞搜索和原像搜索提供加速 | SHA-256（原像安全性从 256 位降至 128 位）、SHA-3 系列 | 可控——输出长度加倍即可应对 | SHA-256 在大多数场景下仍然安全；高安全需求场景可迁移至 SHA-384/SHA-512 |
| 潜在的未来量子算法 | 未知——可能发现新的量子加速攻击 | 格基方案（LWE/MLWE）、编码基方案、哈希基方案 | 未知——目前无已知量子多项式时间攻击 | 保持密码敏捷性（crypto agility）；关注量子算法研究进展；部署算法多样性 |
笔者认为，Grover 算法的实际威胁在大众媒体中被显著高估了，而 Shor 算法的破坏力则被恰如其分地警惕着。原因在于：Grover 算法仅提供二次加速（\(O(2^n) \to O(2^{n/2})\)），其对对称密码的影响等价于”将密钥长度减半”——AES-256 在量子计算机面前仍具备 128 位安全性，这在可预见的未来是完全足够的。更关键的是，Grover 算法的加速难以与并行化叠加：经典计算机投入 \(k\) 倍算力可将搜索时间缩短 \(k\) 倍，但 \(k\) 台量子计算机并行运行 Grover 算法只能将时间缩短 \(\sqrt{k}\) 倍。这意味着”用更多量子计算机暴力破解 AES-256”的经济成本极其高昂。相比之下，Shor 算法对公钥密码的打击是毁灭性的——它不是”让攻击变难一点”，而是”让攻击变得轻而易举”。RSA-2048 在足够大的量子计算机面前与明文传输无异。这种不对称性决定了后量子迁移的优先级：公钥密码的迁移刻不容缓，对称密码只需审慎调整参数。
密码学百科系列 · 第 56 篇