前言：一场与“量子幽灵”的对话
破解私钥的计算过程，可以等价为一个模运算问题 。这类问题正好是量子算法（如Shor算法）能够高效处理的 。具体流程是：首先，根据问题的模数（32）来确定所需量子比特的数量（5个，因为 25=32） 。然后通过量子门操作（哈达玛门）制备出包含所有可能性的叠加态 。准备好后，执行一个关键的“神谕”（Oracle）计算，这个计算会将包含私钥信息的关系编码到量子态的相位中 。接着，通过量子傅立叶变换（QFT）放大并提取这个相位信息，使其能被测量 。最后，进行测量，得到一组特定的高概率结果 。用这些结果，通过经典的数学公式就能反推出我们想找的私钥 。
大家好，我是S. Tippeconnic。今天，我想邀请你进入一个奇妙的世界——在这里，物理学的诡异规则不再是书本上的理论，而是我们用来破解密码的强大工具。故事的主角，是一台名为 `ibm_torino` 的133量子比特计算机，以及一个看似不起眼的5比特椭圆曲线加密（ECC）密钥。
你可能会问，5比特？这听起来也太小了，我的手机密码都比这复杂得多。你说得没错。但这次实验的意义，并不在于破解一个多么坚固的堡垒，而在于验证一把“万能钥匙”的可行性。这把钥匙，就是量子计算，特别是传奇的Shor算法。
想象一下，现代密码学就像一个精心设计的“单向飞镖靶”。把飞镖（数据）扔到靶上（加密）很容易，但想让飞镖原路返回（解密），几乎不可能——除非你有投掷者的秘密手法（私钥）。对于传统计算机来说，面对没有私钥的加密信息，它只能像个盲人一样，把靶上的每个点都摸一遍，直到找到那个正确的点。当靶足够大时，这个过程可能需要花费宇宙诞生至今的时间。
而量子计算机，则像一个拥有“回声定位”能力的超级英雄。它不是一个点一个点地去摸，而是朝着整个靶面大喊一声。加密信息这堵“墙”会以一种特殊的方式回响，而这声“回响”中，就编码着那个秘密手法的信息。通过一种叫做“量子傅立叶变换”的神奇“耳朵”，我们能从嘈杂的回响中分辨出最清晰的那个频率，从而直接定位到秘密所在。我们的实验，就是一次精心策划的“回声定位”行动。尽管目标很小，但成功捕获回响，就证明了这套方法的威力。现在，让我们一起深入这场量子世界的探险吧。
摘要 (参照 Nature 规范)
椭圆曲线密码学（ECC）是现代数字安全通信的基石，其安全性依赖于经典计算机难以解决的椭圆曲线离散对数问题（ECDLP）。然而，Shor量子算法理论上能以多项式时间破解此类难题，对现有公钥密码体系构成潜在威胁。本研究报告了一项在IBM的133量子比特超导处理器 `ibm_torino` 上，利用Shor风格的量子攻击成功破解一个5比特ECC密钥的实验。我们关注的是一个定义在有限域 \(F_p\) 上的椭圆曲线的32阶循环子群，其中公钥关系表示为 \(Q = kP\)， \(P\) 是生成元， \(Q\) 是公钥，而 \(k\) 是待求解的5比特秘密标量（私钥）。
我们设计并实现了一个15量子比特的电路，其中包含10个逻辑量子比特（分别编码两个5比特的寄存器 \(a\) 和 \(b\)）和5个辅助量子比特（用于存储中间计算结果）。该电路的核心是一个“神谕”（Oracle）函数 \(U_f\)，它将变换 \(|a\rangle|b\rangle|0\rangle \rightarrow |a\rangle|b\rangle|aP+bQ\rangle\) 作用于量子态上。值得注意的是，整个量子计算过程中，秘密密钥 \(k\) 从未被直接编码到神谕或任何门操作中；它的信息是通过公钥 \(Q\) 隐性地、非局部地编码在整个系统的纠缠态相位里。在初始的哈达玛变换产生均匀叠加态后，神谕的调用将满足 \(a+kb \equiv 0 \pmod{32}\) 的状态分量赋予了特定的相位。随后，对寄存器 \(a\) 和 \(b\) 施加量子傅立叶变换（QFT），该变换将相位信息转化到计算基上，通过干涉效应使得测量结果的概率幅集中在满足对偶关系 \(u+kv \equiv 0 \pmod{32}\) 的输出值 \((u,v)\) 上，在 \(32 \times 32\) 的输出空间中形成清晰的对角线“山脊”结构。
我们在Qiskit Runtime 2.0平台上执行了该电路，总计采集了16,384次测量样本（shots）。尽管编译后的电路深度超过67,000层，包含超过10万个量子门，极易受到退相干和门错误的影响，实验结果依然展现出显著的非随机干涉模式。通过对测量结果进行经典后处理，我们筛选出 \(b\) 值与模数32互质（即 \(b\) 可逆）的有效样本，并计算候选密钥 \(k = (-a)b^{-1} \pmod{32}\)。在统计计数最高的100个有效结果中，我们成功地、多次地恢复了预设的秘密密钥 \(k=7\)。这一结果有力地证明，即使在当前含噪声中等规模量子（NISQ）时代，Shor算法的核心物理原理——相位干涉，依然能够在真实的、复杂的量子处理器上得以体现，并提取出加密信息。本实验不仅验证了Shor算法在ECC上的实际可操作性，也为评估未来容错量子计算机对密码学构成的实际威胁提供了重要的实验基准。
量子工具箱：破解之旅的分步详解
现在，让我们卷起袖子，一步步拆解这个看似神秘的量子破解过程。你将看到，每一步都像是在搭建一个精密的乐高模型，最终组合成一部能够“听到”密码的机器。
第一步：问题转化 - 从曲线到时钟
椭圆曲线上的数学运算很复杂，但幸运的是，对于我们关心的这个32阶子群，我们可以做一个巧妙的类比。想象一个只有32个刻度的时钟，从0到31。椭圆曲线上的点加法运算，可以被完美地映射成这个时钟上的“指针”加法。例如，点 \(7P\) 就对应时钟上的数字7，点 \(8P\) 对应8。而 \(7P + 8P = 15P\)，在我们的时钟上就是 \(7+8=15\)。如果超过31，就绕一圈回来，这就是“模运算”，比如 \(25P + 10P = 35P\)，在时钟上就是 \((25+10) \pmod{32} = 3\)。
通过这种方式，寻找私钥 \(k\) 的难题 \(Q=kP\)，就变成了在时钟上解方程：\(Q_{idx} \equiv k \cdot P_{idx} \pmod{32}\)。这是一个经典的模运算问题，也正是Shor算法的“主场”。为了处理模32的运算，我们需要能表示0到31所有数字的量子比特，因为 \(2^5 = 32\)，所以我们确定了需要5个量子比特来构建核心的计算单元。
静态图示：从椭圆曲线到模32时钟
下图形象地展示了我们将复杂的椭圆曲线点（左侧）如何简化为易于量子计算的整数环（右侧）的过程。每个点都找到了自己在“时钟”上的唯一位置。
第二步：制备叠加态 - 同时探索所有路径
如果让经典计算机来猜私钥 \(k\)，它只能一次猜一个：k=1？不对。k=2？不对……直到试遍所有可能。而量子计算机的超能力在于“量子叠加”。通过一个叫做“哈达玛门”（Hadamard Gate）的操作，我们可以让每个量子比特同时处于 \(|0\rangle\) 和 \(|1\rangle\) 的状态。当我们对两个5比特的寄存器（我们称之为 \(a\) 和 \(b\)）中的所有10个量子比特都执行这个操作后，我们就创造了一个包含 \(32 \times 32 = 1024\) 种可能组合的宏大叠加态。这就像我们瞬间拥有了1024个“量子克隆”，每个克隆都在同时测试一种 \((a, b)\) 组合的可能性。我们的初始状态是： \[ |\psi_1\rangle = \frac{1}{32} \sum_{a=0}^{31} \sum_{b=0}^{31} |a\rangle |b\rangle |0\rangle \]
动画1：哈达玛门的魔力
一个量子比特可以被想象成一个指向北极（\(|0\rangle\)）或南极（\(|1\rangle\)）的箭头。哈达玛门的作用就像轻轻一拨，让这个箭头同时指向所有方向，均匀地覆盖在球面上，进入“叠加态”。
第三步：神谕（Oracle） - 在相位中留下“秘密”标记
这是整个算法最核心、最精妙的一步。我们需要设计一个特殊的量子模块，也就是“神谕”，它能识别出与私钥 \(k\) 相关的 \((a,b)\) 组合，并给它们做一个“秘密标记”。这个标记非常特别，它不改变这些组合的数值，而是改变它们的“相位”——一个量子态所特有的复数属性。
具体来说，神谕执行的计算是 \(f(a,b) = aP + bQ\)。利用我们之前建立的映射，这等价于计算 \((a + bk) \pmod{32}\)。神谕将这个计算结果存储到第三个辅助寄存器中。于是，整个量子系统的状态演变成了： \[ |\psi_2\rangle = \frac{1}{32} \sum_{a=0}^{31} \sum_{b=0}^{31} |a\rangle |b\rangle |a+kb \pmod{32}\rangle \] 注意，神谕本身并不知道 \(k\) 是多少，它只是忠实地根据我们给它的公钥 \(Q\) 去执行运算。但这个过程巧妙地将所有满足特定 \(a+kb\) 关系的 \((a,b)\) 组合，与相同的计算结果关联起来，从而在这些组合之间建立了深刻的纠缠关系。正是这种纠缠，将私钥 \(k\) 的信息烙印在了量子态的相位结构之中。
动画2：神谕的相位标记
想象无数粒子（代表不同 \((a,b)\) 组合）流过一个“检测门”（神谕）。那些携带着与私钥 \(k\) 相关信息的粒子，在通过时会被染上特殊的“荧光”（相位改变），而其他粒子则不受影响。你可以拖动下面的滑块改变私钥k，观察哪些粒子会被标记。
第四步：量子傅立叶变换（QFT） - 让秘密“共振”
我们已经给正确的解做了标记，但它们还淹没在1024种可能性中，无法直接看到。这时，我们需要一个“放大器”，这就是量子傅立叶变换（QFT）的作用。你可以把它想象成声学上的“频谱分析仪”。
生活中的类比是：在一片嘈杂的声音中，你想找出隐藏的特定音调（比如Do-Re-Mi）。傅立叶变换就能将混乱的声波分解成一系列纯净的频率，让你清晰地看到哪些音调的能量最强。同样，QFT作用在我们的量子寄存器 \(a\) 和 \(b\) 上，会将之前神谕留下的相位标记，转化为概率幅的“共振”。那些被标记的、相位一致的状态会相互叠加增强（相长干涉），而那些未被标记的、相位杂乱的状态则会相互抵消（相消干涉）。
经过QFT后，量子态变为： \[ |\psi_3\rangle \propto \sum_{u=0}^{31} \sum_{v=0}^{31} \left( \sum_{a,b \text{ s.t. } a+kb \equiv \text{const}} e^{\frac{2\pi i}{32}(au+bv)} \right) |u\rangle|v\rangle \] 这个复杂的公式告诉我们一个惊人的结果：只有当测量值 \((u,v)\) 满足一个简单的线性关系 \(u+kv \equiv 0 \pmod{32}\) 时，括号里的求和才会产生强烈的相长干涉，使得测量到这个 \((u,v)\) 的概率变得非常高。其他不满足该关系的 \((u,v)\) 几乎不可能被测量到。
动画3：QFT的干涉力量
在QFT的作用下，之前被神谕标记的粒子开始“共鸣”。在代表输出结果的屏幕上，这些共鸣点会连成一条清晰的直线，这就是“干涉条纹”。这条直线的斜率，就暴露了我们苦苦追寻的私钥 \(k\)。
模拟测量次数: 0 / 256
第五步：测量与经典计算 - 收获果实
现在，万事俱备。我们对量子计算机进行“测量”。每次测量，量子叠加态都会“坍缩”，随机给出一个经典的结果——一个具体的 \((u,v)\) 值。由于QFT的干涉效应，我们测量到的 \((u,v)\) 值会以极高的概率落在 \(u+kv \equiv 0 \pmod{32}\) 这条直线上。
我们重复测量成千上万次，收集一大堆高概率的 \((u,v)\) 数据点。接下来就简单了，回到我们的经典计算机上，随便挑一个测量结果 \((u,v)\)，比如 \((u_0, v_0)\)。我们只需要解一个小学水平的同余方程： \[ k \equiv -u_0 \cdot v_0^{-1} \pmod{32} \] 这里 \(v_0^{-1}\) 是 \(v_0\) 在模32下的乘法逆元。当然，这要求 \(v_0\) 和32是互质的（它们的最大公约数为1）。这就是为什么我们在后处理中要筛选掉那些 \(v_0\) 不可逆的数据。通过这个简单的计算，我们就从量子世界的概率云中，抓住了那个确定的、唯一的私钥 \(k\)。在我们的实验中，这个值就是7。
动画4：经典后处理计算器
从QFT干涉图中随机抽取一个高概率点 \((u, v)\)。下面的计算器将为你展示如何通过简单的模运算，从这个测量结果中反推出私钥 \(k\)。
随机测量点: (u=?, v=?)
计算步骤:
- 检查 \(v\) 是否可逆: ...
- 计算 \(v^{-1} \pmod{32}\): ...
- 计算 \(k = (-u \cdot v^{-1}) \pmod{32}\): ...
最终恢复的密钥 k = ?
实验结果：噪声中的胜利回响
理论是完美的，但现实中的量子计算机充满了“噪声”，就像收音机里的静电干扰。我们的电路深度超过67000层，每一次门操作都可能引入微小的错误。那么，我们的“回声定位”真的成功了吗？答案是肯定的。
下图展示了我们从 `ibm_torino` 上获取的16384次测量的原始数据热力图。尽管图像上有不少噪声造成的杂点，但你依然可以看到一些水平方向的“亮带”，这就是量子干涉形成的“山脊”的证据。这表明，量子态的演化并没有被噪声完全淹没，信息的结构被保留了下来。
静态图示1：原始计数热力图 (a vs b)
这张热力图是QFT之后直接测量寄存器a和b得到的。颜色越亮代表该 \((a,b)\) 组合被测量到的次数越多。明显的水平条纹预示着干涉效应的存在。
更有说服力的是对恢复出的密钥 \(k\) 的统计。我们将所有有效的测量结果 \((u,v)\) 都用来计算 \(k\)，然后统计每个 \(k\) 值出现的总次数。如下图所示，虽然 \(k=0\) 和 \(k=24\) 等值由于系统偏差和噪声出现了很高的峰值，但我们真正要找的密钥 \(k=7\)，也作为一个显著的信号峰出现了！在计数最高的前100个结果中，\(k=7\) 出现了3次，总计数超过127次，足以让我们在众多候选者中锁定它。
静态图示2：恢复的k值直方图
这个直方图统计了每个可能的密钥值被计算出来的总次数。尽管存在噪声峰，但目标密钥 \(k=7\) (红色标注) 依然作为清晰的信号脱颖而出。
这次实验就像是在暴风雨中驾驶一艘小船，虽然航程颠簸，但我们最终凭借着量子力学的罗盘，准确地抵达了目的地。它雄辩地证明了，即使在今天这个充满噪声的量子计算时代，Shor算法的强大威力也已初露锋芒。
技术附录：深入细节
量子电路概览
整个Shor算法的实现可以被一个量子电路图所概括。这个电路清晰地展示了信息的流动和处理过程：从初始的叠加态制备，到核心的神谕函数调用，再到最后的QFT和测量。
静态图示3：简化量子电路图
下图展示了本次实验所用量子电路的核心结构。三组量子线分别代表寄存器 \(|a\rangle\)、\(|b\rangle\) 和辅助寄存器 \(|p\rangle\)。H门代表哈达玛变换，\(U_f\) 代表复杂的神谕模块，QFT-1代表逆量子傅立叶变换（在Shor算法的因子分解版本中使用逆变换，在离散对数问题中我们用正向变换，但原理相通）。
关于 \(b\) 的可逆性
在第五步的经典后处理中，我们强调需要 \(b\) 在模32下是可逆的。这意味着 \(b\) 必须与32互质，也就是 \(gcd(b, 32)=1\)。在0到31的整数中，只有奇数满足这个条件。这意味着我们大约有一半的测量结果是“无效”的，因为它们的 \(b\) 值是偶数，无法用于求解 \(k\)。这在一定程度上降低了算法的效率，但在实践中，只要我们采集足够多的样本，总能获得充足的有效数据点来完成破解。这也是为什么量子算法通常需要重复运行多次的原因之一。