#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))