肖尔算法详解：它能破解比特币吗？

肖尔算法（Shor’s algorithm）是量子计算（quantum computing）被视为现代密码学严肃的长期威胁的主要原因之一。

大多数公钥密码学依赖一种简单的不对称性：有些数学运算很容易执行，但在经典计算机上极难逆向求解。

RSA 依赖大合数分解的困难性。Diffie–Hellman、椭圆曲线数字签名算法（ECDSA）、Schnorr 签名和椭圆曲线密码学，则依赖求解离散对数（discrete-logarithm）问题的困难性。这些数学问题各不相同，但具有相同的基本安全假设：经典计算机无法以足以造成实际影响的速度完成逆向求解。

肖尔算法打破了这一假设。

数学家彼得·肖尔（Peter Shor）于 1994 年发表的肖尔算法表明，一台足够大、具备容错能力的量子计算机，能够高效解决整数分解和离散对数问题。这意味着，它可以破解 RSA、Diffie–Hellman、椭圆曲线密码学，以及用于授权比特币交易的签名方案。

威胁是真实的，但尚未到来。

本指南将解释肖尔算法的作用、工作原理、它为何威胁公钥密码学、能否破解比特币，以及今天还有哪些障碍阻止这种攻击发生。

什么是肖尔算法？

肖尔算法是一种量子算法，解决某些数学问题的速度远快于任何已知的经典算法。

它最广为人知的用途是因数分解。给定一个由两个素数相乘得到的大数，肖尔算法可以在足够强大的量子计算机上，高效还原这些素因数。这就是它能破解 RSA 的原因。

但肖尔算法并不只是因数分解算法。

它还有一个求解离散对数的版本，这才是与 Diffie–Hellman、椭圆曲线密码学、ECDSA、Schnorr 签名和比特币相关的版本。

简单来说：

整数分解可以破解 RSA。

离散对数求解可以破解 Diffie–Hellman、ECDSA、Schnorr 签名和椭圆曲线密码学。

比特币面临的是第二种攻击，而非第一种。

比特币不使用 RSA，而是使用 secp256k1，这是一条用于数字签名的椭圆曲线。对比特币的量子攻击并不是对比特币密钥做因数分解，而是利用肖尔离散对数算法，从公开已知的公钥中还原私钥。

肖尔算法为何重要？

肖尔算法之所以重要，是因为公钥密码学无处不在。

它保护加密的 Web 流量、保障软件更新、验证服务器身份、支持数字签名，并授权区块链交易。如果一台足够大的量子计算机能够以密码学应用所需的规模运行肖尔算法，今天许多公钥系统就会变得不安全。

对 RSA 而言，攻击过程很直接：分解公开模数，还原私钥，破解加密或签名。

对椭圆曲线系统而言，攻击方式有所不同：求解椭圆曲线离散对数问题，从公钥还原私钥，然后伪造签名。

第二种情况才与比特币有关。

比特币资金并不是通过通常意义上的加密来保护，而是通过数字签名保护。钱包要花费比特币，就必须生成有效签名，证明自己控制着相关私钥。如果量子计算机能够从对应公钥推导出私钥，就可以生成有效签名并转走资金。

这才是比特币真正面临的量子威胁：签名伪造，而非解密。

肖尔算法如何工作？

肖尔因数分解算法大致分为三个步骤：

1. 选择一个合适的随机数。
2. 使用量子计算机寻找一个重复数学序列的周期。
3. 使用普通的经典算术求出因数。

只有寻找周期这一步需要量子计算机。

这一步正是突破所在。在密码学使用的规模下，经典计算机没有已知的高效方法找到相关周期。量子计算机则可以利用叠加（superposition）、干涉（interference）和量子傅里叶变换（quantum Fourier transform）提取周期。

用一个小例子最容易理解这个思路。

肖尔算法如何分解一个数？

假设我们要分解：

N = 21

任何人都能手算分解 21，但同样的结构也适用于大得多的数。

第一步：随机选择一个互素数

