Why the world uses elliptic curves

If you are reading this blog on a modern browser, you are most likely connected to it using TLS 1.3 which uses an ephemeral, elliptic curve version of Diffie-Hellman (ECDHE) to agree on a shared secret key and start encrypting stuff with it. What makes elliptic curve Diffie-Hellman better than the regular Diffie-Hellman (DHE) is that elliptic curves are more efficient.

As an example, in order to achieve ~128 bit of security with RSA, you need a key that is ~3072 bits long. But for the widely used Curve25519 elliptic curve, it only takes a key that's ~256 bits. For a typical DH operation, two public keys must be transmitted through the wire, so with RSA you'd have 768 bytes of data, but only 64 bytes for Curve25519 and other elliptic curves! Neat.

This massive boost in key efficiency allow connection handshakes to be faster, and for more creativity/security in protocols like being able to generate many ephemeral keys, something which would be inefficient with big keys like RSA.

But why exactly are elliptic curves more efficient? That is today's topic.

RSA's inefficiencies

A cipher is considered (semantically) secure if the fastest approach to cracking it to simply try to bruteforce the key manually. This means that 3072-bit RSA is secure because it'd take on average *waves hands* $2^{128}$ operations to find the key. The same goes for the 256-bit Curve25519 keys.

The "bruteforce" way of cracking RSA is to find the prime factors $p$ and $q$ of $N = pq$, where $N$ is publicly known. A naive way to try and factor $N$ would be to try diving $N$ by $1, 2, \dots, \sqrt{N}$. Note here that diving $N$ by something above $\sqrt{N}$ is useless. At most, you'll have $p = q = \sqrt{N}$, and so if $p \geq \sqrt{N}$, then $q = \frac{N}{p} \leq \sqrt{N}$. In this case you'll find $q$ before $p$.

Usually in cipher complexity we express the number in terms of how many bits we need to store it (we'll name it $n$). We therefore have $N = 2^n$. Our naive algorithm runs in $O(\sqrt N) = O(\sqrt{2^n}) = O(2^{n/2})$ time. That's very inefficient of course. If $n$ was 256 bits, then the algorithm would have a cost of $2^{256/2} = 2^{128}$. That's the 128-bit security cost we discussed earlier! But does this mean that RSA keys of 256 bits are 128-bit secure? No, because there are in fact more efficient algorithms to factor down $N$, some of which are faster enough that in order to compensate for them and keep the cost at $2^{128}$, we need bigger keys.

Currently the "state of the art" for factoring big $N$ numbers like RSA keys is the GNFS algorithm (General Number Field Sieve). It's time complexity is the following: $$O(\exp{(((64/9)^{1/3} + o(1))(\log N)^{1/3}(\log \log N)^{2/3})})$$

with $o(1)$ a constant factor. If we neglect it, then for a key of $n = 256$ bits we have a cost of $2^{46}$ bits (plugging in $N = 2^{256}$ in the equation). That's not good at all and certainly possible to bruteforce[2]. But what about $3072$ bit keys? It comes out at around $\approx 2^{138}$ bits, which is around what we expected (128-bit security)!

You might have already noticed that our naive $O(\sqrt N)$ algorithm implicating that 256-bit keys result in 128-bit security is exactly where Curve25519 is standing at! We'll get to that.

The discrete log problem

Instead of factoring a large number $N$ like RSA does, the problem that elliptic curves assume to be difficult to do is calculating the discrete log of a certain number in a certain group.

Briefly explained, a group is a set of elements ("numbers"), with a given operation ("addition", "multiplication", ...). Repeating this same openation a certain amount of times is called exponentiation. The operation that inverts exponentiation is the logarithm.

For instance, let's look at the group of regular integers with the multiplication law $\mathbb Z^*$. Repeating this multiplication law, for instance $216 = 6 * 6 * 6$ gives you $216 = 6^3$, which is 6 exponent 3. This is our exponentiation! Therefore, inverting this operation, meaning finding $y$ such that $216 = 6^y$, is the logarithm by definition: $\log_6(216) = y = 3$.

Another quick example would be the group of integers modulo $n$: $\mathbb Z / n \mathbb Z$. In this group, the logarithm is the modulo inverse, which is also trivial to do using the Euclidean algorithm[3].

Of course, the solutions to the discrete log problem are easy in the specific groups we just gave, but the discrete log isn't always that easy--and when it comes to elliptic curves, their groups are entirely different ones!

In this elliptic curve world, addition is easy and so is multiplying (which is our exponentiation, using the Double-and-Add algorithm). Dividing it (our logarithm) is not. Therefore, is you have two points on your elliptic curve $P$ and $Q$ such that $P = \underbrace{Q + Q + \dots + Q}_{n \text{ times}} = nQ$, then finding $n$ is hard.

Pollard's rho ($\rho$) algorithm

Possibly the most famous algorithm to compute the discrete log is Pollard's rho algorithm, because it works for any group, whether it's integers with RSA, prime multiplicative groups like ElGamal, or prime fields like elliptic curves. The running time for this algorithm for a group of $N$ elements is $O(\sqrt N)$.

In the general case, we don't know of any faster algorithm than Pollard's $\rho$ algorithm to bruteforce elliptic curves keys.

While there are certain constructions of elliptic curves or groups that have faster known algorithms, this is not the case for the elliptic curves we're using.

Whether the elliptic curves we're using right now in cryptography may have faster ways to compute the discrete log is the the big question of the modern classical cryptography field.

Assuming elliptic curves stay secure for the distant future, this $O(\sqrt N)$ is as good as it can really get. Going back to our Curve25519, its construction is in a prime field whose prime is $2^{255} - 19$ (hence the name), so roughly speaking Pollard's algorithm would have a cost of $O(\sqrt{2^{255} - 19}) \approx 2^{128}$.

Where different elliptic curves implementations differ (Curve25519, P-256, secp256k1...) is in their ease of implementation without Fucking It Up™, and ability to generate keys and whatnot quickly.

The reason Curve25519 is the de-facto standard today is because it's simple to implement, and implement safely, and is really fast thanks to a multitude of mathematical tricks and careful considerations when choosing the elliptic curve.

The post-quantum inefficiency

While Pollard's $\rho$ algorithm is the fastest "general case" algorithm we have in a classical setting, that is not the case in a quantum computing setting, where Shor's algorithms makes factorization and discrete log efficient to calculate. Therefore, we have to come up with new things.

As it stands today, the post-quantum algorithms we have aren't very efficient, and so we're back to RSA-like levels of key sizes. For instance, ML-KEM-768 (192-bit security) comes at around ~1800 bits through the wire.

ML-KEM does not use Diffie-Hellman to do key exchange, instead, it uses key encapsulation (KEM), and relies on the "learning with errors" problem instead of the discrete log. KEM is a form of asymmetric/public-key cryptography that achieve the same result as Diffie-Hellman however (a shared secret key). There is still a long road ahead for this new field of cryptography, and hopefully the very smart and hard working researchers will come up with more efficient solutions!

Footnotes