British Elevator (350 pts)¶
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!