[原创]量子算法分析: 椭圆曲线密码学的量子破解方法-逆向工程-看雪安全社区

[原创]量子算法分析: 椭圆曲线密码学的量子破解方法

发表于: 2026-1-14 13:13 18854

[原创]量子算法分析: 椭圆曲线密码学的量子破解方法

gjden

2026-1-14 13:13

18854

以前写了篇RSA的量子算法分析的文章，在这篇文章里留了个离散对数问题的坑一直没填，借此机会把坑填了，ECC的shor算法破解除了少数几篇论文中简单地提及外，几乎没有系统而详细地资料，本文算是独一篇了。我们知道RSA算法的安全是基于大数质因数分解难题，即RSA的安全性主要依赖于从两个大素数的乘积中恢复这两个素数的难度。而椭圆曲线密码学(ECC)主要依赖于离散对数问题的难解性上。不过用Shor算法的思想来破解ECC相对来说要困难些：算法设计会更复杂，量子电路复杂度也会更高，并且需要更多的量子比特（目前对于如何降低量子比特数依然是量子计算前沿的重要课题，比如如何优化量子电路减少量子比特以及如何实现高效的量子纠错机制从而减少量子比特数）。因此本文稍微会比RSA那篇要难理解点，不过这篇尽量保证严谨的基础上更通俗易懂。

