【密码学百科】Shor 算法与 Grover 算法：量子计算对密码学的冲击

在经典计算机上，分解一个 2048 位的大整数需要的时间远超宇宙年龄；在量子计算机上，同样的任务可能仅需数小时。1994 年，Peter Shor 在贝尔实验室发表了一篇论文，证明量子计算机能够在多项式时间内完成整数分解（integer factorization）与离散对数（discrete logarithm）运算。次年，Lov Grover 提出了一种量子搜索算法，能将无结构搜索问题的复杂度从 O(N) 降低至 O(√N)。这两个算法被视为量子计算领域最重要的理论成果，它们从根本上动摇了现代公钥密码体系和对称密码体系的安全假设。本文将深入剖析这两个算法的数学原理、量子电路构造以及对各类密码算法的具体影响，帮助读者理解”量子威胁”究竟意味着什么。

一、Shor 算法概述

先看一张图，把这一节的关键关系串起来。

graph TD
    A[Shor] --> B[RSA 与 ECC]
    C[Grover] --> D[对称安全减半]
    B --> E[后量子迁移]
    D --> E

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 算法做的正是同一件事：函数 f(x) = a^x mod N 是一条”数论绳子”，它的起伏（取值）具有精确的周期 r，而量子傅里叶变换就是量子版的”频谱分析仪”，能够从叠加态中一次性提取出这个周期。经典计算机之所以做不到这一点，是因为它每次只能测量”绳子”上的一个点；量子计算机则通过叠加态同时”触摸”了绳子上的所有点，再通过干涉让周期信息自然浮现。

这一直觉还解释了为什么 Shor 算法不能加速一般性搜索问题：没有周期性结构的问题就像完全随机起伏的绳子——傅里叶变换找不到任何峰值，量子干涉无法发挥作用。对称密码和哈希函数之所以能在量子时代存活（仅需加倍密钥长度），正是因为它们被刻意设计为不具有任何可利用的代数结构。

周期性：区分量子可破与量子安全的分水岭

上述直觉可以提炼为一个更锐利的判据：一个密码方案是否会被 Shor 算法攻破，取决于其底层困难问题是否具有可被量子傅里叶变换提取的隐藏周期结构。

数学上，这类问题可统一表述为隐含子群问题（Hidden Subgroup Problem, HSP）：给定有限群 G 上的函数 f，若 f 在 G 的某个未知子群 H 的陪集上取常值（f(x) = f(y) 当且仅当 xH = yH），则 QFT 可以高效识别 H。整数分解与离散对数恰好是阿贝尔群上的 HSP——函数 f(x) = a^x mod N 的周期 r 定义了整数加法群 Z 中的子群 rZ，QFT 直接提取 r。椭圆曲线上的标量乘法 f(k) = kP 同理，周期就是点 P 的阶。

格基密码（LWE、MLWE、SIS）的底层问题——最短向量问题（SVP）和带噪声学习问题（LWE）——则完全不同。考虑 LWE 的核心运算：给定矩阵 A 和向量 b = As + e，其中 s 是秘密向量，e 是从高斯分布采样的噪声。这里没有任何周期性可言：噪声 e 使得输出 b 在格点附近形成一团弥散的高维高斯分布，不存在重复的波形，也不存在尖锐的频率峰值。QFT 在这样的信号上只能得到平坦的频谱——没有峰值可锁定，没有周期可提取。更准确地说，格上的某些问题可以归约为非阿贝尔群上的 HSP（如二面体群 HSP），目前已知的量子算法对此类问题仅能提供亚指数级别的加速，远达不到多项式时间。

这就是 NIST 在 2024 年将 ML-KEM 和 ML-DSA（均基于模格问题）作为首批后量子标准的根本原因：格的数学结构从本质上抵抗了 Shor 算法的攻击范式。掌握”有周期结构 → Shor 可破”与”无周期结构 → Shor 无效”这一对偶关系，是理解量子密码分析全局图景的核心钥匙。

从历史意义上看，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 门将量子比特顺序反转。

以 3 量子比特 QFT 为例，电路结构如下：

3-qubit QFT 电路:

q0 ──[H]──[R2]──[R3]──────────────────×──
              │      │                  │
q1 ───────── ● ─────┼───[H]──[R2]─────┼── 
                     │          │       │
q2 ────────────────  ● ──────── ● ─[H]─×──

其中 R_k 门的矩阵定义为:
R_k = [[1, 0], [0, exp(2πi/2^k)]]

