ECC

2026-04-05/更新于 2026-07-15

简介

ECC 的数学基础是椭圆曲线，一般用形如 $y^{2} = x^{3} + a x + b$ 的方程表示。在曲线上取一个点，按照椭圆曲线群上特定的数学规则，我们让这一点与自身相加 $n$ 次，最终得到另一点。其中，相加次数 $n$ 作为私钥，终点坐标作为公钥。根据椭圆曲线上的离散对数问题，从起点坐标和 $n$ 得到终点坐标很简单，但从起点坐标和终点坐标想要得到 $n$ 却极难。在真正的密码学中，我们不能使用实数域上的椭圆曲线。因为不仅计算机会有浮点数误差，也不能保证非对称加密的安全。所以 ECC 会将椭圆曲线定义在有限域内，目前常用的两大类是 素数域和二进制域（或特征为 2 的伽罗华域），后者主要在底层硬件上使用。

ECC 的优点在于用极短的密钥，实现极高的安全性。一个 256 位的 ECC 密钥提供的安全级别，大概相当于一个 3072 位的 RSA 密钥。

群上的运算

对于常用于加密的 Weierstrass 方程：

y^{2} = x^{3} + a x + b, Δ = 4 a^{3} + 27 b^{2} \neq 0

在素数域 $G F (p)$ 上，写作：

y^{2} \equiv x^{3} + a x + b (\mod p)

在曲线上若有两个不同点 $P, Q$ , 二者相加得到的点 $R$ 就是 $P, Q$ 两点所连成的直线与椭圆曲线的交点沿着 $x$ 轴翻转的点（纵坐标取反）。若是自己与自己相加，结果就是这个点的切线与椭圆曲线的交点再翻转。ECC 加密算法是对某点的不断相加。椭圆曲线由曲线上的所有点和一个看不到的无穷远点组成，后者作为单位元存在。若是一个点与无穷远点相加，得到的结果依旧是它自身。在有限群内，元素的运算是周期性循环的。当相加次数 $n$ 正好等于起始点的阶时，结果是无穷远点。上述的“画线求交点”，实际上也是实数域的概念。对于素数域的椭圆曲线，若 $P, Q$ 相异，加法实现如下：

先求斜率。 $k \equiv (y_{2} - y_{1}) \times (x_{2} - x_{1})^{- 1} (\mod p)$
代入椭圆曲线方程， $(k (x - x_{1}) + y_{1})^{2} = x^{3} + a x + b$
展开成标准形式， $x^{3} - k^{2} x^{2} + (a + 2 k^{2} x_{1} - 2 k y_{1}) x + (b - k^{2} x_{1}^{2} + 2 k y_{1} x_{1} - y_{1}^{2}) = 0$
使用韦达定理， $x_{1} + x_{2} + x_{3} = - (- k^{2}) = k^{2}$
最终取模后得到目标点的横坐标 $x_{3}$ ， $x_{3} \equiv (k^{2} - x_{1} - x_{2}) (\mod p)$
取反后得到纵坐标 $y_{3} \equiv k (x_{1} - x_{3}) - y_{1} (\mod p)$

若是 $P, Q$ 相同，只在第一步有变化。此时 $k \equiv (3 x_{1}^{2} + a) \times (2 y_{1})^{- 1} (\mod p)$ ，由隐函数求导得到。

几种常见的曲线参数

（先贴上吧，我还不知道怎么用）

#NIST P-256（Secp256r1）
#p = 2^224(2^32 − 1) + 2^192 + 2^96 − 1
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

#Secp256k1（比特币使用）
#p = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 = 2^256 – 2^32 – 977 
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7

#NIST P-384
#p = 2^384 – 2^128 – 2^96 + 2^32 – 1
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575

#NIST P-521
p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a = -3
b = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984

在 sagemath 中，定义 Weierstrass 方程的广义形式 $y^{2} + a_{1} x y + a_{3} y = x^{3} + a_{2} x^{2} + a_{4} x + a_{6}$ ，使用函数 EllipticCurve([a1, a2, a3, a4, a6])。当前三个参数为 0 时，退化成短 Weierstrass 形式 $y^{2} = x^{3} + a x + b$ ，此时语法变为常见的 EllipticCurve([a, b])。

尖点与结点

在代数几何和密码学中，我们要求椭圆曲线是平滑的。但如果定义曲线的方程出现奇点，这条曲线在严格意义上会退化为奇异三次曲线。这类曲线上的奇点分为两类：结点和尖点。

以简化 Weierstrass 方程为例：

