hxp


SharifCTF 2016: crypto350 "British Elevator" writeup

After noticing this challenge was about elliptic curves, I could not resist having a try at it. The “description” consisted of the following data:

p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576
E: y^2 = x^3 + Ax + B over GF(p)
P = (5732560139258194764535999929325388041568732716579308775, 14532336890195013837874850588152996214121327870156054248)
Q = (2609506039090139098835068603396546214836589143940493046, 8637771092812212464887027788957801177574860926032421582)
Q = secret * P
flag = secret

Hence the task is simply to compute the (discrete) logarithm of Q with base P on an elliptic curve E given by a Weierstraß equation \[ E\colon\quad y^2=x^3+Ax+B \text. \]

This problem is generally infeasible in reasonable time for curves over prime fields as large as $p$, hence we suspect the curve is particularly badly chosen. sage confirms this assumption:

sage: p = 16857450949524777441941817393974784044780411511252189319
sage: A = 16857450949524777441941817393974784044780411507861094535
sage: B = 77986137112576
sage: E = EllipticCurve(GF(p), [0, 0, 0, A, B])
sage: E
Elliptic Curve defined by y^2 = x^3 + 16857450949524777441941817393974784044780411507861094535*x + 77986137112576 over Finite Field of size 16857450949524777441941817393974784044780411511252189319
sage: E.order()
16857450949524777441941817393974784044780411511252189319
sage: E.order() == p
True

The order of $E$ is exactly the order of the base field $p$, hence the additive transfer attack, also known as “Smart-ASS attack” or “anomalous curve attack”, applies. We follow the paper The discrete logarithm problem on elliptic curves of trace one by Nigel Smart.

In short, it says that $\log_PQ$ is the $p^0$-coefficient of the quotient $\psi_p([p]Q_p)/\psi_p([p]P_p)$ of the $p$-adic elliptic logarithms of the $p$-multiples of $p$-adic lifts $Q_p,P_p$ of the points $Q$ and $P$. Phew, that’s quite a mouthful. Let’s have a look at the individual steps:

  1. We can easily interpret $E$ as an elliptic curve $E_p$ over the $p$-adic numbers $\mathbb Q_p$ since this is a complete discrete valuation ring with residue field $\mathbb F_p$. To lift a point on $E$ to $E_p$, we need to lift one coordinate and compute the other. Fortunately sage has an implementation of square roots for $p$-adics, hence we may simply lift $x$ to an element of $\mathbb Q_p$ (by taking any representant of $x$ in $\mathbb Z$ and interpreting that as an element of $\mathbb Q_p$) and compute $y := \sqrt{x^3+Ax+B}$. Of course there are, in general, two square roots, only one of which has $p^0$-coefficient equal to the $y$-coordinate of $P$: We need to pick that one in order to get the sign of the logarithm we eventually want to compute correct.
  2. Once we have points $P_p$ and $Q_p$ on $E_p$ which reduce to $P$ and $Q$ on $E$, that is, modulo $p$, we can just compute $[p]P_p$ and $[p]Q_p$ on $E_p$ using the usual point addition formulas.
  3. The rest is unexpectedly easy (in practice): sage has an implementation of the formal group including its formal logarithm. That logarithm is a power series with coefficients in $\mathbb Q_p$ with the very nice property that it yields a group homomorphism from a subgroup $E_1(\mathbb Q_p)$ of $E_p$ (in which $[p]P_p$ and $[p]Q_p$ are included by construction) to the additive group $(\mathbb Q_p,+)$: Letting $f$ denote said power series, this homomorphism is given by \[ \psi_p\colon\; E_1(\mathbb Q_p) \to \mathbb Q_p,\;(x,y)\mapsto f(-x/y) \text. \]
    (Strictly speaking, we should now be checking if $\psi_p$ is injective as this would guarantee that our final logarithm is correct, but in practice it works just fine.)
    Therefore we may transfer the problem of computing $\log_{P_p}Q_p$ to $(\mathbb Q_p,+)$, in which “logarithms” are just division. Of course, there may be many different lifts of $P$ and $Q$ to $E_p$ which yield different logarithms, but all of these logarithms have the same $p^0$-coefficient since the lifts come from the same points on $E$.

Finally, here’s an implementation producing the solution:

#!/usr/bin/env sage

p = 16857450949524777441941817393974784044780411511252189319
A = 16857450949524777441941817393974784044780411507861094535
B = 77986137112576
xP = 5732560139258194764535999929325388041568732716579308775
yP = 14532336890195013837874850588152996214121327870156054248
xQ = 2609506039090139098835068603396546214836589143940493046
yQ = 8637771092812212464887027788957801177574860926032421582

E = EllipticCurve(GF(p), [0, 0, 0, A, B])
assert E.order() == p

Qp = Qp(p, 2)
Ep = EllipticCurve(Qp, [0, 0, 0, A, B])

yPp = sqrt(Qp(xP) ** 3 + Qp(A) * Qp(xP) + Qp(B))
Pp = Ep(Qp(xP), (-yPp, yPp)[yPp[0] == yP])

yQp = sqrt(Qp(xQ) ** 3 + Qp(A) * Qp(xQ) + Qp(B))
Qp = Ep(Qp(xQ), (-yQp, yQp)[yQp[0] == yQ])

print('Pp = {}'.format(Pp))
print('Qp = {}'.format(Qp))
print('-' * 40)

lQ = Ep.formal_group().log()(- (p * Qp)[0] // (p * Qp)[1]) / p
print('log(Q) = {}'.format(lQ))
lP = Ep.formal_group().log()(- (p * Pp)[0] // (p * Pp)[1]) / p
print('log(P) = {}'.format(lP))
print('-' * 40)

e = lQ / lP
print('e = {}'.format(e))

assert e[0] * E(xP, yP) == E(xQ, yQ)

print('\n--> FLAG: {:d}\n'.format(e[0]))