*CTF 2021 | MyCurve

#*CTF_2021

from Crypto.Util.number import bytes_to_long
from flag import flag
assert flag[:5]=='*CTF{' and flag[-1]=='}'
flag=flag[5:-1]
def add(P,Q):
    if Q==0:
        return P
    x1,y1=P
    x2,y2=Q
    return (d1*(x1+x2)+d2*(x1+y1)*(x2+y2)+(x1+x1^2)*(x2*(y1+y2+1)+y1*y2))/(d1+(x1+x1^2)*(x2+y2)),(d1*(y1+y2)+d2*(x1+y1)*(x2+y2)+(y1+y1^2)*(y2*(x1+x2+1)+x1*x2))/(d1+(y1+y1^2)*(x2+y2))

def mul(k,P):
    Q=(0,0)
    while k>0:
        if is_even(k):
            k/=2
            P=add(P,P)
        else:
            k-=1
            Q=add(P,Q)
    return Q

F=GF(2**100)
R.<x,y>=F[]
d1=F.fetch_int(1)
d2=F.fetch_int(1)
x,y=(698546134536218110797266045394L, 1234575357354908313123830206394L)
G=(F.fetch_int(x),F.fetch_int(y))
P=mul(bytes_to_long(flag),G)
print (G[0].integer_representation(),G[1].integer_representation())
print (P[0].integer_representation(),P[1].integer_representation())
#(698546134536218110797266045394L, 1234575357354908313123830206394L)
#(403494114976379491717836688842L, 915160228101530700618267188624L)

上の何かしらの曲線の上のECDLP。 今回はBinary Edwards Curve という曲線だった。このPDFによるとBinary Edwards Curveは Weierstrass Form で表した楕円曲線へのisomorphismが存在するのでこちらに移してorderをみると、小さい素数の積になっているから、 Pohlig-Hellman Attackで解けるし、Sageが実装してくれているのでそれを使うのも良い

F=GF(2**100)
d1=F.fetch_int(1)
d2=F.fetch_int(1)
x,y=(698546134536218110797266045394L, 1234575357354908313123830206394L)
G=(F.fetch_int(x),F.fetch_int(y))

#(698546134536218110797266045394L, 1234575357354908313123830206394L)
x,y = (403494114976379491717836688842L, 915160228101530700618267188624L)
P=(F.fetch_int(x),F.fetch_int(y))


a1 = F.fetch_int(1)
a3 = a4 = F.fetch_int(0)
a2 = d1**2 + d2
a6 = (d1**4)*(d1**4 + d1**2 + d2**2)

EC = EllipticCurve(F, [a1,a2,a3,a4,a6])
def f(P):
    x,y = P
    u = d1*(d1*d1 + d1 + d2)*(x + y) / (x*y + d1*(x+y))
    v = d1*(d1*d1 + d1 + d2)*(x / (x*y + d1*(x+y)) + d1 + 1)
    return EC(u, v)

order = EC.order()

P_ = f(P)
G_ = f(G)

x = discrete_log(P_, G_, operation="+")
print(bytes.fromhex(hex(x)[2:]))