即 R2 施加 π/2 相位旋转，R3 施加 π/4 相位旋转。
● 表示控制比特，连线表示受控操作。
最后的 × 是 SWAP 门，反转量子比特顺序。

对于一般的 n 量子比特 QFT，第 j 个量子比特（j = 0, 1, …, n-1）先经过一个 Hadamard 门，然后依次被第 j+1, j+2, …, n-1 个量子比特控制施加 R_2, R_3, …, R_{n-j} 旋转门。这一”Hadamard + 逐级受控旋转”的模式逐行重复，每行比上一行少一个受控门。

整个 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，那么：

1. 若 r 为偶数，计算 a^{r/2} mod N；
2. 检查 a^{r/2} ≢ -1 (mod N)；
3. 若以上两个条件满足，则 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。

阶求取（Order-Finding）的核心逻辑

理解 Shor 算法的关键在于深入理解为什么周期查找能够分解整数，以及 QFT 如何从叠加态中提取周期信息。

从分解到求阶。 整数分解问题可以归约到求阶问题：给定 N 和与 N 互素的 a，求满足 a^r ≡ 1 (mod N) 的最小正整数 r（即 a 在 (Z/NZ)* 中的阶）。归约过程依赖以下数论事实：若 r 是偶数且 a^{r/2} ≢ -1 (mod N)，则 a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) ≡ 0 (mod N)，因此 gcd(a^{r/2} - 1, N) 给出 N 的一个非平凡因子。定量分析表明，随机选取 a 后满足这两个条件的概率至少为 1/2（当 N 有 k 个不同的素因子时，概率为 1 - 1/2^{k-1}）。

QFT 如何提取周期。 这是 Shor 算法最精巧的部分。模幂运算后，量子态可以按 f(x) 的值分组：对于每个可能的输出值 s = a^{x_0} mod N，所有满足 f(x) = s 的 x 值形成一个等差数列 {x_0, x_0+r, x_0+2r, …}。对输入寄存器施加 QFT 后，这个等差数列的傅里叶变换会在频率空间中产生峰值——峰值位置恰好位于 Q/r 的整数倍处。直观理解：

模幂运算后的量子态（简化示意，假设 r=4, Q=16）:

输入寄存器:  |0⟩ |1⟩ |2⟩ |3⟩ |4⟩ |5⟩ |6⟩ |7⟩ |8⟩ |9⟩|10⟩|11⟩|12⟩|13⟩|14⟩|15⟩
             ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓   ↓    ↓    ↓    ↓    ↓    ↓
f(x) mod N:  s0   s1   s2   s3   s0   s1   s2   s3   s0   s1  s2   s3   s0   s1   s2   s3
                                  ↑         ↑         ↑        ↑
                                  重复！周期 r=4

假设测量输出寄存器得到 s0，输入寄存器坍缩为：
  (1/2)(|0⟩ + |4⟩ + |8⟩ + |12⟩)  — 等差数列，公差=r=4

对此施加 QFT，峰值出现在：
  c = 0, Q/r=4, 2Q/r=8, 3Q/r=12
  即 c = 0, 4, 8, 12

从测量值 c=4 和 Q=16，计算 c/Q = 4/16 = 1/4 → 分母=4 → r=4 ✓

这个例子展示了 Shor 算法的核心直觉：周期性的时域信号经过傅里叶变换后在频域中产生尖峰——QFT 就是量子版本的”频谱分析仪”。经典傅里叶变换需要 O(N log N) 时间处理 N 个样本，而 QFT 作用于 N 个叠加态仅需 O(log²N) 个量子门——这正是指数加速的来源。

连分数展开的角色。 测量得到的 c 只是 kQ/r 的近似值（因为 Q/r 通常不是整数）。连分数展开算法可以从 c/Q 的有理近似中高效提取 r。具体而言，将 c/Q 展开为连分数，其收敛子中分母不超过 N 的最佳有理近似的分母就是 r 的候选值。这一步是纯经典计算，复杂度为 O(n²)。

以一个具体例子说明连分数如何工作。假设 N = 15, a = 7, 真实周期 r = 4，输入寄存器大小 Q = 256。测量得到 c = 192，则：

连分数展开 c/Q = 192/256 = 0.75:

步骤 1: 0.75 = 0 + 1/(1/0.75)  → a0 = 0, 余数 = 1/0.75 = 1.333...
步骤 2: 1.333 = 1 + 1/(1/0.333) → a1 = 1, 余数 = 1/0.333 = 3.0
步骤 3: 3.0   = 3                → a2 = 3, 终止