随机选择一个小于 N、与 N 没有公因数的数 x。

令：

x = 2

因为 2 和 21 没有公因数，所以它们互素。

第二步：寻找周期

现在计算序列：

x^k mod N

取 x = 2、N = 21：

2^1 mod 21 = 2

2^2 mod 21 = 4

2^3 mod 21 = 8

2^4 mod 21 = 16

2^5 mod 21 = 11

2^6 mod 21 = 1

序列回到了 1，因此周期为：

r = 6

周期是关键。一旦知道周期，通常就能用经典算术求出因数。

第三步：求出因数

如果周期 r 是偶数，并且 x^(r/2) 在模 N 意义下不与 -1 同余，就可以继续。

在这里：

r = 6

r / 2 = 3

x^(r/2) = 2^3 = 8

因为 8 在模 21 意义下不与 -1 同余，也就是不等于 20，所以我们计算：

gcd(2^3 - 1, 21) = gcd(7, 21) = 7

gcd(2^3 + 1, 21) = gcd(9, 21) = 3

因此，21 的因数为：

3 和 7

如果周期是奇数，或算术步骤未能成功，肖尔算法只需换一个随机值重试。对于大数，这个过程仍能以高概率高效成功。

肖尔算法为什么比经典因数分解更快？

肖尔算法更快，是因为它将因数分解转化为周期查找问题，再利用量子力学高效找到周期。

经典计算机必须用经典计算寻找数学结构。在密码学密钥的规模下，这种搜索会变得不可行。最好的经典算法虽然非常强大，但其效率随规模增长的表现，仍不足以破解长度选择恰当的 RSA 或椭圆曲线密钥。

量子计算机的工作方式不同。

它可以在许多可能输入的叠加态上计算函数。但重点并不是它简单地“同时尝试所有答案”，这种说法会产生误导。真正有用的能力来自干涉。

肖尔算法安排量子计算，使无关路径相互抵消，而与隐藏周期相关的值得到增强。随后，量子傅里叶变换从量子态中提取周期结构。

测量通常不会直接给出周期，而是产生一个与周期相关的值。经典后处理通常采用连分数（continued fractions），以高概率还原周期。

正是这种结合带来了加速。

量子计算机找到隐藏结构，经典计算机再把结构转化为答案。

肖尔算法得到证明了吗？

是的，肖尔算法已在数学上得到证明。

对于该算法能否在理想、规模足够大的量子计算机上工作，并不存在实质性疑问。悬而未决的问题是：能否制造出规模足够大、足够稳定、纠错能力足够强的量子硬件，用来攻击真实的密码学目标。

迄今为止，肖尔算法只在小规模例子中得到演示。早期实验分解了 15，后来的演示则实现了 21 等小数的分解。

这些实验作为概念验证很重要，但并不是密码学攻击。

许多被广泛报道的较大数的量子“因数分解”，还依赖捷径、经专门编译的电路或预先知道答案。不能将它们与可扩展地运行肖尔算法、攻击 RSA-2048、secp256k1 或任何现实密码学目标混为一谈。

截至 2026 年，尚无量子计算机以具有密码学意义的规模运行过肖尔算法。

肖尔算法今天能实际用于攻击吗？

不能。今天，肖尔算法还无法实际用于攻击现实中的密码系统。

原因很简单：目前还不存在密码学相关量子计算机（Cryptographically Relevant Quantum Computer，CRQC）。

CRQC 是规模、稳定性和纠错能力足以破解广泛部署的公钥密码学的量子计算机。当前的量子计算机距离这一门槛还很远。

主要差距在于容错能力。

今天的物理量子比特（physical qubits）噪声很大，会发生错误、失去相干性，无法可靠运行密码学攻击所需的深电路。要大规模运行肖尔算法，必须将物理量子比特组合成经过纠错的逻辑量子比特（logical qubits）。

逻辑量子比特比物理量子比特可靠得多，但通常需要许多物理量子比特才能创建并维持。

