British Elevator (350 pts)

Question:

 

Write-Up:

In 1997, Nigel P. Smart published an attack on a special type of elliptic curves, which he called "anomalous."

A curve is anomalous if the number of points on it (the order of the curve) is equal to the size of the underlying finite field.

Smart's attack is linear time, meaning it's super fast! It is one of the few successful attacks on discrete logarithms on elliptic curves, so whenever you see a challenge like this, it's best to check whether the curve is anomalous first. A simple Sage code which verifies this follows:

#!/usr/bin/env sage

p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576

E = EllipticCurve(GF(p),[A,B])

assert E.order() == p

Smart's attack uses the so-called Hensel Lift, thus the namesake of this challenge (In British English, an elevator is called a "lift"! Furthermore, smart is a British researcher. Pretty neat, huh?! )

A very good explanation of the attack, along with Sage codes, is provided by Peter Novotney. Novotney's code first implements the Hensel Lift:

#!/usr/bin/env sage

def HenselLift(P, p, prec):
    E = P.curve()
    Eq = E.change_ring(QQ)
    Ep = Eq.change_ring(Qp(p,prec))
    x_P,y_P = P.xy()
    x_lift = ZZ(x_P)
    y_lift = ZZ(y_P)
    x, y, a1, a2, a3, a4, a6 = var('x,y,a1,a2,a3,a4,a6')
    f(a1,a2,a3,a4,a6,x,y) = y^2 + a1*x*y + a3*y - x^3 - a2*x^2 - a4*x - a6
    g(y) = f(ZZ(Eq.a1()),ZZ(Eq.a2()),ZZ(Eq.a3()),ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)
    gDiff = g.diff()
    for i in range(1,prec):
        uInv = ZZ(gDiff(y=y_lift))
        u = uInv.inverse_mod(p^i)
        y_lift = y_lift - u*g(y_lift)
        y_lift = ZZ(Mod(y_lift,p^(i+1)))
    y_lift = y_lift+O(p^prec)
    return Ep([x_lift,y_lift])

and then proceeds to implementing the attack:

#!/usr/bin/env sage

def SmartAttack(P, Q, p, prec):
    E = P.curve()
    Eqq = E.change_ring(QQ)
    Eqp = Eqq.change_ring(Qp(p,prec))
    P_Qp = HenselLift(P,p,prec)
    Q_Qp = HenselLift(Q,p,prec)
    p_times_P = p*P_Qp
    p_times_Q=p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    k = Mod(k,p)
    return k

Using Novotney's excellent procedures, we can simply call the SmartAttack() on our curve as follows:

#!/usr/bin/env sage

p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576

E = EllipticCurve(GF(p),[A,B])

assert E.order() == p

P = (5732560139258194764535999929325388041568732716579308775, 14532336890195013837874850588152996214121327870156054248)
Q = (2609506039090139098835068603396546214836589143940493046, 8637771092812212464887027788957801177574860926032421582)

SmartAttack(E(P),E(Q),p,8)

This outputs 6418297401790414611703852603267852625498215178707956450, which is the flag!

Other Resources

The German team h4x0rpsch0rr, one of Sharif CTF 2016 contestants, also published an excellent write-up for this challenge.

Source Code

British_Elevator_Discret_Log.sage.