I am a layperson interested in how cryptography works. I would like to know why you can use shorter keys with elliptic curve Diffie-Hellman (ECDH) than with the discrete log DH key exchange. Both have to be large enough to withstand brute force attacks. So I assume there must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe. Thank you in advance for your help.
Add a comment |
1 Answer
$\begingroup$
$\endgroup$
1 There must be some attacks that you can use to try and crack the DLP that can't be used on ECDH and that would force you to chose a longer key for it to be safe.
Indeed, there are algorithms applicable to DLP in groups that are a subgroup of $\Bbb Z_p^*$, but not to Elliptic Curve (sub)groups:
- A variant of (G)NFS. See e.g. this article about solving a 768-bit DLP. That used to be the record before this December 2019 announcement about solving a 795-bit DLP.
- Index calculus, which in not quite as efficient, but still much more efficient than generic algorithms like baby-step/giant-step and Pollard's rho, which can attack the DLP in any group.
This website specifically lists recommendations for key size. Depending on crystal ball hypothesis, 250-bit ECC (giving the equivalent of about 125-bit symmetric security against classical computers running distributed Pollard's rho) is conjectured to be about as safe as 2000 to 8800-bit DLP in $\Bbb Z_p^*$ (the discrepancy is mostly due to the lesser confidence about the implausibility of better algorithms in $\Bbb Z_p^*$).
- 1$\begingroup$ Maybe point to keylength.com for up-to-date key size comparisons? $\endgroup$2020-04-06 14:36:44 +00:00Commented Apr 6, 2020 at 14:36