f (x, y) = y^{2} - x^{3} - a x - b = 0

其判别式为 $Δ = - 16 (4 a^{3} + 27 b^{2})$ 。当 $Δ = 0$ 时，曲线出现奇点。

求奇点坐标的方法是利用偏导。对于上述二元函数，若一个点 $(x_{0}, y_{0})$ 是奇点，当且仅当它满足以下三个条件：

$f (x_{0}, y_{0}) = 0$ （点在曲线上）
$\frac{\partial f}{\partial x} (x_{0}, y_{0}) = 0$
$\frac{\partial f}{\partial y} (x_{0}, y_{0}) = 0$

（对于上面的简化方程，一定有 $y = 0, x^{2} = \frac{- a}{3}, x^{3} + a x + b = 0$ ）

求出奇点后，可以通过将坐标原点平移到奇点，观察方程的 最低次齐次多项式（即次数最低，且系数不为 0 的所有项之和）。若它们可以被因式分解为不同的线性因子（如 $y^{2} - α^{2} x^{2} = (y - α x) (y + α x)$ 这种分解），则证明是结点。反之，如最低二次项是一个完全平方项（如 $y^{2}$ ），则是尖点。

简化方程

尖点

对于一般多项式 $x^{3} + a x + b$ ，它有一个三重根时出现尖点。也就是说，方程可以写成 $y^{2} = (x - e_{1})^{3}$ 的形式。这意味着 $a = b = 0$ ，图像：

假设曲线的尖点已被平移到原点，我们研究方程 $y^{2} = x^{3}$ 。

引入参数 $t$ ，对于曲线上任意一个 平滑点（除奇点外的点），我们将其映射在 $t$ 上，满足：

t = \frac{x}{y}

同时也有逆映射。即如果知道 $t$ ，我们也能找到曲线上的点，满足：

x = \frac{1}{t^{2}}, y = \frac{1}{t^{3}}

尖点映射在 加法群 上，即对于这种具有尖点的奇异椭圆曲线，两点之和的运算步骤如下：

算出 $t_{1} = \frac{x_{1}}{y_{1}}, t_{2} = \frac{x_{2}}{y_{2}}$
计算 $t_{3} = t_{1} + t_{2}$
逆映射回坐标点，得到 $x_{3} = \frac{1}{{t_{3}}^{2}}, y_{3} = \frac{1}{{t_{3}}^{3}}$

在这样的奇异曲线上，如果已知 $P, Q$ ，且有 $Q = k P$ ，那么有结果：

k = t_{Q} \times {t_{P}}^{- 1} (\mod p)

结点

结点比尖点略微复杂，但比一般的椭圆曲线简单。对于一般多项式 $x^{3} + a x + b$ ，它有一个二重根时出现结点。也就是说，方程可以写成 $y^{2} = (x - e_{1})^{2} (x - e_{2}), e_{1} \neq e_{2}$ 的形式。图像：

假设曲线的结点已被平移到原点，我们研究方程 $y^{2} = x^{3} + c x^{2}$ 。

设 $α = \sqrt{c}$ ，引入参数 $u$ ，对于曲线上任意一个 平滑点，我们将其映射在 $u$ 上，满足：

u = \frac{y + α x}{y - α x}

逆映射：

x = \frac{4 α^{2} u}{(u - 1)^{2}}, y = \frac{4 α^{3} u (u + 1)}{(u - 1)^{3}}

结点映射在 乘法群 上，求两点之和只需要计算 $u_{1}, u_{2}$ ，再算 $u_{3} = u_{1} \times u_{2}$ ，最后逆映射回去。

在这样的奇异曲线上，如果已知 $P, Q$ ，且有 $Q = k P$ ，那么有方程：

u_{Q} = (u_{P})^{k} (\mod p)

这是一个在有限域乘法群上的离散对数问题，可以用 sagemath 的函数 discrete_log() 求解 $k$ 。

一般方程

研究一般方程的方法和简化方程的办法基本一致。对于一般的 Weierstrass 方程：

f (x, y) = y^{2} + a_{1} x y + a_{3} y - x^{3} - a_{2} x^{2} - a_{4} x - a_{6} = 0

如果在处理这种曲线时 sagemath 回显 xxx defines a singular curve，证明有奇点。值得注意的是，全过程都需要在素数域上研究，并在域上定义多项式环。代码方面体现在所有的常数都应该用域符号 F() 包裹。

研究过程分为以下几步：

Step 1

由奇点处的梯度为 0，得到：