连分数表示: [0; 1, 3]

收敛子序列:
  h0/k0 = 0/1
  h1/k1 = 1/1
  h2/k2 = 3/4  ← 分母 4 ≤ N，取 r = 4

验证: 7^4 mod 15 = 2401 mod 15 = 1 ✓
      r = 4 是偶数 ✓
      7^2 mod 15 = 49 mod 15 = 4 ≠ 14 (即 ≢ -1 mod 15) ✓
      gcd(4-1, 15) = gcd(3, 15) = 3  → 因子!
      gcd(4+1, 15) = gcd(5, 15) = 5  → 因子!
      15 = 3 × 5 ✓

若测量结果不够好（如 c = 0 或 r 的候选值不满足 a^r ≡ 1 mod N），则重新运行量子电路——平均仅需常数次重复即可成功。

整个算法中计算量最大的部分是量子模幂运算。对 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 位，同样被视为量子安全。

把 AES-128 和 AES-256 的 Grover 攻击放在一起对比，可以清晰看出”安全级别减半”的实际含义：

Grover 攻击 AES-128 vs AES-256 对比:

                        AES-128              AES-256
经典搜索空间             2^128                2^256
Grover 迭代次数          π/4 × 2^64          π/4 × 2^128
                         ≈ 1.44 × 10^19       ≈ 2.67 × 10^38
每次迭代 T 门数          ≈ 1.49 × 10^8       ≈ 2.35 × 10^8
所需逻辑量子比特         3169                 6681

假设 T 门速率 10^9 /秒（极为乐观）:
AES-128 单机时间         ≈ 2^{57} 秒 ≈ 46 亿年
AES-256 单机时间         ≈ 2^{86} 秒 ≈ 2.4 × 10^{18} 年

结论: AES-128 的 Grover 攻击在物理上已经不可行（46 亿年 ≈ 地球年龄），
     但 64 位安全性在密码学标准中被视为"不足"——
     因为它意味着假想的大规模并行量子计算可能构成威胁。
     AES-256 的 128 位量子安全性则提供了充裕的安全余量。

NIST 后量子安全级别。 NIST 在其后量子密码标准化过程中定义了五个安全级别，以 Grover 攻击对称密码的代价作为锚点：

NIST 安全级别定义:

级别 I:   至少等同于 Grover 攻击 AES-128 的难度（2^64 量子操作）
级别 II:  至少等同于碰撞搜索 SHA-256 的难度
级别 III: 至少等同于 Grover 攻击 AES-192 的难度（2^96 量子操作）
级别 IV:  至少等同于碰撞搜索 SHA-384 的难度
级别 V:   至少等同于 Grover 攻击 AES-256 的难度（2^128 量子操作）

标准化方案对应:
  ML-KEM-512  / ML-DSA-44  → 级别 I
  ML-KEM-768  / ML-DSA-65  → 级别 III
  ML-KEM-1024 / ML-DSA-87  → 级别 V

实际含义: 级别 I 已足以抵抗所有已知量子攻击；
         级别 V 提供最高安全余量，适用于需要数十年保密性的场景。

对于散列函数（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 攻击。这比公钥密码系统需要完全更换算法的情况要温和得多。

具体数值案例：AES-256 与 ML-KEM-768

为了让量子威胁的量化分析更加具体，我们以 AES-256 和 ML-KEM-768（NIST 安全级别 3）为例，计算 Grover 攻击的实际资源需求。

AES-256 的 Grover 攻击。 攻击者的目标是从已知的明文-密文对 (m, c) 中恢复 256 位密钥 k，使得 AES-256(k, m) = c。Grover 搜索需要 O(2^{128}) 次迭代，每次迭代在量子电路内执行一次 AES-256 加密和一次比较。Grassl、Langenberg 和 Roetteler 在 2016 年估计了量子 AES 电路的资源需求：

AES-256 量子电路资源估计（Grassl et al. 2016）:

· 所需量子比特数:     6681 个逻辑量子比特
· 每次迭代的 T 门数:  约 2.35 × 10^8
· Grover 迭代次数:    π/4 × 2^128 ≈ 2.67 × 10^38
· 总 T 门数:          约 2^{86.2}

假设 T 门执行速率为 10^9 /秒（极为乐观的假设）:
· 单台量子计算机运行时间: 2^{86.2} / 10^9 ≈ 2^{56.2} 秒 ≈ 23 亿年

