📚 课程目录第4章经典密码的末日

4、经典密码的末日：Shor算法如何破解RSA？Grover算法如何加速暴力破解？

好，咱们今天聊点刺激的。

经典密码学里，RSA 和 AES 一直是顶梁柱。RSA 靠大整数分解保平安，AES 靠暴力穷举撑场面。但量子计算一出来，这两根柱子就摇摇欲坠了。

我个人习惯把量子算法对经典密码的冲击分成两类：一类是「釜底抽薪」，直接瓦解数学难题；另一类是「加速平推」，让暴力破解变得可行。Shor 算法属于前者，Grover 算法属于后者。

4.1 Shor算法：RSA的终结者

RSA 的安全性建立在「大整数分解很难」这个假设上。给你两个大素数 p 和 q，乘起来得到 n 很容易；但给你 n，反推出 p 和 q，经典计算机几乎做不到。

Shor 算法在 1994 年被提出，它能在多项式时间内完成大整数分解。这意味着什么？2048 位的 RSA，经典计算机需要几十亿年，Shor 算法可能只需要几小时甚至几分钟。

核心逻辑：Shor 算法把分解问题转化为「求函数周期」问题，然后用量子傅里叶变换（QFT）快速找到周期。

具体步骤我简单拆一下：

随机选一个数 a，满足 1 < a < n，且 gcd(a, n) = 1。
构造周期函数 f(x) = a^x mod n。这个函数在经典计算机上算很慢，但量子计算机可以并行计算所有 x 对应的 f(x)。
用量子傅里叶变换找周期 r。这是 Shor 算法的核心——QFT 能把叠加态中的周期信息提取出来。
得到周期 r 后，如果 r 是偶数，计算 gcd(a^r/2 - 1, n) 和 gcd(a^r/2 + 1, n)，就能得到 p 和 q。

我在做 IoT 安全评估时，遇到过不少设备还在用 1024 位的 RSA 证书。说实话，经典计算机上破解它都只是时间问题，更别提量子计算机了。嗯，这里要注意：Shor 算法需要逻辑量子比特数大约是 2n 个，破解 2048 位 RSA 大概需要 4096 个逻辑量子比特。目前物理量子比特已经上千了，但逻辑量子比特的纠错开销还很大。

避坑指南：我曾经见过有人把「量子比特数」和「逻辑量子比特数」混为一谈。物理量子比特需要纠错才能变成逻辑量子比特，比例通常是 1000:1 甚至更高。所以别看到「1000 量子比特」就以为 RSA 马上完蛋，还早着呢。

4.2 Grover算法：暴力破解的加速器

Grover 算法是另一种量子算法，它不直接破解数学难题，而是加速搜索过程。

经典暴力破解：在 N 个可能密钥里找正确的一个，平均需要尝试 N/2 次。Grover 算法只需要大约 √N 次。你想想看，128 位 AES 密钥，经典需要 2¹²⁷ 次尝试，Grover 只需要 2⁶⁴ 次。

关键结论：Grover 算法把暴力破解的复杂度从 O(N) 降到了 O(√N)。对于对称加密，这意味着密钥长度需要翻倍才能维持同等安全强度。

Grover 算法的核心思想是「振幅放大」。它通过反复应用两个操作——Oracle 和 Diffusion——逐步放大目标状态的振幅，最终以高概率测量到正确答案。

我举个例子：假设你有一个无序数据库，里面有 100 万个条目，你要找其中一个。经典方法平均要查 50 万次。Grover 算法只需要大约 1000 次。这个加速效果在密钥空间越大时越明显。

注意：Grover 算法对对称加密的威胁是「降级」而非「瓦解」。AES-128 被降到大约 64 位安全强度，AES-256 被降到大约 128 位。所以 NIST 建议后量子时代对称加密至少用 256 位密钥。

4.3 两种算法的对比

我把 Shor 和 Grover 的核心差异整理了一下，方便你对照：

维度	Shor 算法	Grover 算法
攻击目标	公钥密码（RSA、ECC、DSA）	对称密码（AES、SM4）、哈希函数
攻击方式	瓦解数学难题（分解、离散对数）	加速暴力搜索
复杂度变化	指数级 → 多项式级	指数级 → 平方根级
威胁程度	致命（完全破解）	降级（需翻倍密钥长度）
所需量子资源	数千逻辑量子比特	数百逻辑量子比特

说白了，Shor 算法是「降维打击」，Grover 算法是「加速平推」。两者对 IoT 的影响完全不同：公钥密码需要彻底替换，对称密码只需要升级密钥长度。

4.4 对IoT设备的实际影响

IoT 设备资源受限，很多还在用低强度的密码算法。我评估过一批智能家居设备，发现以下问题很普遍：

RSA-1024 证书：经典计算机上已经不安全，量子计算机下更是秒破。
ECC-160 密钥：Shor 算法的变体可以破解椭圆曲线离散对数问题。
AES-128 加密：Grover 算法将其安全强度降到 64 位，对长生命周期设备风险很大。
SHA-1 哈希：虽然 Grover 能加速碰撞搜索，但 SHA-1 本身已有经典碰撞攻击。

我的建议：如果你现在设计 IoT 产品，对称加密至少用 AES-256，公钥加密考虑迁移到 CRYSTALS-Kyber 或 Dilithium。别等到量子计算机成熟了再改，那会儿固件升级都来不及。

4.5 知识体系总览

下面这张图把 Shor 和 Grover 的核心逻辑、攻击目标、以及 IoT 迁移路径串起来了：

这张图把 Shor 和 Grover 的攻击目标、复杂度变化、威胁等级以及 IoT 迁移路径都串起来了。你可以看到，Shor 算法直接威胁公钥密码体系，而 Grover 算法主要影响对称密码和哈希函数。IoT 设备的迁移策略也因此不同：公钥需要彻底替换算法，对称加密则可以通过增加密钥长度来应对。

4.6 小结

Shor 算法和 Grover 算法是量子计算对经典密码学的两把利刃。Shor 直接瓦解 RSA 和 ECC 的数学基础，Grover 则让暴力破解变得更快。对于 IoT 设备，这意味着：

公钥密码必须迁移到后量子算法（如 CRYSTALS-Kyber、Dilithium）。
对称密码至少使用 256 位密钥。
哈希函数需要关注输出长度，至少 256 位以上。