$\frac{\partial f}{\partial y} = 2 y + a_{1} x + a_{3} = 0$
$\frac{\partial f}{\partial x} = a_{1} y - 3 x^{2} - 2 a_{2} x - a_{4} = 0$

由(1)式得到 $y$ 关于 $x$ 的显函数：

y = - \frac{a_{1} x + a_{3}}{2}

代入式(2)，得到只含有 $x$ 的一元二次方程：

a_{1} (- \frac{a_{1} x + a_{3}}{2}) - 3 x^{2} - 2 a_{2} x - a_{4} = 0

将得到的 $x_{0}$ 代入显函数式中得到 $y_{0}$ ，再回代进曲线方程验证，就能得到奇点。

Step 2

将坐标原点平移到奇点，定义新的坐标轴：

x = X + x_{0}, y = Y + y_{0}

将平移关系代入原方程，消去后得到新方程：

Y^{2} + a_{1} X Y - c X^{2} - X^{3} = 0, c = 3 x_{0} + a_{2}

Step 3

此时奇点已经在原点。由平移后的方程知道三次项 $X^{3}$ 趋近于 0，二次齐次多项式决定了切线斜率。

对于二次项 $Y^{2} + a_{1} X Y - c X^{2} = 0$ ，两边同除以 $X^{2}$ 。令切线方程为 $Y = t X$ ，有：

t^{2} + a_{1} t - c = 0

解这个一元二次方程。若有两个相异的根，证明奇点有两条不同切线，是结点。若只有一个重根，证明奇点只有一条重切线，是尖点。如果无解，则曲线上的是 非分裂结点，需要构建二次扩域。

Step 4

类似简化方程的映射，这里直接给出映射公式。

若是结点，记上述方程得到的两个异根为 $m_{1}, m_{2}$ ，有：

u = \frac{Y - m_{1} X}{Y - m_{2} X}

若是尖点，记根为 $m$ ，有：

τ = \frac{X}{Y - m X}

Step 5

对于 $Q = k P$ ，若是结点：

u_{Q} = u_{P}^{k} (\mod p)

调用 discrete_log() 即可。若是尖点：

k = τ_{Q} \cdot τ_{P}^{- 1} (\mod p)

直接计算 k = tauQ / tauP。

下面是脚本：

def singular_curve_attack(p, a1, a2, a3, a4, a6, P, Q):
    p = p
    F = GF(p)
    R_x.<x> = F[]
    a1 = F(a1);a2 = F(a2);a3 = F(a3);a4 = F(a4);a6 = F(a6)
    Px = F(P[0]);Py = F(P[1])
    Qx = F(Q[0]);Qy = F(Q[1])
    # 利用对 y 的偏导得到 y 关于 x 的显函数
    yx = - (a1*x + a3)/F(2)
    # 代入对 x 的偏导式子
    fx = a1*yx - F(3)*x*x - F(2)*a2*x - a4
    # 对 fx 求根，得到可能是奇点的 x 坐标，之后回代进曲线方程验证
    roots = fx.roots()
    x0, y0 = None, None
    # 调用 roots 方法后，返回的是（解，重数）
    for root_couple in roots:
        x_temp = root_couple[0]
        y_temp = - (a1*x_temp + a3)/F(2)
        # 一般方程移项后的值，验证 val 是否等于 0
        val = y_temp^2 + a1*x_temp*y_temp + a3*y_temp - x_temp^3 - a2*x_temp^2 - a4*x_temp - a6
        if val == F(0):
            x0, y0 = x_temp, y_temp
            print("得到奇点坐标")
            break
    if x0 is None:
        print("未找到奇点")
        exit()
    # 根据上面的分析，引入切线方程，构建新环。这里的 c 是平移后方程的二次项系数，也是切线方程的常数项
    c = F(3)*x0 + a2
    R_t.<t> = F[]
    ft = t^2 + a1*t - c
    roots = ft.roots()
    if len(roots) == 2:
        print("奇点是结点")
        m1 = roots[0][0]
        m2 = roots[1][0]
        # 计算平移后的坐标
        PX = Px - x0;PY = Py - y0
        QX = Qx - x0;QY = Qy - y0
        # 计算映射
        uP = (PY - m1*PX) / (PY - m2*PX)
        uQ = (QY - m1*QX) / (QY - m2*QX)
        k = discrete_log(uQ, uP)
        print(f"得到k = {k}")
    elif len(roots) == 1:
        print("奇点是尖点")
        m = roots[0][0]
        # 计算平移后的坐标
        PX = Px - x0;PY = Py - y0
        QX = Qx - x0;QY = Qy - y0
        # 计算映射
        tauP = PX / (PY - m*PX)
        tauQ = QX / (QY - m*QX)
        k = tauQ / tauP
        print(f"得到k = {k}")
    else:
        print("奇点是非分裂结点")
        K.<a> = F.extension(2)
        ft_ext = ft.change_ring(K)
        roots = ft.ext.roots()
        m1 = roots[0][0]
        m2 = roots[1][0]
        PX = K(Px - x0);PY = K(Py - y0)
        QX = K(Qx - x0);QY = K(Qy - y0)
        uP = (PY - m1*PX) / (PY - m2*PX)
        uQ = (QY - m1*QX) / (QY - m2*QX)
        k = discrete_log(uQ, uP, ord = p + 1)
        print(f"得到k = {k}")

