椭圆曲线攻击思路整理

椭圆曲线攻击思路整理

捋一下常见的ecc的出题角度吧

以后还是新题就在此贴后长期更新

小阶攻击(Smart’s Attack / Pohlig-Hellman)

核心原理

如果 #E(Fp)\#E(\mathbb{F}_p) 的因子分解中包含小素因子,则 ECDLP 可以通过 Pohlig-Hellman 算法分治求解。

Pohlig-Hellman 思想:

设 n=p1e1⋅p2e2⋯pkekn = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k},则:

k mod n=CRT(k mod p1e1,  k mod p2e2,  …,  k mod pkek)k \bmod n = \text{CRT}(k \bmod p_1^{e_1},\; k \bmod p_2^{e_2},\; \ldots,\; k \bmod p_k^{e_k})

对每个小因子 pieip_i^{e_i},单独求解 k mod pieik \bmod p_i^{e_i}(BSGS 或直接枚举),然后用中国剩余定理合并。

Smart’s Attack(异常曲线):

当 #E(Fp)=p\#E(\mathbb{F}_p) = p 时(即 t=1t = 1,Frobenius 迹为 1),曲线是异常曲线,ECDLP 可以在 O(log⁡p)O(\log p) 时间内通过 p-adic 对数 求解。

# Smart's Attack
def smart_attack(P, Q, p):
E = P.curve()
Ep = EllipticCurve(Qp(p, 2), [E.a1(), E.a2(), E.a3(), E.a4(), E.a6()])
P_Qp = Ep.lift_x(ZZ(P.xy()[0]))
Q_Qp = Ep.lift_x(ZZ(Q.xy()[0]))
p_times_P = p * P_Qp
p_times_Q = p * Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P / y_P)
phi_Q = -(x_Q / y_Q)
k = phi_Q / phi_P
return ZZ(k)


# discrete_log内置Pohlig-Hellman,但是要记得指定运算符
discrete_log(Q, G, ord=5, operation='+')

特殊曲线(奇异曲线 / 超奇异曲线)

奇异曲线

三种奇异曲线类型:

类型 条件 归约到
尖点曲线(Cusp) a≡0,b≡0a \equiv 0, b \equiv 0 (Fp,+)(\mathbb{F}_p, +) 加法群
结点曲线(Node,有两个不同切线) 4a3+27b2≡04a^3 + 27b^2 \equiv 0,其他条件 (Fp∗,×)(\mathbb{F}_p^*, \times) 乘法群
结点曲线(Node,重切线) 4a3+27b2≡04a^3 + 27b^2 \equiv 0,其他条件 (Fp2∗,×)(\mathbb{F}_{p^2}^*, \times)

思路:

  1. 找到奇异点 (x0,y0)(x_0, y_0)
  2. 做变量替换 t=y−y0x−x0t = \frac{y - y_0}{x - x_0},将问题归约到 Fp∗\mathbb{F}_p^* 上的 DLP
  3. 用普通 DLP 算法( Pohlig-Hellman + BSGS)求解

例题:

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

p = 9259018534502783714631247560818133078409930397939705162361230465031580254504264713899169170790687716589100652406132800533397486109926387016562663961524649
a = 0
b = 6235467631650349040636525320446729529985562949423449382969614887116983248527693872546808737512375916974084741892428681798937790855872528526403738040908493
c = 4165903654767429195543540819098180314477702137507994424192636596518008877139978822038616746899053449640020812062736993008962585578921635697413459959685760
d = 1889382340373247565387211782596794283852946561870564309251998196824383297786878212641581641540685106266683503654620956037368416192796434147249748216284648
e = 3015564788819504594313842562882781366361783108618226049128986996153057550014499326419988348165744003693083108924831219996703133056523468396967900376388617


def add(P1, P2):
def double(P):
def mul(k, P):



m = bytes_to_long(flag)
G = (1244884551970947614719458919805713649754289814760243366205012699871413235954279930743612403791919112394457579170253990713250052822262255880036254772609156, 4579639528751113977115209571728128585569082149696598770106934145500742785077382446292613925719404433141749168427443122707253164477493499731016883616496009)
P = mul(m, G)
print(P)

# (9039120379228240875764080238389949393433230267005269099421166553853462484353350917730468887801035670710981414900285176863179650428412616144755102163764906, 6266065680737729548475090556806928225106996606788926050268440244885398464756877886842570309216095272026404453765198968208595242208306240371310555394416694)

分析:

对原曲线移项配方整理可以得到
y2=(x−r)3y^2 = (x-r)^3
进一步平移曲线得到:y2=x3y^2 = x^3
群同构关系:
尖点曲线的光滑点群 Ens(Fp)E_{\text{ns}}(\mathbb{F}_p) 同构于有限域的加法群 (Fp,+)(\mathbb{F}_p, +):

$$E_{\text{ns}}(\mathbb{F}_p) \cong (\mathbb{F}_p, +)$$

