If you look at the technical details of a modern HTTPS connection, an encrypted messaging app or a cryptocurrency wallet, you will almost always find acronyms such as ECDHE, ECDSA, X25519 or Ed25519. They all point to elliptic curve cryptography (ECC), which in recent years has largely replaced RSA in many uses. The main reason is simple: it offers the same security with much smaller keys.
What an elliptic curve is
In cryptography, an elliptic curve is the set of points satisfying an equation of the form y² = x³ + ax + b. Despite the name, it has nothing to do with ellipses: drawn on a plane, it looks like a wavy line, symmetrical about the horizontal axis.
The interesting part is that an "addition" operation can be defined on the points of the curve:
- take two points P and Q on the curve;
- draw the straight line through them: it will meet the curve at a third point;
- reflect that point across the horizontal axis: the result is P + Q.
Adding a point to itself gives 2P, then 3P and so on. In cryptography we do not work with real numbers but with integers modulo a large prime: the curve becomes a seemingly random cloud of points, but the addition rules still hold.
The hard problem
Given a fixed public starting point G, called the generator, you can quickly compute k × G even for a huge number k, thanks to a technique of repeated doubling. The reverse, working back to k knowing only G and the result, is extremely hard. It is called the elliptic curve discrete logarithm problem.
Everything rests on this:
- the private key is the secret number k;
- the public key is the point K = k × G.
Publishing K does not reveal k, just as knowing the product of two primes does not easily reveal the factors in RSA.
Why the keys are so short
For the discrete logarithm on well-chosen curves, no shortcuts comparable to those that exist for factoring are known. The result is a huge difference in size:
| Security level | RSA | Elliptic curves |
|---|---|---|
| 128 bits | 3072 bits | 256 bits |
| 192 bits | 7680 bits | 384 bits |
| 256 bits | 15360 bits | about 512 bits |
Shorter keys mean smaller signatures, faster computation, less energy consumed and less data transmitted. For smartphones, IoT devices and servers handling millions of connections, the difference is real.
Where elliptic curves are used
There are two main applications.
Key exchange (ECDH)
Two parties, each with its own key pair, combine their private key with the other's public key and obtain the same secret point, without ever transmitting it. It is the elliptic curve version of Diffie-Hellman. In the ephemeral variant (ECDHE), used in TLS, keys are generated afresh for every session.
Digital signatures (ECDSA and EdDSA)
- ECDSA is the most widespread signature scheme in web certificates and in Bitcoin.
- EdDSA, in its Ed25519 form, is more recent and designed to be simpler to implement correctly and less exposed to mistakes.
The most widely used curves
- P-256 (also called secp256r1): standardised by NIST, very common in TLS and smart cards.
- Curve25519: designed by Daniel J. Bernstein, used for key exchange (X25519) and, in an equivalent form, for Ed25519 signatures. It appears in many modern protocols and in the main encrypted messaging apps.
- secp256k1: the curve chosen by Bitcoin and other cryptocurrencies.
The choice of curve matters. A curve with weak parameters, or an implementation that does not check whether received points really lie on the curve, can open the way to attacks. That is why it is best to rely on standard curves and mature libraries.
The most dangerous mistake: the random value in signatures
ECDSA signatures require, for each signature, a secret random number called a nonce. If the same nonce is used twice with the same key, or if it is predictable, the private key can be derived from the pair of signatures with simple calculations.
This is not a theoretical risk: it has happened in real cases, including the signing keys of a well-known video game console, compromised precisely because the value that was supposed to be random was always the same. Modern solutions generate the nonce deterministically from the key and the message, or adopt Ed25519, which does so by design.
What about quantum computers?
Like RSA, elliptic curve cryptography would be vulnerable to a sufficiently powerful quantum computer thanks to Shor's algorithm. Elliptic curves remain the best choice among classical schemes today, but the transition to post-quantum cryptography will affect them too, probably with an intermediate phase of hybrid schemes.
In short
- Elliptic curve cryptography rests on the difficulty of recovering k from k × G.
- A 256-bit key offers security comparable to 3072-bit RSA.
- It is used for key exchange (ECDH, X25519) and for signatures (ECDSA, Ed25519).
- Reusing or predicting the nonce in ECDSA signatures allows the private key to be recovered.
- Like RSA, it is vulnerable to future quantum computers and is part of the post-quantum transition.
