The Problem

We’re given a curve of the form

\[E: Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6\]

Parametrized by

\[\begin{equation} \begin{cases} a_1 &= 0\\ a_2 &= \text{0x9d2b4588d4bf67a70c4a7a981bf11faf}\\ a_3 &= \text{0xb58af8ef}\\ a_4 &= \text{0x85be993fc04714e65d2cf3b7f8771893}\\ a_6 &= \text{0xe7c66c794a5fa366f08a1414db10f141}\\ \end{cases} \end{equation}\]

Over the ring $\mathbb{Z}_{\text{0xdfb07f75bf0f3a110a940f1912cb1f533418ce2d8f4eef2edd531fe28050a1d3}}$

And a generator G where

\[G_x = \text{0x1fc7a798adb77fce98cabecd76270518d648324a325a98611c5c19fb3c88c67d}\\ G_y = \text{0xd72e468e3b2b8949942bc66cbecd69c7f0d864bd54f4516cebac8492fd1c56da}\\\]

Along with Alice’s public key $P = nG$ where

\[P_x = \text{0x4765a39ca3edaf0838a99619ca4e509f791cc2b1eb7f42951950c69c4bfa5812}\]

Is it possible for Eve to retrieve Alice’s secret key $n$?

Hardness Assumptions

To retrieve the secret key, Eve needs to solve an instance of the elliptic curve discrete log problem. The ECDLP asks us

Given two points on an elliptic curve $Q, P \in E(\mathbb{F}_p)$ such that $Q = kP$, find $k$.

This problem is well studied and assumed to be difficult under the right circumstances. It’s difficulty however relies completely on the structure of the underlying group. For instance, DLP in $(\mathbb{Z}_{n}, +)$ is trivial as $g + g + \cdots + g = g \cdot z = y \mod n$ can be inverted in polynomial time (how?). In general, the best known algorithms for the DLP in a generic group take $\mathcal{O}(\sqrt n)$ group operations (exponential in the bit length of the modulus).

The Vulnerability

Therefore, to find Alice’s secret key, Eve would either have to devise a subexponential algorithm for discrete log over a generic group (and win a Turing award in the process) or discover some weakness in the group structure defined above.

It turns out that the given curve is unsafe because its order has nontrivial factors:

\[\# E(\mathbb{Z}_p) = 3^2 \times 59 \times 14771 \times 27733 \times 620059697 \times 2915987653003935133321\\ \times 257255080924232005234239344602998871\]

Why does this matter? We know that the order of an elliptic curve group is bound by the size of the underlying field (Hasse). We also know that the order of a subgroup divides the order of the group (Lagrange).

If Eve can compute the discrete log modulo each of these factors, she can compute the discrete log modulo their product and obtain the secret key. In this way Eve decomposes the original problem (intractable over $\mathbb{Z}_p$) into a collection of manageable sub problems whose result can then be combined using the Chinese Remainder Theorem.

What makes the sub problems manageable? The size of the subgroup must be small enough for the runtime of a generic algorithm (baby step giant step, Pohlig-Hellman, etc) to become feasible.

The Attack

Let \(q = \#E(\mathbb{Z}_p)\). We start by factoring \(q = \prod_{i=1}^{k} p_{i}^{e_i}\) for prime $p_i$.

We then map the base point and Alice’s public key into each of these subgroups by calculating

\[G_i = (q*p_{i}^{-e_i})G \\ P_i = (q*p_{i}^{-e_i})P\]

Apply your favorite discrete log algorithm (Pohlig-Hellman) to obtain $n_i$ such that.

\[P_i = n_iG_i\]

Recall that the runtime here is exponential in the bit length of the modulus. Using the first five factors in our list we obtain the system

\[\begin{equation} \begin{cases} n_1 &= 4 \mod 9\\ n_2 &= 27 \mod 59\\ n_3 &= 12977 \mod 14771\\ n_4 &= 2568 \mod 27733\\ n_5 &= 261975359 \mod 620059697\\ \end{cases} \end{equation}\]

Of course these moduli are all relatively prime, so we can apply the CRT to obtain the solution

\[n = 82438979720724695506 \mod 134876030111980880301\]

\(\implies n = 82438979720724695506 k + 134876030111980880301\) for some \(k \in \mathbb{Z}_{p}\)

If we exhaustively search for such a $k$ (testing for equality against Alice’s public key) we quickly find her private key:

\[n = 847508536173296595626689 \mod p\]

Indeed we can check that \(847508536173296595626689 G = P\). Here’s what this looks like in sage:

#!/usr/bin/env sage
a1 = 0
a2 = 0x9d2b4588d4bf67a70c4a7a981bf11faf
a3 = 0xb58af8ef
a4 = 0x85be993fc04714e65d2cf3b7f8771893
a6 = 0xe7c66c794a5fa366f08a1414db10f141
p = 0xdfb07f75bf0f3a110a940f1912cb1f533418ce2d8f4eef2edd531fe28050a1d3

E = EllipticCurve(Zmod(p), [0, a2, a3, a4, a6])

G = E.point((0x1fc7a798adb77fce98cabecd76270518d648324a325a98611c5c19fb3c88c67d, 0xd72e468e3b2b8949942bc66cbecd69c7f0d864bd54f4516cebac8492fd1c56da))
P = E.lift_x(0x4765a39ca3edaf0838a99619ca4e509f791cc2b1eb7f42951950c69c4bfa5812)

order = E.order()
factors = [x^y for (x,y) in factor(order)][:5]

residues = []
for factor in factors:
    a =  G * (order // factor)
    b =  P * (order // factor)
    i = discrete_log(b, a, a.order(), operation='+')
    residues.append(i)
    
n = crt(residues, factors)
modulus = prod(factors)

while True:
    if G * n == P:
        print(n)
        break
    n += modulus

TL;DR

Use a safe prime \(p = 2q+1\) for some large prime \(q\) so that that the order \(p-1 = 2q\) leads to no nontrivial subgroups.