ElGamal 算法

椭圆曲线上的 ElGamal 加密算法，是将传统的 ElGamal 算法从有限域乘法群移植到椭圆曲线加法群上的变体。它的安全性建立在椭圆曲线离散对数问题（ECDLP）的困难性之上。对于标准的 ElGamal，其依赖于离散对数难题（DLP），加解密流程如下：

在进行通信前，接收方需要生成一对公私钥。
- 选取一个大素数 $p$ ，以及模 $p$ 乘法群的一个生成元 $g$ 。
- 随机选择一个整数 $x$ ，要求 $1 < x < p - 1$ ，作为私钥，严格保密。
- 计算 $y \equiv g^{x} (\mod p)$ ，作为公钥。
假如加密方要发送消息 $m$ 给接收方，需要使用 $(p, q, y)$ 进行加密，且需要保证 $m < p$ ，防止消息截断。
- 每次加密时，必须随机选择一个临时密钥 $k$ ，要求 $1 < k < p - 1$ ，且与 $p - 1$ 互质，每次加密后都要更换。
- 计算 $c_{1} \equiv g^{k} (\mod p)$ ，相当于把 $k$ 加密起来。
- 计算掩码 $s \equiv y^{k} (\mod p)$ ，用来掩盖明文。
- 计算 $c_{2} = m \cdot s (\mod p)$ 。
最终生成的密文是一个数对 $(c_{1}, c_{2})$ 。
接收方收到 $(c_{1}, c_{2})$ 之后，使用自己的私钥 $x$ 进行解密。
- 恢复掩码。 $s = c_{1}^{x} (\mod p)$ ，因为 $c_{1}^{x} = (g^{k})^{x} = (g^{x})^{k} = y^{k} = s (\mod p)$ 。
- 计算 $s$ 关于 $p$ 的逆元，即满足 $s \cdot s^{- 1} \equiv 1 (\mod p)$ 的 $s^{- 1}$ 。
- 恢复明文。 $m = c_{2} \cdot s^{- 1} (\mod p)$ 。

想要了解椭圆曲线上的 ElGamal 加密，得先明白一些名词的意思：

生成元 $G$ ：被公开的初始点，密钥生成从这个点开始。
阶 $n$ ：生成元 $G$ 的阶。数值代表点 $G$ 不断与自身相加，到达无穷远点所需要的次数。由于由基点生成的子群是循环的，所以也表示该基点能够产出不同点的数目。
私钥 $n_{a}$ ：加密方选定，表示进行多少次加法运算。
公钥 $P_{a}$ ：把生成元 $G$ 倍加 $n_{a}$ 次得到的点坐标。
随机量 $k$ ：每次发送消息时随机在范围 $(1, n - 1)$ 中选取，用于保证每次生成的密文都不相同。

不仅基点有阶，曲线也有阶的概念。

曲线的阶通常用 $N$ 表示，数值上等于椭圆曲线上所有合法坐标点的总数。
基点的阶用 $n$ 表示。如上文所述，数值代表点 $G$ 不断与自身相加，到达无穷远点所需要的次数。

群论中，拉格朗日定理规定：基点的阶 $n$ ，一定能被曲线的阶 $N$ 整除。写成公式：

N = h \times n

也就是说，对于一条曲线，当曲线的阶 $N$ 为质数时，基点一定能通过自身的倍加，遍历到曲线上每一个合法点（因为 $N$ 不能被质因数分解，即 $h = 1$ ， $n = N$ ），典型的例子是计算比特币使用的 secp256k1 曲线。相反的，如果 $N$ 能被分解成很多小质数，那么无论再怎么选取基点，能遍历到的点只有曲线的一部分。

加密

