10
$\begingroup$

I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted to solve the other - for example, one reference claims:

The asymptotic running time of the best discrete logarithm algorithm is approximately the same as that of the best general-purpose factoring algorithm. Therefore, it requires about as much effort to solve the discrete logarithm problem modulo a 512-bit prime as it does to factor a 512-bit RSA modulus.

Now, I suspect that this isn't true, but I'd like to get a feel for why it isn't true.

For instance, as I understand it, the generalized number field sieve can be applied both to solve integer factorization and to solve discrete log. Why is it that it gives such an extreme speed up in integer factorization compared to brute-force, and less so in improving discrete log?

If the asymptotic running times for both applications are approximately the same, then I'm completely confused. I suspect that I'm comparing the wrong parameters, but how is it that ECC key-sizes can be so much smaller that in RSA?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\begingroup$

Actually, the problem is that the above quote uses the term "discrete log" in a way that's different from what you're thinking of.

When someone uses the term "discrete log", they can mean two things:

  • A discrete log in the group $Z^*_p$; that is, given $p$, $g$ and $g^x \bmod p$, recover $x$

  • A discrete log in some other group; that is, given a group $G$, a generator $g$ and the value $g^x$, recover $x$.

Of course, the precise meaning is given by context.

In this specific case, the quote refers to the first meaning of discrete log; a log over a multiplicative group modulo a prime (and for such a group, there exist subexponential ways of solving it).

However, when we're dealing with the security of an EC group, we don't care about discrete logs modulo $Z^*_p$; instead, we care about the discrete log within the EC group (that is, the second meaning). These EC groups (or, at least, the ones based on curves that we actually use) do not have these fast methods of solving it; in particular, the number field sieve algorithm does not appear to apply.

And, because the DLOG problem in an EC group is much harder, we can use a smaller EC curve safely.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "And, because the DLOG problem in an EC group is much harder, we can use a smaller EC curve safely." or this is what we currently think. Some experts (conspiracy theorists) have been recommending against Elliptic Curves, because the small groups used in them may be due to our current lack of understanding faster solution methods rather than a fundamental feature of EC groups. Keylength.com: NIST report on crypto key strength is good resource for checking current matching key and group size for various algorithms (DL, IFC, EC) at equivalent security level. $\endgroup$
    – user4982
    Commented Jan 31, 2014 at 17:57
  • $\begingroup$ @user4982 Also, the NSA has been very observant and influential in EC development. While the inherent EC technology might be secure, current implementations might not be. I would be hesitant on adopting the technology until is more mature. $\endgroup$
    – recursion.ninja
    Commented Jan 31, 2014 at 21:08
  • $\begingroup$ There don't appear to be curves for 1000+ bit keys. How does one design them? $\endgroup$
    – user10653
    Commented Apr 13, 2017 at 23:28
  • $\begingroup$ @user10653 Why would you want a 1000-bit ECC key? $\endgroup$
    – forest
    Commented Dec 8, 2018 at 5:26

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.