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.
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^*$).