量子计算机不会对 128 位对称密钥构成威胁

# 量子计算机对 128 位对称密钥不构成威胁 Source: https://words.filippo.io/128-bits/ 密码学相关量子计算机 (https://words.filippo.io/crqc-timeline/) 日益迫近的威胁，使得替换目前部署的非对称加密基元——密钥交换（ECDH）和数字签名（RSA、ECDSA、EdDSA）——变得刻不容缓，因为它们易受 Shor 量子算法 (https://en.wikipedia.org/wiki/Shor's_algorithm) 的影响。然而，这并不会影响现有的对称加密算法（AES、SHA-2、SHA-3）或其密钥长度。 一个常见的误解是，量子计算机将“减半”对称密钥的安全性，即需要 256 位密钥才能提供 128 位的安全性。这种理解并不准确，并未反映量子算法提供的加速比，也未见于任何合规性要求，反而可能分散我们用于真正必要的后量子过渡工作的精力与注意力。该误解通常源于对不同量子算法——Grover 算法 (https://en.wikipedia.org/wiki/Grover%27s_algorithm) 适用性的误读。 **AES-128 对量子计算机安全。SHA-256 对量子计算机安全。在后量子过渡过程中，无需更改任何对称密钥长度。**这是专家和相关标准制定机构几乎达成的共识，必须向整个 IT 社区传播。本文的其余部分将从技术角度和权威引用两方面支持这一观点。 ## Grover 算法的加速效应 Grover 算法是一种量子算法，它允许通过对非结构化函数 $f$ 进行 $\pi/4 \times \sqrt{N}$ 次查询，在大小为 $N$ 的输入空间中搜索到“正确答案”。 人们常据此认为，Grover 算法可以在 $2^{64}$ 个“单位时间”内破解 AES-128 密钥。但这在实际中并不成立，因为以单一连续线程运行此类攻击需要数十万年，而并行化只会导致总成本上升。 关于 Grover 算法，有几个关键点需要理解： - 函数预言机（oracle）$f$ 必须作为量子电路的一部分实现； - 预言机的调用必须按顺序依次执行； - 关键在于，除了划分搜索空间外，没有其他更好的方法来并行化该攻击（Zalka, 1997 (https://arxiv.org/abs/quant-ph/9711070)）。 为什么最后一点如此重要？因为与普通的暴力破解攻击（属于“embarrassingly parallel”即极易并行的任务）不同，划分搜索空间会削弱 Grover 算法的二次加速效果。 以一个 64 位密钥的经典暴力破解为例，每次尝试耗时 5 ns（约 3 GHz 频率下的 16 个周期）。仅在单个 CPU 上运行就需要近 $2^{64} \times 5 \text{ ns} \approx 3,000 \text{ 年}$。因此我们将其并行化，分摊到 $2^{16} = 65,536$ 个 CPU 上，每个 CPU 探索 $2^{(64-16)} = 2^{48}$ 个密钥，耗时略多于 $2^{48} \times 5 \text{ ns} \approx 16 \text{ 天}$。请注意，系统完成的工作总量 $2^{16} \times 2^{48} = 2^{64}$ 并未改变。 这就是我们认为 64 位密钥不安全的原因：因为它们可以被高效地并行搜索。如果攻击必须以串行方式执行，则根本不存在风险。1 (https://words.filippo.io/128-bits/#fn:dhoracle) 让我们对 128 位密钥尝试同样的 Grover 攻击。同样，连续执行 $2^{\sqrt{128}} = 2^{64}$ 次操作是不可行的，因此我们将攻击并行化到 $2^{16}$ 台量子计算机上，每台探索 $2^{(128-16)} = 2^{112}$ 个密钥。每个实例所需的工作量为 $\sqrt{2^{128} / 2^{16}} = 2^{56}$。请注意，这可不是 $2^{48}$！ 平方根内的 $2^{16}$ 倍搜索空间缩减因子，仅为每个实例节省了 $2^8$ 工作量，而在经典计算中则直接节省了完整的 $2^{16}$ 倍。 由于我们进行了并行化，整个系统的总工作量从 $2^{64}$ **增加**到了 $2^{56} \times 2^{16} = 2^{72}$，在此过程中稀释了二次加速效果。 ### 具体计算分析 这让我们直观地理解了为什么 Grover 算法难以并行化。要判断它是否仍是威胁，我们需要用具体的数量级来跑一遍数据。 首先，我们需要确定能够连续执行多少个操作（或量子门）。为保守起见，假设我们拥有类似超导量子比特的高速时钟量子架构，且单个门操作耗时 1 μs。2 (https://words.filippo.io/128-bits/#fn:speed) 如果我们愿意让攻击持续运行（期间无停电或保真度损失[!]）十年，这就给出了最大门序列数或“深度（depth）”： $10 \text{ 年} / 1 \text{ μs} \approx 2^{48}$ 接下来，我们需要知道在量子电路中执行 AES-128 需要多少连续的门操作。Liao 和 Luo（2025）(https://eprint.iacr.org/2025/1494) 提供了一个高度优化的 AES-128 Grover 预言机，其深度为 $2^{32}$ 个 T-门（电路“宽度”为 724，大致可理解为并行运行的逻辑量子比特数）。 现在我们可以求解保持每个实例深度不超过 $2^{48}$（即在假设的快速完美量子计算机上十年内完成）的最低并行因子： $\pi / 4 \times \sqrt{2^{128} / x} \times 2^{32} = 2^{48}$ $x \approx 2^{47}$ **这意味着，使用 Grover 算法破解 AES-128，需要 140 万亿个各含 724 个逻辑量子比特的量子电路并行运行 10 年。** 衡量该攻击成本的另一种方式是 **DW 成本**（深度 × 宽度的乘积），大致相当于讨论经典计算的周期数与核心数的乘积。 $\pi / 4 \times \sqrt{2^{128} / 2^{47}} \times 2^{32} \times 724 \times 2^{47} \approx 2^{104.5}$ 值得注意的是，与多年来大幅改进的 Shor 算法实例（及量子纠错）不同，该公式中的项已很少能有进一步提升空间。唯一可优化的两项是 AES-128 Grover 预言机的深度（$2^{32}$）和宽度（724），但它们仅占总成本的 17 个比特，进一步优化空间可能已非常有限。Liao 和 Luo（2025）(https://eprint.iacr.org/2025/1494) 在 Grassl 等人（2015）(https://arxiv.org/abs/1512.04965) 的最初估计基础上削减了 7.5 个比特，并在 Jaques 等人（2019）(https://eprint.iacr.org/2019/1146) 最早的 Grover 专项估计基础上削减了 1.5 个比特。 ## 与 Shor 算法的比较 说到 Shor 算法，这与近期讨论的针对 256 位椭圆曲线的量子攻击相比如何？毕竟，也有人认为或曾经认为那些攻击不可行，但我一直在主张认真对待它们 (https://words.filippo.io/crqc-timeline/)。 Babbush 等人（2026）(https://arxiv.org/abs/2603.28846) 声称仅需 $70\text{M} \approx 2^{26}$ 个门即可执行一次 Shor 算法。在以“快速”门时间 10 μs 实现的架构上（比我们上述保守假设慢了 10 倍），这需要几分钟即可完成。 $2^{104.5} / 2^{26} = 2^{78.5}$ **使用 Grover 算法破解 AES-128 的成本，是使用 Shor 算法破解 256 位椭圆曲线成本的 430 垓（4.3 × 10²³）倍。** ## NIST 的立场一致 美国国家标准与技术研究院（NIST）是负责举办后量子密码国际竞争并编写 ML-KEM 和 ML-DSA 规范文档的标准制定机构。 NIST 不仅认为 AES-128 是安全的，还将其设为后量子基元安全性评估的*基准* (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization/Evaluation-Criteria/Security-(Evaluation-Criteria))。根据定义，AES-128 属于第 1 类 (https://words.filippo.io/128-bits/#fn:cat1) 后量子算法。 在论证使用 AES-128 的合理性时，NIST 引用了我们上文解释的相同观察结果，并引入了 *MAXDEPTH* 的概念，这正好就是迫使并行化并限制 Grover 二次加速效应的最大串行计算量。 > It is worth noting that the security categories based on these reference primitives provide substantially more quantum security than a naïve analysis might suggest\. For example, categories 1, 3 and 5 are defined in terms of block ciphers, which can be broken using Grover’s algorithm, with a quadratic quantum speedup\. But Grover’s algorithm requires a long\-running serial computation, which is difficult to implement in practice\. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramati\[c\]\. > > 值得注意的是，基于这些参考基元的安全类别所提供的量子安全性，远高于朴素分析所暗示的水平。例如，第 1、3 和 5 类基于分组密码定义，而分组密码可通过 Grover 算法结合二次量子加速被破解。但 Grover 算法需要长时间运行的串行计算，这在实践中难以实现。在实际攻击中，必须并行运行许多较小规模的算法实例，这使得量子加速效果不再那么显目[c]。 NIST 的计算采用了优化程度较低（因此也更为乐观/不那么保守）的 AES 量子电路（来自 Grassl 等人 2015 (https://arxiv.org/abs/1512.04965)，而非 Liao 和 Luo 2025 (https://eprint.iacr.org/2025/1494)），但使用了更快的逻辑门速度（因此更符合实际/更保守）。尽管如此，其结果仍落在同一数量级，并得出了相同的结论。 进一步的证据来自《NIST IR 8547 ipd (https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8547.ipd.pdf)》*《向后量子密码标准过渡》*。该文件规定自 2035 年起禁止所有易受量子攻击的算法。然而，它在第 4.1.3 节中再次重申，所有 AES 密钥长度均继续允许使用。 > NIST’s existing standards in symmetric cryptography — including hash functions, XOFs, block ciphers, KDFs, and DRBGs — are significantly less vulnerable to known quantum attacks than the public\-key cryptography standards in SP 800\-56A, SP 800\-56B, and FIPS 186\. In particular, all NIST\-approved symmetric primitives that provide at least 128 bits of classical security are believed to meet the requirements of at least Category 1 security within the system of five security strength categories for evaluating parameter sets in the NIST PQC standardization process \(see Table 1\)\. > > NIST 现有的对称密码标准——包括哈希函数、XOF、分组密码、KDF 和 DRBG——相较于 SP 800-56A、SP 800-56B 和 FIPS 186 中的公钥密码标准，对已知量子攻击的脆弱性显著更低。特别是，所有能提供至少 128 位经典安全性的 NIST 认证对称基元，预计均能满足 NIST PQC 标准化流程中五个安全强度类别评估参数集的第 1 类及以上安全要求（见表 1）。 最后，在《后量子密码常见问题解答 (https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs)》中，明确回答了“我们是否应该加倍 AES 密钥长度？”这一问题。（加粗部分为我强调。） > To protect against the threat of quantum computers, should we double the key length for AES now? \(added 11/18/18\) Grover’s algorithm allows a quantum computer to perform a brute force key search using quadratically fewer steps than would be required classically\. Taken at face value, this suggests that an attacker with access to a quantum computer might be able to attack a symmetric cipher with a key up to twice as long as could be attacked by an attacker with access only to classical computers\. However there are a number of mitigating factors suggesting that Grover’s algorithm will not speed up brute force key search as dramatically as one might suspect from this result\. First of all, quantum computing hardware will likely be more expensive to build and use than classical hardware\. Additionally, it was proven by Zalka in 1997 that in order to obtain the full quadratic speedup, all the steps of Grover’s algorithm must be performed in series\. In the real world, where attacks on cryptography use massively parallel processing, the advantage of Grover’s algorithm will be smaller\. Taking these mitigating factors into account,**it is quite likely that Grover’s algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure for decades to come**\. Furthermore, even if quantum computers turn out to be much less expensive than anticipated, the known difficulty of parallelizing Grover’s algorithm suggests that both AES 192 and AES 256 will still be safe for a very long time\. This of course assumes that no new cryptographic weaknesses, either with respect to classical or quantum cryptanalysis, are found in AES\. Based on such understanding,**current applications can continue to use AES with key sizes 128, 192, or 256 bits**\. NIST will issue guidance regarding any transitions of symmetric key algorithms and hash functions to protect against threats from quantum computers when we can foresee a transition need\. Until then, users should follow the recommendations and guidelines NIST has already issued\. In particular, anything with less than 112 bits of classical security should not be used\. > > 为了保护自身免受量子计算机的威胁，我们现在就应该将 AES 的密钥长度加倍吗？（添加于 18/11/18）Grover 算法允许量子计算机以比经典计算少得多的步骤（二次减少）执行暴力密钥搜索。乍看之下，这表明拥有量子计算机的攻击者可能能够破解对称密码，其密钥长度可达仅拥有经典计算机的攻击者所能破解密钥的两倍。然而，存在多种缓解因素表明，Grover 算法不会如该结果所暗示的那样极大地加速暴力密钥搜索。首先，量子计算机硬件的构建和使用成本可能高于经典硬件。此外，Zalka 在 1997 年已证明，为了获得完全的二次加速，Grover 算法的所有步骤必须以串行方式执行。在现实世界中，密码攻击通常采用大规模并行处理，此时 Grover 算法的优势将大打折扣。综合考虑这些缓解因素，**Grover 算法在攻击 AES 时极有可能提供极少或根本无法带来优势，且 AES-128 在未来数十年内仍将保持安全**。此外，即使量子计算机的实际成本远低于预期，已知 Grover 算法并行化的困难也表明，AES-192 和 AES-256 在很长时间内仍然安全。当然，这前提是尚未在 AES 中发现新的针对经典或量子密码分析的弱点。基于此认知，**当前应用完全可以继续使用密钥长度为 128、192 或 256 位的 AES**。当我们预见过渡需求时，NIST 将发布有关对称密钥算法和哈希函数过渡的指导方针以防范量子计算机威胁。在此之前，用户应遵循 NIST 已发布的建议和指南。特别是，任何经典安全性低于 112 位的算法均不应使用。 NIST 对此没有任何含糊其辞：128 位密钥完全没问题。 ## BSI 的立场一致 其他标准制定机构怎么看呢？德国联邦信息安全办公室近期发布了《BSI TR-02102-1 (https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TG02102/BSI-TR-02102-1.pdf?__blob=publicationFile&v=14)》*《密码机制：推荐意见与密钥长度》*，其中包含了“后量子密码领域的更新”。 文中顺带提及了 Grover 算法，虽然不如 NIST 结论那样斩钉截铁，但最终得出了相同的结论： > The following block ciphers are recommended for use in new cryptographic systems: AES\-128, AES\-192, AES\-256 > > 推荐在新密码系统中使用以下分组密码：AES-128、AES-192、AES-256。 在同一份文件中，他们建议比 NIST 更早地从易受量子攻击的基元（ notably 不包括 AES-128）进行过渡： > The sole use of classic key agreement mechanisms is only recommended until the end of 2031, see also Section 2\.3\. > > 仅建议使用经典密钥协商机制至 2031 年底，详见第 2.3 节。 ## Samuel Jaques 的观点一致 Samuel Jaques 是滑铁卢大学组合数学与优化系的助理教授，专注于密码学与量子计算领域。你可能熟悉他的《量子计算图谱 (https://sam-jaques.appspot.com/quantum_landscape)》。 在上述所有计算完成后，我发现了这份 2024 年的幻灯片演示 (https://ches.iacr.org/2024/Jaques_CHES_2024.pdf)。起初我觉得自己有点好笑，毕竟两年后我几乎重做了同样的工作，且缺乏该领域的深厚专业知识。但实际上，结论的高度吻合令人鼓舞：误差范围足够宽，猜测和优化因素的影响足够小，以至于我们反复得出了等效的结论。 一张幻灯片显示：“误区：由于平方根加速效应，我们应该将密钥长度加倍。” 一张幻灯片显示：“基于表面码的 AES-128 Grover 搜索永远不会成功。” 他谈到了构建哪怕单个逻辑量子比特的难度，我在上文忽略了这一点，因为我们假设的是一个可扩展量子纠错*确实能实现*的世界，否则我们根本无需担心非对称密码学的安危。 他还谈到了退相干问题，我只在保守假设中提到量子计算机实际上几乎不可能不间断运行十年这一点时有所提及。 他提出了一个很好的观点：优化 Grover 预言机电路的正确指标应该是 深度² × 宽度，因为深度既影响成本，也决定了是否会触及最大深度上限。这表明 Liao 和 Luo（2025）(https://eprint.iacr.org/2025/1494) 的电路可能并非最优，他转而使用了 Jang 等人（2022）(https://eprint.iacr.org/2022/683) 的方案，但得出的结果依然非常接近。 最后，他指出在表面码架构中，每个逻辑 T-门需要 $2^{16}$ 次物理操作，因此在得出实用的资源估算之前，公式中仍存在缺失项。 ## 既然这样，为什么不干脆切换过去求个安心？ 整个后量子过渡旨在缓解投机性风险，那为何不在对称密钥上也图个“安全”呢？因为资源是有限的，变更会产生成本，且协调至关重要。 业界正急于部署后量子密码，因为专家们在告