# 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.