Writeup for Intmax's CTF Problem 5

intmax-ctf-problem5.md

Problem

The following code is given (source).

from fielddef import FQFac

q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
GF = FQFac(q)

G = (GF(68001253697693959505385166418825921216879992913338607518506263877231417389309), GF(32956869957026046537418079256725634934468928549809562050419661008417397548252))
P = (GF(78682525735928631168497251673563130650852315793053792730195256219768651938341), GF(84795375029059674300362179151585264542663827440804066060768991521034056440120))

d = 1 #??? This is TARGET. P = dG
SuperP = (GF(78682525735928631168497251673563130650852315793053792730195256219768651938341), GF(40426504872605514126813907278243558543227238540609187742567326172940715852589))
# Super Elliptic Curve 1 + 3 x + 4 x^2 + 4 x^3 + 3 x^4 + x^5

The goal of this problem is to find $d$ satisfying $P=dG$ in the given elliptic curve over the finite field $\mathbb{F}_q$. As additional info, the superelliptic curve point corresponding to the $x$-coordinate of $P$ is given.

Solution

First, we see that it seems that nothing can proceed without knowing the parameters of the elliptic curve. From the parameters of the superelliptic curve, it can be guessed that the parameters of the elliptic curve might be small. Brute-forcing gives

$$y^2 = x^3+3x^2+3x+1.$$

This curve can be transformed into

$$y^2 = (x+1)^3$$

and is singular with the cusp $(-1,0)$.

It is well known that a discrete logarithm problem of a singular elliptic curve with a cusp can be reduced to a discrete logarithm problem on the additive group $(\mathbb{F}_q,+)$ (i.e., just division). Note that the given superelliptic curve is $y^m = (x+1)^3(x^2+1)$, and this parameter seems to be a hint.

The following is a brief description of why it is reducible. Let $x' = x+1$, and then the elliptic curve can be transformed into

$$ y^2 = x'^3. $$

Theorem: Let $E$ be an elliptic curve $y^2=x^3$ over $\mathbb{F}_q$. Let $E_{\mathrm{ns}}$ be a set of nonsingular points over $E$ (i.e., not including the singular point $(0,0)$ ) containing the point $∞ = (0:1:0)$. The map

$$E_{\mathrm{ns}}\to \mathbb{F}_q,\quad (x,y)\mapsto \frac{x}{y},\quad ∞\mapsto 0$$

is a group isomorphism between $E_{\mathrm{ns}}$ and $\mathbb{F}_q$.

■

For this problem, it is sufficient to show that it is isomorphic in the case $(x_1,y_1)\neq(x_2,y_2)$.

Proof: Let $t=x/y$. $x,y$ can be parameterized in $t$ as

$$ x = (y/x)^2 = 1/t^2,\quad y=x/t=1/t^3. $$

This means that every point over $E_{\mathrm{ns}}$ can be represented by the parameter $t$. By corresponding $t=0$ to $∞$, the map becomes a bijection.

We first prove

$$(x_1,y_1)+(x_2,y_2)=(x_3,y_3)\Longrightarrow t_1+t_2=t_3.$$

The formula for the addition of elliptic curves yields

$$ \begin{align} x_3 &= \left(\frac{y_2-y_1}{x_2-x_1}\right)^2 - x_1-x_2 \quad\text{and} \\ -y_3&=\left(\frac{y_2-y_1}{x_2-x_1}\right)\left(x_3-x_1\right)+y_1. \end{align}$$

In these two equations, replacing $x_i$ with $1/t_i^2$ and $y_i$ with $1/t_i^3$ yields

$$\begin{align}t_3^{-2}&=(t_1+t_2)^{-2} \quad \text{and} \\ t_3^{-3}&=\left(t_1+t_2\right)^{-3}. \end{align}$$

(This transformation is straightforward but a bit annoying.)

These two equations yield

$$t_3 = t_1+t_2.$$

We can also prove

$$(x_1,y_1)+(x_2,y_2)=(x_3,y_3)\Longleftarrow t_1+t_2=t_3$$

by the same simple transformation as above. It is omitted here.

Therefore, the map of the theorem is isomorphic for $(x_1,y_1)\neq(x_2,y_2)$. ■

By using the map, we can move the points $G, P$ of the elliptic curve to $\mathbb{F}_q$ and then divide to obtain $n$. The following SageMath script will output the secret key.

q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
F = GF(q)

G = (F(68001253697693959505385166418825921216879992913338607518506263877231417389309), F(32956869957026046537418079256725634934468928549809562050419661008417397548252))
P = (F(78682525735928631168497251673563130650852315793053792730195256219768651938341), F(84795375029059674300362179151585264542663827440804066060768991521034056440120))

G_prime = (G[0] + 1, G[1])
P_prime = (P[0] + 1, P[1])

g = G_prime[0] / G_prime[1]
h = P_prime[0] / P_prime[1]

n = h * g**-1

print(hex(n)[2:].zfill(64))

Private Key: 0000000000000057c469555f618b593aa933215974569cf5189d643c0e9b834f