正是这种开销，使单纯的量子比特数量可能产生误导。拥有数千个物理量子比特的机器，并不等同于拥有数千个可用逻辑量子比特的机器。

近期估计表明，攻击椭圆曲线密码学所需的量子比特数量，可能低于早期预测。例如，Google Quantum AI 的 2026 年研究估计，取决于电路设计，求解一个 256 位椭圆曲线离散对数问题，所需逻辑量子比特可能低于约 1,200 至 1,450 个。在特定假设下，这可能对应不到约 500,000 个物理量子比特。

其他理论架构论文提出，在激进假设下，中性原子系统中的 qLDPC（Quantum LDPC）码等先进纠错方法，还可能进一步降低物理量子比特需求。

这些估计很重要，因为目标正在接近。

但它们并不意味着今天就能实施攻击。

目前，公开已知的量子计算机都不具备通过肖尔算法破解比特币、RSA 或其他现实公钥系统所需的逻辑量子比特、纠错能力、量子门保真度、电路深度或运行时长。

肖尔算法有哪些局限？

主要限制来自硬件，而非理论。

肖尔算法已经存在，问题在于制造能够以所需规模运行它的机器。

主要障碍有三个：

• 逻辑量子比特不足： 真实攻击需要稳定、经过纠错的逻辑量子比特。每个逻辑量子比特都可能需要许多带噪声的物理量子比特，因此当前机器缺乏攻击密码系统所需的可用规模。
• 错误率过高： 量子比特很脆弱，在长时间计算中会不断积累错误。密码学攻击所需的大规模容错纠错尚未实现。
• 电路过深： 肖尔算法需要反复执行复杂算术运算，例如模幂运算（modular exponentiation）或椭圆曲线运算。这要求很高的量子门保真度、快速纠错和长时间运行，超出了当前硬件的能力。

肖尔算法能破解比特币吗？

原则上可以。

肖尔算法的离散对数版本能够破解比特币的签名方案。它不能通过 RSA 因数分解来破解比特币，因为比特币不使用 RSA。

比特币使用的 secp256k1，是其数字签名方案所采用的椭圆曲线。较早的比特币输出使用基于 secp256k1 的 ECDSA，Taproot 则使用基于 secp256k1 的 Schnorr 签名。两者都依赖椭圆曲线离散对数问题的困难性。

一台足够强大的量子计算机运行肖尔算法，就可以求解该问题。如果攻击者掌握相关公钥，就可以还原私钥、伪造有效签名并转走资金。

因此，攻击比特币需要满足两个条件：

1. 攻击者必须能够看到相关公钥。
2. 必须存在能够求解 secp256k1 离散对数问题的 CRQC。

对某些比特币输出而言，第一个条件已经成立。

第二个条件尚未成立。

因此，肖尔算法原则上可以破解比特币，但今天还做不到。

肖尔算法如何从公钥推导私钥

比特币的安全性依赖私钥与公钥之间的单向关系。

私钥是一个秘密数值。

将这个秘密数值与 secp256k1 椭圆曲线上的生成元点相乘，就得到公钥。

这个过程正向容易，反向则不可行。

已知私钥，生成公钥很容易。

已知公钥，要还原私钥，就需要求解椭圆曲线离散对数问题。

对比特币的密钥长度而言，人们认为经典计算机无法实际完成这一求解。但在足够强大的量子计算机上，肖尔算法可以高效解决它。

这意味着，未来的量子攻击者可以取得一个可见的比特币公钥，还原私钥并生成有效签名。

这些签名与合法钱包生成的签名无法区分。

这就是公钥暴露成为比特币量子威胁模型核心问题的原因。

哪些比特币可能受到肖尔算法威胁？

比特币面临的量子风险，取决于输出类型，以及相关公钥是否已经可见。

并非所有比特币都会暴露相同的信息。

有些输出立即公开公钥，有些则只在被花费时公开。Taproot 又以另一种方式公开公钥信息。

P2PK 输出

早期的支付到公钥（pay-to-public-key，P2PK）输出，直接将完整公钥包含在锁定脚本中。

