Elliptic curve brute forcing

Question

I have elliptic curve of equation $y^2 \equiv x^3 -x $. And the coordinate of points $Q$ and $P$. I want to solve $Q=[k]P$ (where $k$ is the unknown) by testing all possible $k$.

Is this the right approach to solve this problem?

Edit

I understand from comments that this is known as Elliptic curve discrete logarithm problem, So what is the best approach to attack this problem.

• Pollard lambda
• Pollard rho
• Baby-Step, Giant-Step
• The Pohlig-Hellman Method
• ...

PS :

I tried to factor $p-1$ and the result is $p-1=(2^2.N)^2$ where N is the order of point $P$

I also noticed from my googling that this curve isn't secure. Can any one explain why, and what that means?

Answer 1

In your particular case the order of the point divides $p-1$, this means that the embedding degree of your curve is 1.

You should be able to apply the MOV attack to transfer your instance of ECDLP into an instance of DLP over $\mathbb{F}_{p}^*$. This would allow you to use the Index Calculus to solve your problem.

As the Index Calculus is subexponential, it would improve the required time for your attack compared to a generic discrete logarithm attack on the elliptic curve (as the Rho or the BSGS).

To perform the MOV attack you should first find a point $R$ of order $n$ which is not a multiple of $P$. This should be easy given your curve. Proceed in the following way:

1. Randomly generate a point $R$ on the curve
2. Find its order
3. Most likely it will be of the form $a*n$, if not goto step 1
4. $R = [a]R$ will have order $n$

Then perform the Weil pairing of $P$ and $Q$ as: $$ \begin{eqnarray} w_1 &=& e(P, R) \\ w_2 &=& e(Q, R) = e(kP, R) = e(P, R)^k \end{eqnarray} $$

If $w_1 = 1$ then goto step 1. Otherwise solve the DLP by finding the $k$ of $w_2 = w_1{^k}$ in $\mathbb{F}_{p}^*$ using Index Calculus.

The returned $k$ will be the $k$ you are looking for (the one of $Q=[k]P$)

This answer by Samuel Neves, which I've used to write this answer, links to Sage code to compute the pairing and has more details.

Edit: Thanks Maarten for finding the goto issue.

Answer 2

From what you say, I assume that you are talking about the Crypto 3 challenge from HackingWeek.

As Ruggero explained, the curve is vulnerable to both the MOV attack and the older FR attack that works similarily, using Weil or Tate pairings (respectivly).

A simple sage code for the FR-attack would be:

q = 134747661567386867366256408824228742802669457
Zq = Zmod(q)
E = EllipticCurve(Zq, [0,0,0,-1,0])
P = E(18185174461194872234733581786593019886770620, 74952280828346465277451545812645059041440154)
Q = E(76468233972358960368422190121977870066985660, 33884872380845276447083435959215308764231090)
n = P.order()
k = GF(n)(q).multiplicative_order()
R = E.random_element()
w1 = P.tate_pairing(R, n, k)
w2 = Q.tate_pairing(R, n, k)
print w1, w2

From then you get $w_1$ and $w_2$, with $w_2=w_1^d$ and you need to solve a discrete logarithm problem in a ring of integer mod p. It can take quite a while (something like 4 hours on my computer) but is still feasible given the small modulus.