2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ well it works, the only question is, will you still be alive when the answer is found... $\endgroup$ – SEJPM May 14 '15 at 15:51
  • $\begingroup$ Yes this is the problem?? it take tremendous amount of time! $\endgroup$ – Chaker May 14 '15 at 15:53
  • $\begingroup$ How large is the field prime / group order? $\endgroup$ – SEJPM May 14 '15 at 15:53
  • $\begingroup$ 143 bit... even NSA can't brute-force this by trying out all k's, I guess the intended attack route for this one is that this may be a weak curve and you can attack it this way, as even 71 bits for standard DLP algorithms is infeasible for most people $\endgroup$ – SEJPM May 14 '15 at 15:55
  • 1
    $\begingroup$ wikipedia has pseudocode for this for standard groups, replace multiplcations with additions for your purpose. And then you only need a library supporting ECC to implement it yourself, like Crypto++ or OpenSSL $\endgroup$ – SEJPM May 14 '15 at 16:16
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice, reads well, but I'm unsure about "if not goto step 2". $\endgroup$ – Maarten Bodewes May 18 '15 at 17:16
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.