选取随机数 $k$
计算点 $C_{1} = k G$ 作为辅助点
计算点 $K = k P_{a}$ 。若是无穷远点，则再次生成
计算点 $C_{2} = M + K$

加密时需要的参数有 $E_{p} (a, b), G, P_{a}$ ，示例代码：

import random
a = 
b = 
p = 
E = EllipticCurve(GF(p),[a,b])
G = E( , )
n = G.order()
Pa = E( , )

M = E( , ) # 消息映射点
k = random.randint(1,n-1)
C1 = k*G
K = k*Pa
C2 = M + K

解密

计算 $n_{a} C_{1} = n_{a} k G = k (n_{a} G) = k P_{a} = K$
得到 $M = C_{2} - K$

解密时需要的参数有 $E_{p} (a, b), n_{a}, C_{1}, C_{2}$ ，示例代码：

a = 
b = 
p = 
E = EllipticCurve(GF(p),[a,b])
C1 = E( , )
C2 = E( , )
na = 
M = C2 - na*C1

举个例子，当 $p = 17, a = 2, b = 2, G = (5, 1), n_{a} = 3$ 时，假设 $M = (9, 16)$ ：

选取 $k = 15$ ，此时得到 $C_{1} = k G = (3, 16)$ 。又 $P_{a} = n_{a} G = (10, 6)$ ， $C_{2} = k P_{a} + M = (0, 11)$

解密时，得到 $M = C_{2} - n_{a} C_{1} = (9, 16)$

值得注意的是，sage 输出的坐标有三个参数，是射影坐标。想得到普通坐标，只需用前两个参数除以第三个参数（如 $(9 : 16 : 1)$ 就是 $(9, 16)$ ），或者在末尾调用 .xy() 方法。

算法、定理与攻击

算法

对于一个简单的加密过程（ $k$ 不参与，只有椭圆曲线 $E$ ，基点 $G$ ，私钥 $n_{a}$ 和公钥 $P_{a}$ ）：

当曲线有弱点时（比如曲线的阶很小，或并非光滑曲线），可以调用 na = discrete_log(Pa, G, operation='+') 直接获取私钥 $n_{a}$ 。这个函数还有一个参数 algorithm，可以指定以下三种破译算法：

大步小步法

algorithm='bsgs'，空间换时间的典型算法，把数乘得到的结果存进表里，只到 $\sqrt{p}$ ，最终使用大数寻找满足 $n_{a} G = P_{a}$ 的私钥 $n_{a}$ 。

Pollard’s rho 算法

algorithm='rho'，假设曲线上有两点做伪随机跳跃，只要跳跃时间够长，它们必定会在某一点碰撞。只要碰撞，根据步数的差值，便能解密出私钥 $n_{a}$ 。时间复杂度和方法一相同，但空间复杂度为 $O (1)$ 。

Pohlig-Hellman 算法

algorithm='pohlig_hellman'，对于一条不好的曲线或者一个不好的基点（曲线阶 $N$ 或基点阶 $n$ 能被分解），这个算法能使用 CRT 把破译任务分解，进而很快得出结果。

定理

哈斯定理

p + 1 - 2 \sqrt{p} \leq N \leq p + 1 + 2 \sqrt{p}

这个定理规定了曲线阶 $N$ 的范围与素数 $p$ 相关，且在正规加密中，二者大致相等。这也是为什么在大步小步法中，算法只遍历到 $\sqrt{p}$ 也没关系，因为 $p$ 和 $N$ 数量级接近，不会影响效率。

如果曲线的阶 $N = p$ ，此时虽然 $N$ 是质数，但是可以进行 Smart’s Attack 攻击（同构映射），使得原本不可解的私钥在几毫秒内被破解出来。对于一般的曲线阶 $N$ ，通常使用 Pohlig-Hellman 算法，即分解 $N$ 。但是就算 $N$ 不可分解，若是选取了坏基点，使得 $n$ 可被分解，Pohlig-Hellman 算法依旧能生效。

费马小定理

a^{p - 1} \equiv 1 (\mod p) gcd (a, p) = 1

计算机无法直接计算模逆元。我们对费马小定理变形：

a \times a^{p - 2} \equiv 1 (\mod p)

此时 $a^{p - 2} (\mod p)$ 就是 $a$ 的模逆元。

CRT

