PicoCTF 2018 | ECC2

#ECDH #ECDLP #Pohlig-Hellman_Attack

Elliptic Curve: y^2 = x^3 + A*x + B mod M
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
B = *You can figure this out with the point below :)*

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)
n = *SECRET*
n*P = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440)

n < 400000000000000000000000000000

Find n.

剰余方程式を解くテクを使って、楕円曲線のbを手に入れる

_, b = PolynomialRing(GF(M), name="b").objgen()
f = Px**3 + Px*A + b - Py**2
B = Integer(f.roots()[0][0])

あとは 楕円曲線の位数が比較的小さい素因数に分解できるので、 Pohlig-Hellman Attackをやれば良い

from sage.all import *

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785
Px, Py = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

_, b = PolynomialRing(GF(M), name="b").objgen()
f = Px**3 + Px*A + b - Py**2
B = Integer(f.roots()[0][0])

EC = EllipticCurve(GF(M), [A, B])
P = EC((Px, Py))
Q = EC((61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440))

order = EC.order()
factors = list(factor(order))
mods = []
zs = []
cur = 1

bound = 400000000000000000000000000000

for factor in factors:
    p, e = factor
    pe = p**e
    Pi = (order // pe) * P
    Qi = (order // pe) * Q
    zi = Pi.discrete_log(Qi)

    zs.append(zi)
    mods.append(pe)

    cur *= pe
    if cur > bound:
        break

print(CRT(zs, mods))