在之前的[文章中](https://bbs.kanxue.com/thread-277516-1.htm)我们比较详细地讨论了利用Shor量子算法攻破RSA加密体系的核心思想和实现过程，也在该篇文章中点破了RSA的脆弱性本质：即周期性（依赖于模幂运算的RSA算法必然具备周期性）。而Shor量子算法便是这种“周期性漏洞”的量子攻击武器。本文中，我们将使用这项“量子武器”来破解椭圆曲线加密算法并对整个攻击过程进行深入的分析。

##   一、ECC加密算法简介

椭圆曲线密码学（Elliptic Curve Cryptography，简称ECC）是一种基于椭圆曲线数学结构的公钥加密技术，与传统的RSA密码系统相比，ECC能够在远短的密钥长度下提供同等甚至更高的安全性。例如，一个256位的ECC密钥提供的安全强度，大致相当于一个3072位的RSA密钥。因此ECC特别适合在计算能力、存储空间和带宽受限的环境中（如移动设备、物联网芯片和区块链系统）使用，目前被广泛应用于数字签名（ECDSA）、密钥交换（ECDH）和加密传输等关键领域。

在分析分析量子破解前，有必要简单介绍一下椭圆曲线以及其数据加密的基本原理，首先**椭圆曲线**是一些列满足以下方程的曲线：

$$
y^2 = x^3 + ax + b \quad (4a^3 + 27b^2 \neq 0)
$$

其中，参数a 和 b是定义曲线的常数，并且必须满足 $4a^3 + 27b^2 \neq 0$ 以确保曲线没有奇点（即曲线是光滑的）。对于比较简单的椭圆曲线 $y^2 = x^3 - x + 1$ ，大概长这样。

![椭圆曲线](upload/attach/202602/302697_N7QQ28PM56TJ5R7.webp)

为了利用椭圆曲线的特性来构造非对称加密，我们首先需要在椭圆曲线上定义点的加法和标量乘法运算。

**点加运算**：两点 P 和 Q 的加法结果是曲线上另一点 R，即 $P+Q=R$ 。若 $P = (x_1,y_1), Q = (x_2,y_2)，R = (x_3,y_3)$ ，则 $P + Q = (x_3,y_3)$ ，计算方式如下：

$\begin{cases}\lambda = \frac{y_2 - y_1}{x_2 - x_1} & (P \neq Q) \\ \lambda = \frac{3x_1^2 + a}{2y_1} & (P = Q) \\x_3 = \lambda^2 - x_1 - x_2, y_3 = \lambda(x_1 - x_3) - y_1\end{cases}$

**标量乘法**：通过点加运算，我们可以构造标量乘法（我们利用标量乘法的困难性来保证密码学的安全性），如：

$2\cdot P = P + P；3\cdot P = P + P + P；k\cdot P = P + P + P+...$ 。

注意，我们定义椭圆曲线上的点加运算和标量乘法运算，是为了构建一个代数结构（群），从而使得椭圆曲线可以用于密码学。具体来说，椭圆曲线上的点加上一个特殊的“无穷远点”构成一个阿贝尔群（交换群）。

比如点加运算定义了椭圆曲线上两个点相加的几何和代数规则，结果仍然是曲线上的点。这个运算满足群的性质（封闭性、结合律、单位元、逆元、交换律）。

- 封闭性：两个点相加的结果还是曲线上的点
- 结合律： $(P + Q) + R = P + (Q + R)$ 
- 单位元：存在无穷远点 $O$ ，使得 $P + O = P$ 
- 逆元：每个点 $P$ 都有逆元 $-P$ 
- 交换律： $P + Q = Q + P$

而标量乘法中，我们通过重复点加运算，可以定义整数k与点P的乘法，即k个P相加。这是椭圆曲线密码学（ECC）中的核心运算，因为从公钥（点Q）和基点G恢复私钥k（整数）的困难性（椭圆曲线离散对数问题）保证了安全性。

**阶的计算**：对于有限域的椭圆曲线，我们可以选取曲线上的一个点作为基点，然后不断累加直到得到无穷远点O，这个累加到点O需要的次数我们称为该基点的阶。比如我们选择一条定义在有限域 $\mathbb{F}_{11}$上的椭圆曲线: $y^2 = x^3 + x + 6 \ (\text{mod} \ 11)$ ，然后我们选择曲线上的一个点作为基点 $G= (2,4)$ ，接下来依次对基点进行累加直到找到周期，即基点的阶。比如：

$2G = G+G=(2,4) + (2,4)$*。*先计算斜率： $s = (3\times2^2+1)/(2\times4) = 13/8 \equiv 2 \times 8^{-1} \equiv 2 \times 7 \equiv 3 \ (\text{mod} \ 11)$，然后得到 $2G$ 的坐标：$x_3 = 3^2 - 2 - 2 = 5$*，*$y_3 = 3(2-5) - 4 =-13≡9$，所以 $2G = (5, 9)$

$3G = 2G + G = (5,9) + (2,4)$。 计算斜率：$s = (4-9)/(2-5) =5/3 \equiv 5*4=20\equiv 9(\text{mod} \ 11)$。然后计算点坐标 ：$x_3 = 9^2 - 5 - 2 = 74 ≡ 8$ ，$y_3 = 9(5-8) - 9 =-36≡8$ ，所以 $3G = (8,8)$。

继续计算下去，最终会发现点 $ (2,4)$ 的阶是 $ 13$ （即 $13G = 无穷远点 O$ ）。

*1G = (2, 4)，2G = (5, 9)，3G = (8, 8)，4G = (10, 9)，5G = (3, 5)，6G = (7, 2)，7G = (7, 9)，8G = (3, 6)，9G = (10, 2)，10G = (8, 3)，11G = (5, 2)，12G = (2, 7)，13G = O (无穷远点), 14G = (2, 4), 15G = (5, 9)*

我们还可以看出，如果点 $G$ 的阶为 $n$ ，那么有: $G=(n+1)G$ 。

基于以上运算法则，我们就可以实现ECC的加解密，过程如下：

**第一步生成密钥：** 选择椭圆曲线 $E$ 和基点 $G$ ，基点$G$的阶为质数 $n$ 。 生成小于 $n$ 的随机整数 $k$ 作为加密私钥。我们在通过私钥k和基点G来生成公钥 $Q$ 即 $Q = k\cdot G$ 。

**第二步加密明文：** 将明文编码为曲线上的点 M。 选择随机数（ $r < n$ ）。 然后通过公钥 $Q$ 计算得到密文对 ( $Cipher1, Cipher2$ )： $Cipher1 = M + r\cdot Q，Cipher2 = r\cdot G$ 。

**第三步解密密文：** 有了密文对后，我们可以通过私钥解密密文得到明文： $M = Cipher1 - k\cdot Cipher2 = M + r\cdot Q - k\cdot r\cdot G = M+r\cdot Q - r\cdot k\cdot G=M+r\cdot Q - r\cdot Q=M$

椭圆曲线密码学（ECC）的安全性建立在椭圆曲线离散对数问题（即ECDLP） 的难解性上，其核心是标量乘法计算上的严重不对称性，即正向计算容易，逆向求解极难。具体而言，在当前ECC加密算法中，已知公开的基点 G 和通过标量乘法得到的公钥 $Q = k\cdot G$ ，想要逆向推导出私有密钥 k所需要的计算量远远高于人类计算的极限。目前，已知最有效的用于求解ECDLP的经典算法（如Pollard Rho算法）所需要的时间复杂度也是指数级或亚指数级的。Pollard's Rho算法计算私钥需要的时间复杂度为 $O(\sqrt{2^n})$ ，其中 $n$ 为私钥比特位长度，比如当私钥长度k为 $n=256$ 位时，该算法需要 $2^{128}$ 次计算，即使在宇宙年龄（$10^{17}$ 秒）尺度下，也需要每秒 $10^{111}$ 次的计算。虽然这是一个恐怖的计算量，但对于量子计算机而言，通过巧妙地设计一套算法，就可以让这种完全不可能的任务变得轻松且简单（将复杂度降至多项式级$O((log n)³)$）。

## 二、周期性分析

在之前文章中，我们通过构建Shor量子算法来寻找RSA代数结构中的周期，进而实现合数的因式分解。而构造Shor算法的本质就是寻找周期，理论上任何一个核心代数结构中存在周期性的加密算法，Shor算法都可以在多项式复杂度下成功地完成攻击。既然定义点加运算和标量乘法的椭圆曲线本质上构成了一个阿贝尔群，那么基于有限域的椭圆曲线加密算法自然也存在一个周期，但在RSA中周期性是比较能够直接发现的，但在ECC中，这个周期性似乎不可见，相对来说比较隐蔽，这就需要我们通过特定的方式找出来。这个特定的方法就引入二元函数，通过简单的变换就可以观察到这个函数在二维平面上的周期。我们定义函数：

$f(a, b) = a·G + b·Q$ ，

代入 $Q = k·G$ 可得：

$f(a, b) = (a + b·k)·G$

我们设 $f(a,b)$ 的周期为 $(a_r,b_r)$ ( $a_r,b_r$ 为整数),因此有：

$f(a,b)=f(a+a_r, b+b_r) = (a+b\cdot k+(a_r+b_r\cdot k))\cdot G\\ \Rightarrow a_r+b_r\cdot k=0$

因此，只要满足此式的任何组合都是函数 $f(a,b)$ 的周期。由于 $a_r,b_r,k$ 皆为整数，因此我们取一个比较好算的周期，设 $b_r=1$ ，则周期对为 $(-k,1)$ 。也就是说我们让$(a, b)$ 沿方向 $v = (-k, 1)$ 移动，函数 $f$ 值就会不变，验证：

$$
   f(a - k \cdot s, b + s) = (a - k s + (b + s)k) \cdot G = (a + b k) \cdot G = f(a, b)\quad s\in Z   
$$

这里 $s$ 为整数，也就是说函数在整数平移 $(a,b) \to (a - k s, b + s)$ 下保持不变。因此，我们通过制备一套量子叠加态系统利用量子纠缠、量子测量以及量子傅里叶变换（QFT），就可以把将 $ f(a,b) $ 的空间周期性转换为动量空间的尖峰，从而可以迅速地找到 $k$ （加密私钥）。

## 三、构造量子算法

接下来我们将一步一步地设计并实现这样的量子算法，下图为解决ECC的shor算法量子电路图（简图）。

![ECC-SHOR量子电路图](upload/attach/202602/302697_9X777Y33MFRDTSV.webp)

**1. 初始化量子寄存器**

首先我们需要两个量子寄存器用于存储编码的信息（实际还需要临时存储点加法中间结果，所以需要更多的辅助寄存器，此处简化不考虑）。

**寄存器1（reg1）**：用于存储椭圆曲线上的点。每个点由两个坐标值(x,y)表示，每个坐标是有限域$F_p$中的元素。因此，每个坐标值需要$log₂p$个量子比特来表示，所以总比特数为 $l=2log₂(p)$。如果 $p=11$ ，那么我们需要8个比特量子寄存器来存储。注意，椭圆曲线密码学中，通常使用压缩表示形式，即只存储x坐标和y的符号位，这样可以节省存储。但在量子计算中，reg1会处于叠加态（无法提前知道点的位置）以及需要进行点加法运算，我们需要完整的坐标，因此存储时无法进行压缩。

**寄存器2（reg2）**：用于存储整数对$(a,b)$。设有限域上的椭圆曲线的阶为 $n$,由于a和b都在模n的整数环中取值，因此Reg2实际上是两个量子寄存器组合而成。设每个量子比特数为 $t$ ，为了确保在应用QFT时，周期能够以高概率被检测到，所以设 $2^t \geq 2n^2$ 得 $t=log_2(2n^2)$ ，故寄存器Reg2有2t个量子比特。

准备好两个量子寄存器后，我们首先需要对其进行初始化，一般将所有量子态置为 $|0⟩$ 。所以，我们这台量子计算机的初始状态为：

$ |\psi_0⟩ = |0⟩_1^{⊗l} ⊗ |0,0⟩_2^{⊗2t}$

其中 $|0⟩_1^{⊗l}$ 为 $l$ 个量子比特的寄存器reg1， $|0⟩_2^{⊗2t}$ 为 $2t$ 个量子比特的寄存器reg2。

然后，对reg2应用Hadamard变换，使其处于所有可能$(a,b)$的均匀叠加态(总共有 $2^{2t}$ 个态的叠加)：

$|\psi_1⟩ = \frac{1}{2^t} \sum_{a=0}^{2^t-1} \sum_{b=0}^{2^t-1} |0⟩_1^{⊗m} |a, b⟩ _2$

**2. 实现函数f的量子黑盒（Oracle）**

对于我们定义的函数： $f(a, b) = aG + bP$ ，由于椭圆曲线点群是阿贝尔群，所以 $aG+bP$ 也是椭圆曲线上的一个点。我们需要通过设计一个特殊量子电路来计算该函数的结果，该电路需要实现基础的模运算如模加、模减、模乘、模逆运算外，还需要实现更为复杂的椭圆曲线标量乘法以及点加法，为了方便，我们将这一系列量子电路运算单元简化为量子黑盒，定义为 $U_f$（其中一种较为高效实现方法可以参考：<a href="elink@013K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6W2M7s2u0A6L8Y4c8Q4x3X3g2A6j5h3y4J5i4K6u0W2L8%4u0Y4i4K6u0r3x3U0l9I4y4#2)9J5c8U0f1&6z5q4)9J5k6i4m8V1k6R3`.`.">98fK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6W2M7s2u0A6L8Y4c8Q4x3X3g2A6j5h3y4J5i4K6u0W2L8%4u0Y4i4K6u0r3x3U0l9I4y4#2)9J5c8U0f1&6z5q4)9J5k6i4m8V1k6R3`.`.</a>）

通过量子电路可以在量子叠加态上计算函数 $f(a, b) = a  G + b P$ 的结果，然后将结果存储到寄存器Reg1中。 $U_f$ 执行操作简单表示如下：

$U_f \underbrace{|a,b\rangle}_{\text{Reg2}} \otimes \underbrace{|0\rangle}_{\text{Reg1}} = \underbrace{|a,b\rangle}_{\text{Reg2}} \otimes \underbrace{|aG+bQ\rangle}_{\text{Reg1}}$

因此，应用 $U_f$ 后，系统状态变为：

$|\psi_2⟩ = \frac{1}{2^t} \sum_{a=0}^{2^t-1} \sum_{b=0}^{2^t-1} |a, b⟩ |f(a, b)⟩=\frac{1}{2^t} \sum_{a=0}^{2^t-1} \sum_{b=0}^{2^t-1} |a, b⟩ |(a+kb)\cdot G⟩$

注意，最后计算得到函数结果存到Reg1中。

**3. 测量寄存器1（函数值寄存器）**

现在，测量寄存器Reg1，Reg1会随机坍塌到某个 $m$ 值的状态，然后可以计算得到曲线点 $Q = m\cdot G$ 。由于两个寄存器是处于纠缠态，因此测量Reg1时，寄存器Reg2（存储$(a,b)$的寄存器）会坍缩到所有满足 $f(a, b) = Q$ 的$(a,b)$对的叠加态上，即：

$|\psi_3⟩ = \frac{1}{\sqrt{K}} \sum_{(a,b) \in S} |a,b⟩ $

其中 $S$ 是满足 $aG+bP=Q$ 的所有 $(a,b)$ 的集合。其中， $K ≈ 2^{2t} / n$ 是满足等式$Q = m\cdot G$的$(a,b)$对的有效态数量。如果我们固定$b$，则$a$分布在模$n$意义下具有周期性，解$a$被确定为 $a = (m - bk)\ mod\ n$ 。但是，由于我们的寄存器reg2中$a和$b的取值范围是0到 $2^t-1$ （而不仅仅是0到$n-1$），所以对于每个$b$，可能有多个a满足条件（即$a$可以加上$n$的整数倍，只要在0到 $2^t-1$ 内）。然而，由于 $2^t$ 远大于$n$（我们取 $t≈2log₂(n)$ ，所以每个$b$大约有 $2^t/n$ 个$a$满足条件。因此得到：

$$
K ≈ 2^t\frac{2^t}{n}=\frac{2^{2t}}{n}
$$

**4. 量子傅里叶变换分析**

由于我们对reg1进行了测量，所以reg2发生了坍缩，注意坍缩后的态依然是叠加态，是所有满足 $f(a, b) = Q$ 的$(a,b)$对的叠加态。这个叠加态中包含了周期信息，因此现在我们需对reg2（大小为2t个量子比特）应用量子傅里叶变换以提取出周期信息。注意，寄存器2由两个寄存器（分别存储$a$和$b$）组成，因此我们分别对a和b的部分应用 $\text{QFT}$ （即应用 $\text{QFT}_{2t}$ ，或者等价于对$a$部分应用 $\text{QFT}_t$ ，再对$b$部分应用 $\text{QFT}_t$ ，因为$\text{QFT}$是张量积的）。

对Reg2应用 $QFT_{2t}$ （即对整个$2t$个量子比特进行量子傅里叶变换）。 $QFT_{2t}$ 的作用是将时域/空域中的周期信号变换为频域中的尖峰：

$QFT_{2t} |a,b⟩ = \frac{1}{2^t} \sum_{c=0}^{2^t-1} \sum_{d=0}^{2^t-1} e^{2\pi i (a c + b d)/2^t}|c,d⟩$

因此，变换后的状态为：

$|\psi_4⟩ = \frac{1}{2^t\sqrt{K}} \sum_{(a,b)\in S} \sum_{c=0}^{2^t-1}\sum_{d=0}^{2^t-1} e^{2\pi i (a c + b d)/2^t} |c,d⟩ \\           = \frac{1}{\sqrt{K}} \frac{1}{2^t}\sum_{c,d} \left[ \sum_{(a,b)\in S} e^{2\pi i (a c + b d)/2^t} \right] |c,d⟩     $

**5. 寄存器2测量与概率分布**

当我们测量reg2时，寄存器状态会坍塌到特定的$(c,d)$，由于reg2在应用量子傅里叶变换前具有周期性，因此此时我们测量reg2得到值大概率会出现在频域尖峰附近，坍缩后系统的态为：

$|\psi_5⟩_m = \frac{1}{2^{t}\sqrt{K}} \left[ \sum_{(a,b)\in S} e^{2\pi i (a c + b d)/2^t} \right] |c,d⟩_m     $

因此，我们需要计算内层求和：

$ac+bd=(m-kb)c+bd=mc+(d-kc)b\\\Rightarrow  \sum_{(a,b)\in S} e^{2\pi i (a c + b d)/2^t}= \sum_{(a,b)\in S} e^{2\pi i [mc+(d-kc)b]/2^t}$

由于 $（a,b）$ 按照 $b=0，1，2，....，2^t-1$ ，并且按此确定 $a$ ，也就确定了向量。因此我们将$（a,b）$和 $b$ 都参数化为 $s$ 。即设 $b=s$ ，那么 $a=m-ks(\ mod\ n)$ ，由此，我们就将向量$（a,b）$转化成为关于 $s$ 的函数了。

由此，内层求和变化为：

$\sum^{K-1}_{s=0} e^{2\pi i [mc+(d-kc)s]/2^t}=e^{2\pi mci/2^t}\sum^{K-1}_{s=0} e^{2\pi i (d-kc)s/2^t}$

设 $r=e^{2\pi i (d-kc)/2^t}$ ,则求和部分:

$S=\sum^{K-1}_{s=0} r^s=\frac{r^K-1}{r-1},\quad r\ne 1$

当 $r=1$ 时即 $e^{2\pi i (d-kc)/2^t}=1$ ，根据欧拉公式 $e^{i\theta} = \cos\theta + i\sin\theta$ 得知：

$\cos(2\pi (d-kc)/2^t)+i\sin(2\pi (d-kc)/2^t)=1$

也就是说当 $(d-kc)/2^t$ 为整数时，所有的值刚好在波峰上相长干涉，因此累加后得到 $S=K$ ，综合一下：

$S=\begin{cases}     K=2^{2t}/n&r= 1\\   \frac{r^K-1}{r-1}&r \ne 1\\ \end{cases}$

综上，令$\gamma=d-kc$，则最后得到有效测量值$（c，d）$的概率分布为（计算过程参考<a href="elink@a4aK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6*7K9s2g2S2L8X3I4S2L8W2)9J5k6i4A6Z5K9h3S2#2i4K6u0W2j5$3!0E0i4K6u0r3M7q4)9J5c8U0p5H3y4U0V1J5x3K6p5%4y4b7`.`.">RSA这篇文章</a>）：

$P(|c,d⟩)=\begin{cases}\frac{1}{\sqrt{K2^{2t}}}=\frac{n}{2^{2t}}&r= 1\\   \frac{1}{\sqrt{K2^{2t}}}|\frac{r^K-1}{r-1}|^2=\frac{n}{2^{2t}}\cdot\frac{\sin^2K\theta/2}{\sin^2\theta/2}\quad&r \ne 1,\theta=2\pi \gamma/2^t\\ \end{cases}$

注： $|\frac{r^K-1}{r-1}|^2=|(e^{2\pi iK\gamma}-1)/(e^{2\pi i \gamma}-1)|^2=(\frac{cosK\theta+isinK\theta-1}{cos\theta+isin\theta-1})^2=\frac{sin^2(K\theta/2)}{sin^2(\theta/2)}$

当 $r=1$ 时，每个波峰刚好位于$\gamma$处即 $d-kc=2^t\cdot l(l为整数)$ ，由于 $c,d\in [0,2^t-1]$ ，因此我们得到同余方程为:

$kc = d(mod\ 2^t)$ 。

这是产生相长干涉的峰值条件。注意，在这种情况下，我们对Reg2测量后得到的$c,d$值是刚好满足同余方程的（因此才会出现$r=1$的情况），通过经典处理就可以很容易地得到 $k$ 的值。

如果我们测量得到的$c,d$值存在误差，此时我们的同余方程方程不是严格的相等：

$kc\approx d(mod\ 2^t)$

此时 $r\ne 1$ （$\gamma/2^t$ 不能整除），实际波峰位于接近理论波峰的两侧。不过我们也可以通过经典处理来解决这个问题。

## 四、概率分析

**1、概率下限**

下面为了计算这种情况出现的概率，我们在方程加入微调的参数。

$d-kc+\delta=\gamma+\delta=2^t\cdot l(l为整数)$

这里，为了严谨讨论，我们设 $|\delta/2^t|$ 小于等于$1/2$（如果大于$1/2$，可以认为是下一个整数 $z-(1-\delta)$ ），所以这是适用于所有情况的。

$n^2\leq 2^t,\frac{n}{2^t}\leq \frac 1 n$

$$
|\delta|\leq 2^t/2\\ \Rightarrow |\theta|=|2\pi \gamma/2^t|\leq\pi n/2^t\leq \pi 2^{t/2}/2^t=\pi/2^{t/2} 
$$

我们考虑当 $t>1$ 时， $\theta \leq \frac \pi 2$ 。此时，当 $\theta\in[0,\frac{\pi}{2}]$， $\sin\theta$ 必位于原点与点 $(\pi/2,1)$ 连线的上方，所以 $|sin\theta|$ 为凸函数，有：

$|sin(\frac{K\theta}{2})|\geq|\frac{2}{\pi}(\frac{K}{2})\theta|$

又因 $sin\frac{\theta}{2}\leq\frac{\theta}{2}$ ，因此：

$$
\frac{sin^2(\frac{K}{2}\theta)}{sin^2(\frac{\theta}{2})} \geq\frac{(\frac{2}{\pi}(\frac{K}{2}\theta))^2}{sin^2(\frac{\theta}{2})}\geq\frac{(\frac{2}{\pi}\frac{K}{2}\theta)^2}{(\frac{\theta}{2})^2}=(\frac{K}{\pi})^2\cdot 4=\frac{4K^2}{\pi^2}
$$

所以得到概率下限：

$P(|c,d⟩)=(\frac{1}{\sqrt{K}} \frac{1}{2^{t}})^2\frac{sin^2(K\theta/2)}{sin^2(\theta/2)}=\frac{1}{K\cdot 2^{2t}}\frac{sin^2(K\theta/2)}{sin^2(\theta/2)}\geq \frac{1}{K\cdot 2^{2t}}\frac{4K^2}{\pi^2}=\frac{4K}{\pi^2 2^{2t}}=\frac{4\cdot(2^{2t}/n)}{\pi^22^{2t}}=\frac{4}{n\pi^2}$

通常由于 $n$ 较大，因此下限概率非常小。

**2、概率上限：**

对于固定的 $c$，考虑 $d$ 在 $kc$ 附近的情况。令 $\gamma_d = d - kc$。

振幅： $ \alpha_{c,d} \propto \frac{\sin(2\pi K \gamma_d /(2\cdot 2^t))}{\sin(2\pi \gamma_d /(2\cdot 2^t))}=\frac{\sin(\pi K \gamma_d / 2^t)}{\sin(\pi \gamma_d / 2^t)} $

当 $|\gamma_d| \leq \frac{2^t}{2K}$ 时，$\gamma$ 的取值个数约为 $\frac{M}{K}$(设 $M=2^t$ ，下同)。

因此，对于固定的 $c$，在主要峰值区域的总概率： $ P_{\text{peak}}(c) \approx \frac{M}{K} \cdot \frac{4K}{\pi^2 M^2} = \frac{4}{\pi^2 M} $

现在考虑所有 $c$ 值。正确的 $c$ 应该满足 $c \approx \frac{jM}{r}$，其中 $r$ 是周期，$j = 0,1,\dots,r-1$。

对于每个 $j$，对应的 $c$ 在区间 $\left[\frac{jM}{r} - \frac{M}{2K}, \frac{jM}{r} + \frac{M}{2K}\right]$ 内，这个区间包含约 $\frac{M}{K}$ 个 $c$ 值。

每个这样的 $c$ 对应的峰值区域概率为 $\frac{4}{\pi^2 M}$，因此对于每个 $j$ 的总概率： $ P(j) \approx \frac{M}{K} \cdot \frac{4}{\pi^2 M} = \frac{4}{\pi^2 K} $

所有 $r$ 个 $j$ 值的总概率： $ P_{\text{total}} \approx r \cdot \frac{4}{\pi^2 K} $

由于 $K \approx \frac{M}{r}$，且 $M = 2^t > 2r^2$，我们有： $ P_{\text{total}} \approx r \cdot \frac{4}{\pi^2} \cdot \frac{r}{M} \leq \frac{4}{\pi^2} \cdot \frac{r^2}{2r^2} = \frac{2}{\pi^2} =0.202$

**五、实例分析**

这里通过具体例子来演示如何使用 Shor 算法破解椭圆曲线密码（ECC）。这个例子中的所有参数都非常小，仅用于演示原理。

## 1. 选择一条椭圆曲线和参数

我们选择一条定义在有限域 $\mathbb{F}_{11}$上的椭圆曲线： $y^2 = x^3 + x + 1$ ，其**基点G为** $(0, 1)$，通过计算不难得到基点$G$的阶$n$为7，即 $7G = \mathcal{O}$。

所以，我们的 ECC 公钥系统参数是：

$$
E: y^2 = x^3 + x + 1
$$

$G = (0, 1)$, $n=7$

计算倍点直到得到无穷远点

$G = (0, 1)，2G = (3, 3)，3G = (6, 6)，4G = (6, 5)，5G = (3, 8)，6G = (0, 10)，7G = O$

我们随机选3作为私钥即 $k=3$，那么公钥$Q$为 $Q = kG = 3G$。

因此我们的ECDLP 问题就变为了： 已知 $G=(0,1)$和 $Q=(6,6)$，求 $k$使得 $Q = kG$。

## 2. 应用 Shor 算法

现在，我们扮演量子攻击者，知道基点 $G$和公钥 $Q$，求私钥 $k$。我们首先需要用到两个寄存器，寄存器1（reg1）用于存储椭圆曲线点（由于 $p = 7$ ，需要 $t>2log_2p=2log_211$ 约8量子比特） ；寄存器2（reg2）用于存储(a,b)对（我们需要满足 $2^t > 2n^2 = 98$ ，因此选择 $t = 7$（ $2^7 = 128 > 98$ ），所以需要14量子比特） 。所以总共需要量子比特约22个(理论上，实际需要得多得多)。然后我们开始实验：

**1）初始化量子态**

$ |\psi_0\rangle = \frac{1}{128} \sum_{a=0}^{127} \sum_{b=0}^{127} |a,b\rangle |0\rangle $

**2）量子黑盒计算 $f(a,b) = aG + bQ$**

计算所有叠加态： $ |\psi_1\rangle = \frac{1}{128} \sum_{a,b} |a,b\rangle |(a + 3b) \cdot G\rangle $

**3）测量寄存器Reg1**

假设测量得到点： $P_1 = (3, 8)$ （即5G），这意味着 $a + 3b \equiv 5\ (\mod 7)$ 。寄存器2坍缩到满足该方程的所有$(a,b)$叠加态：

$ |\psi_2\rangle = \frac{1}{\sqrt{K}} \sum_{s} |5 - 3s, s\rangle $

其中 $s$ 遍历所有整数使得 $0 ≤ 5-3s < 128$ 且 $0 ≤ s < 128$

**4）量子傅里叶变换**

对寄存器2应用QFT：

$ |\psi_3\rangle = \text{QFT}|\psi_2\rangle = \frac{1}{\sqrt{K}} \sum_{c,d} \alpha_{c,d} |c,d\rangle $

其中峰值出现在： $d ≡ 3c\ (\mod 128)$

**5）测量寄存器Reg2**

假设测量得到： $(c_1, d_1) = (43,\ 129 \mod 128 = 1)$

## 3、经典算法得到私钥

上面进行一次完整实验过程，我们再次重复上面的过程2次，最后得到3个实验结果，假设实验结果如下：

$\begin{array}{c|c|c|c} 测量Reg1:P & P_G&Reg1坍缩条件&测量Reg2:(c,d)\in [0,127] \\ \hline  P_1=(3,8)& 5G&a + kb ≡ 5 (mod 7)& (43,1)\\ P_1=(6,5)& 4G&a + kb ≡ 4 (mod 7)& (29, 87)\\ P_1=(0,10)& 6G&a + kb ≡ 6 (mod 7)& (57,43)\\\end{array}$

根据同余方程 $kc\approx d(mod\ 2^t)$ 得到方程组：

$\begin{cases}      43k\equiv 1&\mod\ 128\\    29k\equiv 87&\mod\ 128\\ 57k\equiv 43&\mod\ 128\\ \end{cases}$

由于私钥范围是 0 ≤ k < 7，且 k ≡ 3 (mod 128)： $ k = 3 $ 。可以验证，上述的模拟实验结果几乎都是刚好位于相长干涉的峰值上，也就是刚好 $\gamma=\frac{d-kc}{2^7}$ 为整数的理想情况下。但现实中量子计算机存在显著的噪声和误差，这会导致非整数情况，那我们该如何处理？比如我们测量得到：

$ (c, d) = (29, 88)$ 即 $d-kc=88 - 3×29 = 88 - 87 = 1$

因此 $\frac{d-kc}{2^7}=\frac{1}{2^7}$ ，无法整除。此时我们需要通过连分数展开来得到真实的私钥k。当然如果实验误差较大也可以通过连分数展开来进行排除。

连分数展开如下：

$\frac{88}{29}=3+\frac{1}{29}=[3;29]$

因此渐进分数为：$3/1$，$88/29$ 。然后我们通过公式：$|d g_i - h_i c|<\sigma$ 来判定误差 $\delta$ 的容忍程度( $\sigma$ 我们可以取 $0.5n=0.5\times 7=3.5$ )。

对于渐近分数 $ \frac{h_1}{g_1}=\frac3 1$ : $\delta=|1×88-3×29| = |88-87| = 1$

对于渐近分数  $ \frac{h_2}{g_2}= \frac{88}{29}$ : $\delta=|88×29 - 29×88| = |2552 - 2552| = 0$

看来两个都是可以接受的误差。然后通过 $k_i=h_i\cdot g_i^{-1} \mod 2^t$ 计算候选私钥。

$k_1\equiv 3\times 1^{-1}=3 (\mod 7)\\ k_2\equiv88\times 29^{-1}\equiv 88\times 53\equiv 56\equiv 0(\mod 7)$

最后带入椭圆曲线满足$Q=kG$等式进行验证，筛选出正确的私钥，通过验证只有 $k_1=3$ 满足，从而正确地找到私钥。本例子是一个简单的演示，以便帮助大家理解Shor算法利用量子特性破解椭圆曲线密码的过程。

**六、总结**：

总算完结了，通过上面的分析可以看出，整个算法过程连分数展开是多项式时间的，而量子部分需要 $O(t)$ 个量子比特 $t=O(\log n)$ ，而量子黑盒（计算椭圆曲线点加和标量乘）的电路深度是 $O(m^2)$ 或 $O(m^3)$ （其中 $m=O(\log p)$ 是域元素的比特长度，p是定义域的素数，n是阶，通常 $\log p≈\log n$ ）。因此，总量子门复杂度为多项式级别 $O((\log n)^3)$ 。

在量子算法层面，椭圆曲线的量子电路远比RSA复杂，因为我们必须实现椭圆曲线点加法和标量乘法的量子电路，还需要实现有限域上的算术运算（模加、模乘、模逆），这需要大量辅助量子比特和量子门。目前量子计算机所制备量子比特数还不足以运行实际参数的算法，例如，破解256位ECC需要数千个逻辑量子比特，而为了实现量子纠错至少需要上百万个量子比特才有可能实现真正效果。

参考文章：
Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press: 124–134

登录后可查看完整内容

冰与火的战歌：Windows内核攻防实战高级班！从零到实战，融合AI与Windows内核攻防全技术栈，打造具备自动化能力的内核开发高手。

最后于 2026-1-20 13:48 被gjden编辑，原因：

#系统底层 #加密算法

收藏・16

点赞・14

打赏

最新回复 (8)
kanxue 雪币： 22717 活跃值： (24835) 能力值： (RANK：350 ) 在线值：发帖 2406 回帖 17125 粉丝 746 关注私信	kanxue 8 2 楼这篇文章分析得很深入，量子破解椭圆曲线密码学的内容很有挑战性，很前沿。感谢分享！ 2026-1-14 18:01 1
蜕无痕雪币： 2217 活跃值： (3327) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 25 粉丝 143 关注私信	蜕无痕 3 楼顶尖 2026-1-14 18:29 0
readyu 雪币： 11685 活跃值： (1006) 能力值： ( LV12，RANK：779 ) 在线值：发帖 36 回帖 393 粉丝 56 关注私信	readyu 12 4 楼感谢精彩的文章！在乐观的情况下，未来十年，有可能实现32 位 ECDLP 的计算，成为量子计算领域 “验证 ECDLP 破解能力” 的首个里程碑？采用超导量子计算机技术方案，成本可能需要从10亿美元量级，下降到1亿美元量级？ 2026-1-14 20:44 0
TeLeMan 雪币： 97 活跃值： (3348) 能力值： ( LV4，RANK：50 ) 在线值：发帖 14 回帖 132 粉丝 8 关注私信	TeLeMan 1 5 楼 readyu 感谢精彩的文章！在乐观的情况下，未来十年，有可能实现32 位 ECDLP 的计算，成为量子计算领域 “验证 ECDLP 破解能力” 的首个里程碑？采用超导量子计算机技术方案，成本可能需要从10亿美元 ... 7fdK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6%4N6%4N6Q4x3X3g2&6L8%4g2@1N6h3u0W2i4K6u0W2j5$3!0E0i4K6u0r3N6$3q4@1j5$3S2Q4x3@1k6$3i4K6y4p5g2$3g2h3c8@1A6J5y4X3S2Q4x3X3c8o6f1g2)9J5y4X3&6T1M7%4m8Q4x3@1u0Q4c8e0c8Q4b7U0S2Q4z5p5c8Q4c8e0S2Q4b7e0k6Q4z5o6q4Q4c8e0g2Q4b7e0c8Q4b7f1q4Q4c8e0c8Q4b7U0W2Q4z5e0m8Q4c8e0S2Q4b7e0N6Q4z5o6t1`. 2026-1-15 09:50 0
ioshackery 雪币： 1091 活跃值： (76) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 9 粉丝 1 关注私信	ioshackery 6 楼高端、大气、上档次 2026-1-17 10:58 0
海风月影雪币： 7546 活跃值： (4339) 能力值： (RANK：1130 ) 在线值：发帖 93 回帖 2318 粉丝 127 关注私信	海风月影 22 7 楼太猛了！！ 2026-1-17 21:53 0
轻装前行雪币： 800 活跃值： (3402) 能力值： ( LV2，RANK：10 ) 在线值：发帖 13 回帖 118 粉丝 0 关注私信	轻装前行 8 楼中本聪钱包瑟瑟发抖？ 2026-1-19 18:04 0
舒默哦雪币： 6956 活跃值： (6218) 能力值： ( LV11，RANK：180 ) 在线值：发帖 11 回帖 162 粉丝 126 关注私信	舒默哦 4 9 楼看不懂，不影响我点赞 2026-1-21 10:15 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

gjden

发帖

447

回帖

640

RANK

关注

私信

他的文章

关于我们

联系我们

企业服务

看雪公众号

最新回复 (8)
kanxue 雪币： 22717 活跃值： (24835) 能力值： (RANK：350 ) 在线值：发帖 2406 回帖 17125 粉丝 746 关注私信	kanxue 8 2 楼这篇文章分析得很深入，量子破解椭圆曲线密码学的内容很有挑战性，很前沿。感谢分享！ 2026-1-14 18:01 1
蜕无痕雪币： 2217 活跃值： (3327) 能力值： ( LV3，RANK：20 ) 在线值：发帖 4 回帖 25 粉丝 143 关注私信	蜕无痕 3 楼顶尖 2026-1-14 18:29 0
readyu 雪币： 11685 活跃值： (1006) 能力值： ( LV12，RANK：779 ) 在线值：发帖 36 回帖 393 粉丝 56 关注私信	readyu 12 4 楼感谢精彩的文章！在乐观的情况下，未来十年，有可能实现32 位 ECDLP 的计算，成为量子计算领域 “验证 ECDLP 破解能力” 的首个里程碑？采用超导量子计算机技术方案，成本可能需要从10亿美元量级，下降到1亿美元量级？ 2026-1-14 20:44 0
TeLeMan 雪币： 97 活跃值： (3348) 能力值： ( LV4，RANK：50 ) 在线值：发帖 14 回帖 132 粉丝 8 关注私信	TeLeMan 1 5 楼 readyu 感谢精彩的文章！在乐观的情况下，未来十年，有可能实现32 位 ECDLP 的计算，成为量子计算领域 “验证 ECDLP 破解能力” 的首个里程碑？采用超导量子计算机技术方案，成本可能需要从10亿美元 ... 7fdK9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6%4N6%4N6Q4x3X3g2&6L8%4g2@1N6h3u0W2i4K6u0W2j5$3!0E0i4K6u0r3N6$3q4@1j5$3S2Q4x3@1k6$3i4K6y4p5g2$3g2h3c8@1A6J5y4X3S2Q4x3X3c8o6f1g2)9J5y4X3&6T1M7%4m8Q4x3@1u0Q4c8e0c8Q4b7U0S2Q4z5p5c8Q4c8e0S2Q4b7e0k6Q4z5o6q4Q4c8e0g2Q4b7e0c8Q4b7f1q4Q4c8e0c8Q4b7U0W2Q4z5e0m8Q4c8e0S2Q4b7e0N6Q4z5o6t1`. 2026-1-15 09:50 0
ioshackery 雪币： 1091 活跃值： (76) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 9 粉丝 1 关注私信	ioshackery 6 楼高端、大气、上档次 2026-1-17 10:58 0
海风月影雪币： 7546 活跃值： (4339) 能力值： (RANK：1130 ) 在线值：发帖 93 回帖 2318 粉丝 127 关注私信	海风月影 22 7 楼太猛了！！ 2026-1-17 21:53 0
轻装前行雪币： 800 活跃值： (3402) 能力值： ( LV2，RANK：10 ) 在线值：发帖 13 回帖 118 粉丝 0 关注私信	轻装前行 8 楼中本聪钱包瑟瑟发抖？ 2026-1-19 18:04 0
舒默哦雪币： 6956 活跃值： (6218) 能力值： ( LV11，RANK：180 ) 在线值：发帖 11 回帖 162 粉丝 126 关注私信	舒默哦 4 9 楼看不懂，不影响我点赞 2026-1-21 10:15 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复