结论: 即使 Grover 将搜索空间从 2^{256} 降到 2^{128}，
      AES-256 在量子计算时代仍然是安全的。

ML-KEM-768 的安全性参数。 ML-KEM-768 的安全性基于 Module-LWE 问题的困难性，NIST 将其分类为安全级别 3（等效于 AES-192 的经典安全性）。量子攻击 MLWE 的最优已知方法是基于格的 BKZ 算法变体，其量子复杂度远高于 Grover 搜索。具体而言：

ML-KEM-768 参数与量子安全性:

· 模数 q = 3329
· 多项式维度 n = 256, 模块秩 k = 3
· 公钥大小: 1184 字节
· 密文大小: 1088 字节
· 共享密钥: 32 字节

量子攻击估计（primal 攻击，BKZ + Grover 加速）:
· 经典安全性: 约 182 位（Core-SVP 模型）
· 量子安全性: 约 164 位（量子筛法模型）
· NIST 分类: 安全级别 3（≥ AES-192 等效）

对比: 量子计算机攻击 ML-KEM-768 需要的量子资源
      远远超过攻击 ECDH P-256 所需的约 2330 个逻辑量子比特。
      这正是后量子密码的意义——将量子攻击的成本重新拉回到不可行的范围。

这两个案例清晰地展示了量子威胁的不对称性：Shor 算法使公钥密码（如 ECDH P-256）的安全性归零，而 Grover 算法仅将对称密码（如 AES-256）的安全性减半——AES-256 仍然安全，但 ECDH 必须被替换。

八、量子资源估计

理解量子威胁的紧迫程度，需要对实际破解密码系统所需的量子资源有清晰的认识。这里涉及几个关键概念：逻辑量子比特（logical qubits）、物理量子比特（physical qubits）、T 门深度（T-gate depth）以及量子纠错开销（error correction overhead）。

逻辑量子比特是算法层面的量子比特，执行精确的量子运算。物理量子比特则是实际硬件中带有噪声的量子比特。为了实现容错计算，需要使用量子纠错码将多个物理量子比特编码为一个逻辑量子比特。目前最有前景的纠错方案是表面码（surface code），其编码率随所需纠错能力的增加而降低。

以破解 RSA-2048 为例，Gidney 和 Ekera 在 2021 年给出了迄今最优化的资源估计：

• 逻辑量子比特：约 4000 个（使用窗口化算术和测量-反馈优化）
• T 门数量：约 10^{10}（百亿级别，通过 Toffoli 门计数约 3 × 10^8 再乘以 T 门分解因子）
• 物理量子比特：约 2000 万个（假设表面码距离 d ≈ 27，物理错误率 p ≈ 10^{-3}）
• 运行时间：约 8 小时（假设门操作时间约 1 微秒、魔法态蒸馏工厂并行运行）

对于破解 ECC P-256：

• 逻辑量子比特：约 2300 个
• 物理量子比特：约 900 万个
• 运行时间：约数小时

当前量子硬件的状况与上述需求之间存在巨大鸿沟。截至目前，领先的量子计算平台包括：IBM 的超导量子处理器（约 1000 多个物理量子比特）、Google 的 Sycamore 和 Willow 系列处理器、IonQ 的离子阱处理器等。这些处理器的物理量子比特数量比破解 RSA-2048 所需的少三到四个数量级，且尚未实现真正的容错计算。

当前量子分解的实际记录。 在真实量子硬件上完成的最大整数分解是 21 = 3 x 7（使用编译优化后的 Shor 算法变体，仅需数个量子比特）。一些团队声称用量子退火或混合方法分解了更大的数（如 RSA-250 级别），但这些工作依赖大量经典预处理，并非真正的 Shor 算法实现。从”分解 21”到”分解 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 算法的存在意味着我们必须以前所未有的紧迫感推进密码体系的演进。无论量子计算机的确切到来时间如何，提前做好准备的代价远低于被动应对的损失。密码学的历史告诉我们：算法的瓦解往往比预期来得更快，而迁移的过程总是比预想的更慢。现在就行动，才是最明智的选择。

十、量子算法影响与应对策略矩阵

下表从算法、受影响密码体制和应对策略三个维度，系统梳理量子计算对现有密码基础设施的冲击全景。

笔者认为，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 篇

← 上一篇：量子计算基础 | 系列目录 | 下一篇：后量子密码总览 →