这意味着，输出创建时公钥就已经暴露。

这些币的公钥将始终对未来的量子攻击者可见。许多早期 coinbase 时期的输出都是 P2PK，这也是早期挖出的币，例如被认为属于中本聪（Satoshi）的 100 万 BTC，经常出现在量子风险分析中的原因。

P2PKH 与 P2WPKH 输出

支付到公钥哈希（pay-to-public-key-hash）的输出则不同。

P2PKH 和 P2WPKH 输出不会立即公开公钥，而是包含公钥的哈希。只有在币被花费时，公钥才会公开。

这一点很重要，因为肖尔算法不会直接破解密码学哈希。量子攻击者需要的是公钥本身，而不仅仅是它的哈希。

不过，一旦 P2PKH 或 P2WPKH 输出被花费，公钥就会出现在花费它的交易中，并永久在链上可见。

如果该密钥控制的所有资金一次性全部花完，就可能没有剩余的币与这个已暴露密钥关联。但如果重复使用同一地址，或仍有其他 UTXO 由同一密钥控制，那么这些剩余的币就会成为长期暴露的目标。

重复使用的比特币地址

在量子威胁模型中，地址复用（address reuse）尤其危险。

钱包一旦从某个地址花费资金，该地址背后的公钥就会公开。仍由同一密钥控制的任何其他币，都可能受到未来私钥还原攻击的威胁。

这也是比特币最佳实践一直不鼓励地址复用的原因之一。量子风险让良好的使用习惯变得更加重要。

待确认的比特币交易

对于由哈希保护的输出，还存在一个短暂的攻击窗口。

P2PKH 或 P2WPKH 交易广播后，在得到确认之前，公钥就已出现在待确认交易中。在未来足够快的量子计算机出现后，攻击者理论上可以利用这段内存池窗口推导私钥，并尝试广播一笔冲突交易。

今天还无法做到这一点，因为这样的量子计算机尚不存在。

但这说明，量子迁移不能拖到最后一刻。一旦快速量子攻击变得可行，从旧地址类型转移资金本身也可能有风险。

Taproot 与 P2TR 输出

不应将 Taproot 输出描述为像 P2PKH 或 P2WPKH 那样，将公钥隐藏在哈希之后。

Taproot 输出在见证程序（witness program）中直接包含一个仅含 x 坐标的 secp256k1 输出公钥。这意味着，从输出创建时起，相关公钥信息就已经可见。

Taproot 改善了隐私、效率和脚本灵活性，但没有让比特币具备量子抗性。

未来针对 secp256k1 的量子攻击，仍会影响 Taproot 输出。

比特币地址类型的更详细说明，见：《比特币地址格式入门指南》。

有多少比特币暴露于量子风险？

估计值各不相同，但链上分析通常认为，公钥已暴露的比特币数量达到数百万 BTC。

常见估计约为 600 万至 700 万 BTC，大约占供应量的 30%，具体取决于分析方法和统计口径。

要精确、实时地了解这一风险，可以查看 Project Eleven 的 Bitcoin Risk List。这个技术数据库持续审查区块链，寻找已暴露的公钥。根据其追踪数据，超过 1410 万个余额非零的地址已暴露公钥。这些易受攻击的地址合计持有超过 705 万 BTC，价值超过 4440 亿美元，面临未来量子攻击的风险。

图：Project Eleven 的 Bitcoin Risk List 仪表板，追踪因公钥可见而暴露于量子攻击的 BTC 总量及其美元价值。

其中既包括采用直接公开公钥的输出类型的币，也包括与复用密钥或此前已用于花费的密钥相关联的币。

确切数量会随时间变化，也取决于关于地址复用、输出类型、丢失的币，以及哪些币应被算作具有经济风险的假设。

重点不在于某个精确数字。

重点是，已经有相当大、且在经济上有重要意义的一部分比特币暴露了公钥。

存放在全新、从未花费过的 P2PKH 或 P2WPKH 类型输出中的币，对于这种特定攻击更安全，因为可见的只有公钥哈希。但它们并非永久安全。转移这些币时，公钥就会公开；未来迁移仍需要在 CRQC 出现前保护它们。

