SSSAAttack

ecpyは遅い

# http://mslc.ctf.su/wp/polictf-2012-crypto-500/
def hensel_lift(curve, p, point):
    A, B = map(int, (E.a4(), E.a6()))
    x, y = map(int, point.xy())

    fr = y**2 - (x**3 + A*x + B)
    t = (- fr / p) % p
    t *= inverse_mod(2 * y, p)  # (y**2)' = 2 * y
    t %= p
    new_y = y + p * t
    return x, new_y

def sssa_attack(E, g, v, p):
    x1, y1 = g.xy()
    x2, y2 = v.xy()
    if 0:
        # Hensel lift can preserve the curve
        x1, y1 = hensel_lift(E, p, g)
        x2, y2 = hensel_lift(E, p, v)
    else:
        # we can calso lift by adding random multiple of p
        # just need to compute new curve
        x1 = int(x1)
        x2 = int(x2)
        y1 = int(y1)+p
        y2 = int(y2)+p

    # calculate new A, B (actually, they will be the same here)
    mod = p ** 2

    A2 = y2**2 - y1**2 - (x2**3 - x1**3)
    A2 = A2 * inverse_mod(x2 - x1, mod)
    A2 %= mod

    B2 = y1**2 - x1**3 - A2 * x1
    B2 %= mod

    # new curve
    E2 = EllipticCurve(IntegerModRing(p**2), [A2, B2])

    # calculate dlog
    g2s = (p - 1) * E2(x1, y1)
    v2s = (p - 1) * E2(x2, y2)

    x1s, y1s = map(int, g2s.xy())
    x2s, y2s = map(int, v2s.xy())

    dx1 = (x1s - x1) // p
    dx2 = (x2s - x2) // p
    dy1 = (y1s - y1)
    dy2 = (y2s - y2)

    m = (dy1 * inverse_mod(dx1, p) % p) * (dx2 * inverse_mod(dy2, p) % p) % p
    return m
p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
A = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
B = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
EC = EllipticCurve(GF(p), [A, B])
P = EC.random_point()
Q = EC.random_point()
x = sssa_attack(EC, P, Q, p)
assert Q == x * P