I concluded the previous post by saying elliptic curve Diffie-Hellman key exchange (ECDHE) requires smaller keys than finite field Diffie-Hellman (FFDHE) to obtain the same level of security.

How much smaller are we talking about? According to NIST recommendations, a 256-bit elliptic curve provides about the same security as working over a 3072-bit finite field. Not only are elliptic curves smaller, they scale better. A 512-bit elliptic curve is believed to be about as secure as a 15360-bit finite field: a factor of 2x for elliptic curves and a factor of 5x for finite fields.

The core idea of Diffie-Hellman is to pick a group *G*, an element *g*, and a large number of *x*. If *y* is the result of starting with *x* and applying the group operation *x* times, it is difficult to recover *x* from knowing *y*. This is called the discrete logarithm problem, taking its name from the case of the group operation being multiplication. But the inverse problem is still called the discrete logarithm problem when the group is additive.

In FFDHE the group *G* is the multiplicative group of a generator *g* modulo a large prime *p*. Applying the group operation (i.e. multiplication) to *g* a number of times *x* is computing

*y* = *g ^{x}*

and *x* is rightly called a discrete logarithm; the process is directly analogous to taking the logarithm of a real number.

In ECDHE the group is given by addition on an elliptic curve. Applying the group operation *x* times to *g*, adding *g* to itself *x* times, is written *xg*. The problem of recovering *x* from *xg* is still called the discrete *logarithm* problem, though you could call it the discrete “division” problem.

Some groups are unsuited for Diffie-Hellman cryptography because the discrete logarithm problem is easy. If we let *G* be the *additive* group modulo a prime (not the multiplicative group) then it is easy to recover *x* from *xg*.

Note that when we talk about applying the group operation a large number of times, we mean a *really* large number of times, *in theory*, though not in practice. If you’re working over an elliptic curve with on the order of 2^{256} elements, and *x* is on the order of 2^{256}, then *xg* is the result of adding *x* to itself on the order of 2^{256} times. But in practice you’d double *g* on the order of 256 times. See fast exponentiation.

In the post on FFDHE we said that you have to be careful that your choice of prime and generator doesn’t give the group structure that a cryptanalysist could exploit. This is also true for the elliptic curves used in ECDHE, and even more so because elliptic curves are more subtle than finite fields.

If large-scale quantum computing ever becomes practical, Diffie-Hellman encryption will be broken because a quantum computer can solve discrete logarithm problems efficiently via Schor’s algorithm. This applies equally to finite fields and elliptic curves.