TJCTF 2016 | Curvature2

#ECDH

from flag import FLAG
FLAG = int(FLAG.encode('hex'),16)

P = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
Gx = 0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da
Gy = 0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90

assert FLAG < P

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

def inv(a):
    gcd, x, y = egcd(a % P, P)
    if gcd != 1:
        return -1
    else:
        return x % P

def add(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    i = inv(b[0] - a[0])
    if i == -1:
        return 0
    l = ((b[1] - a[1]) * i) % P
    x = (l*l - a[0] - b[0]) % P
    y = (l*(a[0] - x) - a[1]) % P
    return (x,y)

def double(a):
    if a == 0:
        return a
    i = inv(2*a[1])
    if i == -1:
        return 0
    l = ((3*a[0]*a[0] + A) * i) % P
    x = (l*l - 2*a[0]) % P
    y = (l*(a[0] - x) - a[1]) % P
    return (x,y)

def multiply(point, exponent):
    r0 = 0
    r1 = point
    for i in bin(exponent)[2:]:
        if i == '0':
            r1 = add(r0, r1)
            r0 = double(r0)
        else:
            r0 = add(r0, r1)
            r1 = double(r1)
    return r0

print(multiply((Gx,Gy),FLAG))

# Output:
# (10150325274093651859575658519947563789222194633356867789068177057343771571940302488270622886585658965620106459791565259790154958179860547267338437952379763L, 6795014289013853849339410895464797184780777251924203530417684718894057583288011725702609805686960505075072642102076744937056900144377846048950215257629102L)

楕円曲線の位数 = 体の位数になっていて、 SSSAAttack ができるらしいのでやる。ecpy ありがとう

from sage.all import PolynomialRing, GF
from ecpy import *


P = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
Gx = 0xcf634030986cf41c1add87e71d638b9cc723c764059cf4c9b8ed2a0aaf5d51dc770372503ebfaad746ab9220e992c09822916978226465ad31d354a3efee51da
Gy = 0x65eaad8848b2787103fce02358b45d8a61420031989eb6b4b70d82fe20d85583ae542eb8f76749dc640b0f13f682228819b8b2f04bd7a5a17a4c675540fe1c90

_, b = PolynomialRing(GF(P), name="b").objgen()
f = Gx**3 + A*Gx + b - Gy**2
B = int(f.roots()[0][0])

F = FiniteField(P)
EC = EllipticCurve(F, int(A), B)

G = EC(Gx, Gy)

Q = EC(10150325274093651859575658519947563789222194633356867789068177057343771571940302488270622886585658965620106459791565259790154958179860547267338437952379763, 6795014289013853849339410895464797184780777251924203530417684718894057583288011725702609805686960505075072642102076744937056900144377846048950215257629102)
s = SSSA_Attack(F, EC, G, Q)
print(bytes.fromhex(hex(s)[2:]))