4
$\begingroup$

I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits).

I managed to factor the order of the curve, and most of the prime factors were smooth, but two of the factors weren't, they were about 80 bits each. I'm given two points $P$ and $Q$, and $Q = nP$, so the goal is to find $n$.

So the order has some smooth factors and some not so smooth factors, so I tried to apply pollard rho to the semi-large primes but that's still a $O(\sqrt{2^{80}})$ complexity, which I think will take too long.

I started looking at Pollard's lambda algorithm. I'm not given a bound on $n$, but I was given an upper bound on $n$, so I know that $n < U$, $U$ was about $b$ bits, could I use with pollard's lambda algorithm (or pollard's rho algorithm) so it's more efficient than $O(\sqrt{2^{80}})$

So is it possible pollard's lambda with the pohlig-hellman algorithm, or is the a better attack to use if I know a number $U$ so that $n < U$ and $Q = nP$.

Improve this question
$\endgroup$
5
  • $\begingroup$ How large is $U$? $\endgroup$
    – yyyyyyy
    Commented Apr 5, 2017 at 13:52
  • $\begingroup$ The $U$ was just a hypothetical situation because I was trying to see how I could implement pollard lambda with this question. Cause it's optimized when $a \le n \le b$ and if $b-a$ is somewhat small. For example if $U$ was about 100 bits so we know that $0 \le n \le U$, would the ECDLP be easier to solve with a smaller complexity? @yyyyyyy $\endgroup$
    – user45697
    Commented Apr 5, 2017 at 13:57
  • $\begingroup$ Pollard's lambda algorithm would have roughly complexity $\mathcal{O}(\sqrt{2^b})$ so if $b < 80$ it's worth considering. $\endgroup$
    – puzzlepalace
    Commented Apr 5, 2017 at 14:41
  • $\begingroup$ @puzzlepalace how would I do that is my question cause what if the bound given is larger than the prime (or order) I'm using. $\endgroup$
    – user45697
    Commented Apr 5, 2017 at 14:47
  • $\begingroup$ $\sqrt{2^{80}} = 2^{40}$, and $2^{40}$ is definitely feasible. $\endgroup$
    – Myria
    Commented Apr 6, 2017 at 19:04

1 Answer 1

Reset to default
1
$\begingroup$

If the question is "can I solve the ECDLP by combining Pohlig-Hellman and Pollard's lambda", then the answer is yes, provided your $p-1$ is smooth enough.

First off, as mentioned in the comments, a search interval of $[0, 2^{40}]$ is quite doable with Pollard's lambda.

Factorize $p-1$ to get all the $B$-smooth prime factors; let's say there are $k$ of them, the ${r_k}$. Then run Pohlig-Hellman on each of them and obtain the secret key mod $r = \prod_i^kr_i$. If the order of your base point on your curve is $Q$, then your search interval looks like $[0, Q/r]$. So $Q/r$ puts the bounds on how long you would expect the lambda algorithm to find a collision.

What's a good $B$ for smoothness? Now this is implementation-dependent, so that depends on what you're working with and how long you have to wait. In practice, I found that if you factorize $p-1$ up to about $2^{20}$, and you have a few primes of that size, and the order of your base point is much smaller than $p-1$, that cuts $Q/r$ down to a reasonable size, but of course your experience may differ.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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