Description

Alice wants to use the ECDSA signature algorithm.
For this, she chooses to use the elliptic curve equation E where y² = x³ – x, defined on the finite field with q elements, F_q, with q = 134747661567386867366256408824228742802669457 .

She chose P as a base point of order N = 2902021510595963727029 with:
P = (18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154)

Then, she chooses as secret signature key a random integer d with 1<d<N.
The public key is the point Q=d⊗P where ⊗ is the scalar multiplication on the elliptic curve E.

The value of Q is:
Q=(76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090)

The validation key is given by the value of d.

Resolution

This challenge is about solving the Elliptic Curve Discrete Logarithm Problem (ECDLP).

We used the excellent PARI/GP tool for calculus.

We first checked wether the given elliptic curve was a candidate for Smart’s attack, which leads to a linear algorithm for solving the ECDLP.

For this we need to have #E(F_q) = q.

? q = 134747661567386867366256408824228742802669457
%1 = 134747661567386867366256408824228742802669457
? E = ellinit([0,0,0,-1,0],134747661567386867366256408824228742802669457)
%2 = [Mod(0, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(134747661567386867366256408824228742802669456, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(134747661567386867366256408824228742802669455, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(134747661567386867366256408824228742802669456, 134747661567386867366256408824228742802669457), Mod(48, 134747661567386867366256408824228742802669457), Mod(0, 134747661567386867366256408824228742802669457), Mod(64, 134747661567386867366256408824228742802669457), Mod(1728, 134747661567386867366256408824228742802669457), Vecsmall([3]), [134747661567386867366256408824228742802669457, [134747661567386867366256408824228742802668161, 0, [6, 0, 0, 0]]], [0, 0, 0, 0]]
? ellcard(E)
%3 =134747661567386867366256408824228742802669456

We have #E(F_q) = q – 1, so we can’t use this attack.

So we decided to rely on PARI/GP’s algorithm to calculate the discrete logarithm :

? P = [18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154]
%4 = [18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154]
? G = [76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090]
%5 = [76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090]
? N = 2902021510595963727029
%6 = 2902021510595963727029
? ord = [N, factor(N)]
%7 = [2902021510595963727029, Mat([2902021510595963727029, 1])]
? d = elllog(E, G, P, ord)
%8 = 1598838546070749569403

Bingo ! The flag is 1598838546070749569403.