点(t3,t2)(t^3,t^2)一定在曲线上,所以一个点对应一个有限域里面的数字t=XYt = \frac{X}{Y}
由此得到对应的映射函数 ϕ\phi:
$$\phi(X, Y) = \frac{X}{Y} \pmod p, \quad \phi(\mathcal{O}) = 0$$
求解:将ecdlp同构到有限域上的加法群 DLP:
$$\phi(Q) \equiv k \cdot \phi(P) \pmod p \implies k \equiv \phi(Q) \cdot \phi(P)^{-1} \pmod p$$

一次模逆就拿下了
补充一点相关知识:

群同态(Homomorphism):
一个映射 ϕ:G→H\phi: G \to H 满足保运算性质:$$\phi(a \star b) = \phi(a) \odot \phi(b) \quad (\forall a, b \in G)$$单位元对应:ϕ(eG)=eH\phi(e_G) = e_H逆元对应:ϕ(a−1)=ϕ(a)−1\phi(a^{-1}) = \phi(a)^{-1}同态像与核:$$\ker(\phi) = {a \in G \mid \phi(a) = e_H}$$
群同构(Isomorphism):
若同态 ϕ:G→H\phi: G \to H 是双射(既单又满),则称 GG 与 HH 群同构,记作 G≅HG \cong H。存在可逆同态 ϕ−1:H→G\phi^{-1}: H \to G。两个同构的群在抽象代数结构上完全等价,只是“元素的记号和运算的符号不同”。

Tate-Weil配对

在标准 ECC 中,我们在群 GG 上只有加法(点加 P+QP + Q)和标量乘(k⋅Pk \cdot P),但无法把“两个点相乘得到一个点”。
配对打破了这个限制。它提供了一个映射函数 ee:

e:G1×G2→GTe: G_1 \times G_2 \to G_T

  • 输入:曲线上的两个点 P∈G1,Q∈G2P \in G_1, Q \in G_2(通常是阶为 rr 的挠点群)。
  • 输出:某个有限域扩张 Fqk×\mathbb{F}_{q^k}^\times 中的乘法群元素(即一个普通的域元素/数)。
  • 核心数学性质(双线性 Bilinearity):

e(aP,bQ)=e(P,Q)abe(aP, bQ) = e(P, Q)^{ab}

把点上的标量乘法转换为了有限域乘法群中的指数乘法。

Weil 配对 er(P,Q)e_r(P, Q)

  • 定义域:通常定义在曲线的全部 rr-挠点群上 E[r]×E[r]→μr⊂Fqk×E[r] \times E[r] \to \mu_r \subset \mathbb{F}_{q^k}^\times(μr\mu_r 表示 rr 次单位根)。
  • 交错性(Alternating):er(P,P)=1e_r(P, P) = 1。因此,如果 PP 和 QQ 属于同一个循环子群(例如 Q=kPQ = kP),算出来的结果恒为 11。
  • 计算代价:需要计算两个有理函数的求值比,计算量偏大。

Tate 配对 ⟨P,Q⟩r\langle P, Q \rangle_r 与简化 Tate 配对

  • 定义域:G1×G2→Fqk×/(Fqk×)rG_1 \times G_2 \to \mathbb{F}_{q^k}^\times / (\mathbb{F}_{q^k}^\times)^r。
  • 自配对特性:通常 e(P,P)≠1e(P, P) \neq 1(不再是交错的),适合更广泛的协议设计。
  • 简化处理:原生 Tate 配对输出的是一个商群等价类,工程中需要加上一个最终幂运算(Final Exponentiation):

    e(P,Q)=⟨P,Q⟩r(qk−1)/re(P, Q) = \langle P, Q \rangle_r^{(q^k - 1)/r}

例题:HTB Cyber Apocalypse 2022 / CA CTF 2022 —— MOVs Like Jagger

p  = 434252269029337012720086440207      (99 bit)
a = -35, b = 98
#E = p + 1 (超奇异)
G = (16378704336066569231287640165, 377857010369614774097663166640)
k = 2

exp

from sage.all import *

a = -35
b = 98
p = 434252269029337012720086440207

E = EllipticCurve(GF(p), [a, b])


def movAttack(G, Q):
k = 1
while (p**k - 1) % E.order():
k += 1

Ee = EllipticCurve(GF(p**k, 'y'), [a, b])

R = Ee.random_point()
m = R.order()
d = gcd(m, G.order())
B = (m // d) * R

assert G.order() / B.order() in ZZ
assert G.order() == B.order()

Ge = Ee(G)
Qe = Ee(Q)

n = G.order()
alpha = Ge.weil_pairing(B, n)
beta = Qe.weil_pairing(B, n)

print('Computing log...')
nQ = beta.log(alpha)
return nQ


Gx = 16378704336066569231287640165
Gy = 377857010369614774097663166640

Px = 0x43984282fd683ce8a6ae3b3be
Py = 0x566a38eb7dbd4af0ed45421cb

Qx = 0x3b505638fdfbf59f732e44805
Qy = 0xb8823b17c3f4047dc20a3afa

G = E(Gx, Gy)
P = E(Px, Py)
Q = E(Qx, Qy)

nQ = movAttack(G, Q)
secret_point = nQ * P

print(hex(secret_point[0]))
print(hex(secret_point[1]))