{\begin{cases} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \end{cases}, gcd (m_{1}, m_{2}) = 1 \Rightarrow x \equiv a_{1} M_{1} M_{1}^{- 1} + a_{2} M_{2} M_{2}^{- 1} (\mod m_{1} m_{2})

CRT 主要应用于上述的 Pohlig-Hellman 算法，以及合数环 $Z_{N}$ 上的 ECC。

类似 RSA 中利用 CRT 加速，ECC 也可以利用 CRT 加速。先算 $Q_{p} = (d mod o r d e r_{p}) \times P (\mod p)$ ，再算 $Q_{q} = (d mod o r d e r_{q}) \times P (\mod q)$ 。算完两个小结果后合并，就能得到最终的 $Q$ 。CRT 在 ECC 中很重要。

攻击

Smart Attack

当曲线的阶等于 $p$ 时应用的攻击：

def smart_attack(p, A, B, P, Q):
    """
    针对异常曲线 (Anomalous Curve) 的 Smart's Attack
    适用条件：曲线的阶 N 严格等于素数域 p (N == p)
    数学目标：求解 Q = d * P 中的私钥 d
    """
    E = EllipticCurve(GF(p), [A, B])
    Px = P[0];Py = P[1];Qx = Q[0];Qy = Q[1]
    P = E(Px, Py)
    Q = E(Qx, Qy)
    
    Eqp = EllipticCurve(Qp(p, 2), [ZZ(t) for t in E.a_invariants()])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_P = p * P_Qp
    p_Q = p * Q_Qp

    x_P, y_P = p_P.xy()
    x_Q, y_Q = p_Q.xy()

    phi_P = -(x_P / y_P)
    phi_Q = -(x_Q / y_Q)

    d = phi_Q / phi_P
    
    print(f"d = {ZZ(d) % p}")

Pohlig-Hellman Attack

当曲线的阶能被分解成多个素数，且各个素因子都不是很大时，使用这个攻击方法：

def normal_attack(p, A, B, P, Q):
    E = EllipticCurve(GF(p), [A, B])
    Px = P[0];Py = P[1];Qx = Q[0];Qy = Q[1]
    P = E(Px, Py)
    Q = E(Qx, Qy)
    N = E.order()
    try:
        d = discrete_log(Q, P, ord=N, operation='+')
        print(f"d = {d}")
    except ValueError:
        print("None")

Pohlig-Hellman Attack 2.0

若曲线的阶中有大素数，导致原始的 Pohlig-Hellman 算法变得无法实现，我们可以手动实现这个攻击，并剔除大素数，得到私钥的片段，最后根据私钥的实际大小或取值范围，通过离散对数求解获得真正的私钥。

def big_factor_attack(p, A, B, P, Q, limit=0):
    E = EllipticCurve(GF(p),[A,B])
    P = E(P[0],P[1]);Q = E(Q[0],Q[1])
    # 对阶进行因数分解
    factors, exponents = zip(*factor(P.order()))
    # 计算每个质因数幂 pi^ei，切掉最后一个因子
    primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
    M = P.order() // primes[-1]
    length = primes[-1].bit_length()
    primes = primes[:-1]
    print(f"去除最大素因子后的质因数表: {primes}")
    print(f"它们的乘积是 {M}")
    print(f"最大素因子的二进制长度为 {length} bit，{'建议保留' if length <= 50 else '建议舍弃'}")
    dlogs = []
    for fac in primes:
        # 将点映射到阶为 fac 的子群中
        t = int(int(P.order()) // int(fac))
        # 在子群中求解离散对数
        dlog = discrete_log(t * Q, t * P, operation="+")
        dlogs += [dlog]
    # 使用 CRT 合并结果
    m_partial = CRT_list(dlogs, primes)
    print(f"m_partial = {m_partial}")
    if limit is not 0:
        # 新基点
        P_new = M*P
        Q_new = Q - m_partial*P
        i = discrete_log(Q_new, P_new, bounds=(0, limit), operation='+')
        m = m_partial + i*M
        print(f"m = {m}")

MOV Attack

当基点的阶能够整除 $p^{k} - 1$ ，且 $k$ 极小（通常 $k \leq 6$ ）时使用的攻击。

def MOV_attack(p, A, B, P, Q):
    n = P.order()
    
    k = 1
    while (p^k - 1) % n != 0:
        k += 1
        assert k <= 6
    print(f"找到k = {k}")
	
    F.<a> = GF(p^k)
    E_ext = E.base_extend(F)
    P_ext = E_ext(P)
    Q_ext = E_ext(Q)
    
    while True:
        T = E_ext.random_point()
        T = (T.order() // n) * T
        if T.order() == n and T != P_ext:
            break
    
    g = P_ext.weil_pairing(T, n)
    h = Q_ext.weil_pairing(T, n)
    
    x = discrete_log(h, g)
    print(f"私钥是{x}")

题目

（摘自 DJ 师傅的博客，wp 是自己写的）

Q1

from secret import flag
from Crypto.Util.number import *

assert(flag[:5] == b"flag{" and flag[-1:] == b"}")

flag = flag[5:-1]

d1 = bytes_to_long(flag[:len(flag)//2])
d2 = bytes_to_long(flag[len(flag)//2:])

N1 = 27544759469094453505371358768052861416297003882211878831861112512567899543941
A1 = 4208715803791813173086894172778966025419787767340027559010619240548499823390
B1 = 11846440123913040489420209031751160809904311707943252241515965930654415480691
P1x = 479750084250968709343887919962436485997147832319843477221083468203689368148
P1y = 15452861783577624143044213767588871736433639621547613407582902947429567101675

P1 = (P1x,P1y)
E1 = EllipticCurve(Zmod(N1), [0, 0, 0, A1, B1])
P1 = E1(P1)
Q1 = d1 * P1

N2 = 6471339743593595797696002766822660599108196938080465998531085409467
A2 = 3199218821393204771660095172457569312269694438403110131957204042314
B2 = 762889472027318213897694878260359911054972690369935049954326689904
P2x = 2557373437970770011124755960432555084678930336188254243278984381842
P2y = 4442763096366920105760404533052204677305995021662082361185473321644

P2 = (P2x,P2y)
E2 = EllipticCurve(Zmod(N2), [0, 0, 0, A2, B2])
P2 = E2(P2)
Q2 = d2 * P2

print(Q1)
print(Q2)
'''
(14736970297054248276364510675718632926198693034158620007675880103924809577805 : 3447209262654420855289144268810543114387612255490962015335062266658385100211 : 1)
(4834036103940457959470026215023033401071737087504569417466448644066 : 5511016821581393405975510064568222454318072088628361854656950557373 : 1)
'''

WP1

题目把 flag 分成了两部分，处理方式完全相同。这里讲一下 flag1 求解的思路。

观察到这道题的椭圆曲线定义在剩余环上，尝试进行质因数分解，得到

1 2	`N1_f1 = 92636417177965240871815246762704348071 N1_f2 = 297342668339361548416629796745639177971`

copy 题目参数：

A1 = 4208715803791813173086894172778966025419787767340027559010619240548499823390
B1 = 11846440123913040489420209031751160809904311707943252241515965930654415480691
P1x = 479750084250968709343887919962436485997147832319843477221083468203689368148
P1y = 15452861783577624143044213767588871736433639621547613407582902947429567101675
P1 = (P1x,P1y)

沿用原始的 $A 1, B 1$ ，将原始基点和原始公钥投影在小曲线上，得到两个新基点和新公钥：

E1_f1 = EllipticCurve(GF(N1_f1),[A1,B1])
E1_f2 = EllipticCurve(GF(N1_f2),[A1,B1])
P1_f1 = E1_f1(P1)
P1_f2 = E1_f2(P1)
Q1_f1 = E1_f1(Q1)
Q1_f2 = E1_f2(Q1)

使用算法攻击私钥。重点来了，这里得到的 d1_f1 和 d1_f2 是真正私钥 d1 除以新基点的阶的余数，即 $d_{1 f 1} \equiv d_{1} (\mod {order}_{P 1 f_{1}})$ 。原因在于小曲线是原曲线的投影，而“阶”衡量的是能够产生点的数目。既然整体缩小了，那么转的圈数必定有盈余，最终的目的地又不能超过小曲线自身的阶数，所以得到的就是“局部私钥”，即原始私钥对投影基点的阶取模的结果。在这之后，得到同余方程组：

{\begin{cases} d_{1} \equiv d_{1 f_{1}} (\mod {order}_{P 1 f_{1}}) \\ d_{1} \equiv d_{1 f_{2}} (\mod {order}_{P 1 f_{2}}) \end{cases}

使用 CRT 求解原始私钥 $d_{1}$ ，接着求出 flag1 即可。

d1_f1 = discrete_log(Q1_f1, P1_f1, operation='+')
d1_f2 = discrete_log(Q1_f2, P1_f2, operation='+')
order_P1_f1 = P1_f1.order()
order_P1_f2 = P1_f2.order()
d1 = crt([d1_f1,d1_f2],[order_P1_f1,order_P1_f2])
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(d1).decode())

但是，我在实操的时候发现 d1_f2 跑不出来。查看 DJ 师傅的 wp，发现了对于 $N_{1 f 2}$ 和 ${order}_{P 1 f_{2}}$ ，二者完全相同。这个时候普通的算法不起作用，而 Smart’s Attack 攻击可以奏效。于是将 d1_f2 = discrete_log(Q1_f2, P1_f2, operation='+') 替换为 Smart’s Attack 攻击脚本。

flag2 就不需要 Smart’s Attack 攻击了。最后超级拼装，得到 flag{f4b9d58c-0f2b-4d7f-8c66-7ab0ae5e4621}

Q2

print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)



def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)

WP2

对于第一和第三部分，分别是普通攻击和 smart 攻击。值得注意的是第二部分，这里的 $N$ 不是光滑数。

对于这样的情况，我们需要手动实现 Pohlig-Hellman 算法。如果只有一个非常大的素因子，且 $N / p_{b i g}$ （即剩余所有素因子的乘积）和 bytes_to_long(flag) 大致相同（就算前者小于后者，也能大幅减小搜索步长），那么就可以高效率地得到一个 $m$ 的片段。

记剩余所有素因子的乘积为 $M = N / p_{b i g}$ ，那么 $m_{p a r t i a l}$ 和 $m$ 关于 $M$ 同余，即：

m_{p a r t i a l} \equiv m (\mod M)

load("ECC.sage")

p = 146808027458411567
A = 46056180
B = 2316783294673
P = (119851377153561800, 50725039619018388)
Q = (22306318711744209, 111808951703508717)
normal_attack(p,A,B,P,Q)

p1 = 1256438680873352167711863680253958927079458741172412327087203
A1 = 377999945830334462584412960368612
B1 = 604811648267717218711247799143415167229480
P1 = (550637390822762334900354060650869238926454800955557622817950, 700751312208881169841494663466728684704743091638451132521079)
Q1 = (1152079922659509908913443110457333432642379532625238229329830, 819973744403969324837069647827669815566569448190043645544592)
big_factor_attack(p1,A1,B1,P1,Q1)

p2 = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A2 = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B2 = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
P2 = (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861, 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q2 = (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927, 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)
smart_attack(p2,A2,B2,P2,Q2)

得到 flag{025ab3d9-2521-4a81-9957-8c3381622434}

Q3

from Crypto.Util.number import bytes_to_long
from secret import flag

p = 64464091191308356774703439660771627086045800299627641179047457478059588557461
a = 31926335967105564755113987930261069322507794703287741857397622356704769886356
b = 34835808070187351680507689900273321615070127680320357724483770400791707112940
Gx = 2053202552422630348010474635096983783565667661786369125783579647572276572403
Gy = 51320753844844801021362329076409450910659564359017581255542897537756778371539

assert flag[:5] == "CnHongKe{"
assert flag[-1] == "}"

k = bytes_to_long(flag[9:-1])
assert k < 32000000000000000000000000000

Zp = Zmod(P)
EC = EllipticCurve(Zp, [a, b])
G = EC(Gx, Gy)
K = k * G
print K

# (31981799071949968743482831587417174146463993877255771340814476669214408840460 : 15144025062588325012239455117890516531350002058200271280110877844265896081387 : 1)

WP3

和 Q2 很相似，但是这里给的 k 只是片段，长度为 74bit，断言限制了长度小于 95bit。

我们发现这道题和 Q2 很相似，也很容易爆破。于是我们在 wp2 的基础上，加入一个可选的形参，让它能在得到 $m_{p a r t i a l}$ 之后进行指定范围的爆破。对于

(m_{p a r t i a l} + k \cdot M) P = Q

$M$ 是素因子的乘积。移项，有

k (M P) = Q - m_{p a r t i a l} P

将 $M P$ 看作 $P_{n e w}$ ， $Q - m_{p a r t i a l} P$ 看作 $Q_{n e w}$ ，就有

k P_{n e w} = Q_{n e w}

用 discrete_log() 函数求解完整的 $k$ ，进而得到真正的 $m$ 。

load("ECC.sage")
Q = (31981799071949968743482831587417174146463993877255771340814476669214408840460 , 15144025062588325012239455117890516531350002058200271280110877844265896081387)
p = 64464091191308356774703439660771627086045800299627641179047457478059588557461
A = 31926335967105564755113987930261069322507794703287741857397622356704769886356
B = 34835808070187351680507689900273321615070127680320357724483770400791707112940
P = (2053202552422630348010474635096983783565667661786369125783579647572276572403,51320753844844801021362329076409450910659564359017581255542897537756778371539) 
big_factor_attack(p, A, B, P, Q, 2**21)

得到 CnHongKe{factor_ordeq}