攻击尚未发生

第二个条件尚未满足。今天还没有 CRQC，正如前述局限所示，当前硬件能力仍相差多个数量级。悬而未决的并非这一要求能否达到，而是什么时候达到。研究预测分布较广，大致集中在 2020 年代末至 2030 年代中期。一项详细分析估计，到 2035 年出现具备相应能力的机器的概率约为六分之一，到 2050 年则超过一半（arXiv： Quantum Horizon）。

防御肖尔算法：后量子密码学

应对肖尔算法的防御方法是后量子密码学（post-quantum cryptography）。

后量子密码学以新的算法替换脆弱的公钥系统。这些算法所依赖的数学问题，目前没有已知的经典或量子计算机高效求解方法。

主要类别包括基于格、基于哈希、基于编码、多变量和基于同源的方法，不过它们在标准化过程中的存续情况并不相同。

2024 年 8 月，美国国家标准与技术研究院（NIST）最终确定了首批三项后量子密码学标准：

FIPS 203：ML-KEM，一种基于格、用于密钥建立的密钥封装（key-encapsulation）机制。

FIPS 204：ML-DSA，一种基于格的数字签名方案。

FIPS 205：SLH-DSA，一种源自 SPHINCS+ 的基于哈希的数字签名方案。

这些标准旨在支持 CRQC 出现之前的迁移。

对普通加密通信而言，迁移的紧迫性部分来自“现在收集，以后解密”（harvest now, decrypt later）攻击。攻击者今天可以记录加密流量，如果原来的密钥交换容易受到量子攻击，今后就能解密。

对区块链而言，迁移更加艰巨。它需要新的签名方案、新的地址格式，通常还需要协调升级或分叉。深入讨论见《区块链中的量子抗性》和《比特币走向量子抗性的可能路径》。

其他常见问题

肖尔算法如何破解 RSA？

肖尔算法通过分解 RSA 公钥核心的大数，将其还原为两个秘密素数，从而破解 RSA。在足够强大的量子计算机上，它能以低次多项式数量的步骤找到这些素数，而不必耗费经典计算机所需的天文数字般的时间，进而暴露私钥、攻破加密。

RSA 仍是互联网上使用最广泛的密码系统之一，应用于 TLS、电子邮件和代码签名。不过，大多数区块链并不使用 RSA。RSA 的密钥和签名较大，达到 2048 至 4096 位，而 256 位的 ECC 密钥就能提供相近安全性。在每个字节都涉及手续费和存储成本的区块链上，RSA 过于笨重，因此比特币和以太坊改用 ECC。

肖尔算法与格罗弗算法有什么区别？

肖尔算法对公钥密码学提供指数级加速：通过因数分解破解 RSA，通过离散对数破解 Diffie–Hellman、ECDSA、Schnorr 签名和椭圆曲线密码学。格罗弗算法（Grover’s algorithm）对暴力穷举搜索（brute-force search）则只提供平方级加速。它会影响 AES 等对称密码和 SHA-256 等哈希，但不会以相同方式破解它们。应对方法也不同：容易受到肖尔算法攻击的公钥方案必须更换；对称方案和哈希通常需要更大的安全裕量（security margins），例如更长的密钥。这也是为什么从任何实际意义上说，即使量子计算机也无法破解 SHA-256。

如何使用肖尔算法？

实际使用肖尔算法时，需要在量子计算框架上运行，而非普通硬件，因为今天的量子计算机只能处理非常小的输入。开发者通常使用 Qiskit 或 IBM Quantum 这样的框架，在模拟器或小型设备上运行该算法，分解 15 或 21 等数。这已经足以观察完整流程：经典准备步骤、量子周期查找电路，以及将测量结果转化为因数的经典后处理。

---

本文仅用于教育。量子硬件能力和量子比特需求估计正在快速变化，文中数字反映的是截至 2026 年中发表的研究。