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