Elliptic Curve Cryptography

When your phone sets up a secure connection to a website, it often does the equivalent of a 3072-bit RSA key's worth of security using a key only 256 bits long. That's roughly 12 times smaller for the same protection level. The reason is a strange piece of math: points on a curve shaped like y² = x³ + ax + b, where you can "add" two points together and get a third point back on the same curve. This is elliptic curve cryptography (ECC), and it now secures most of the encrypted web, Bitcoin wallets, and Signal messages.

- What an elliptic curve is and what point addition means geometrically - Why the "elliptic curve discrete logarithm problem" is hard to reverse - How ECC achieves RSA-level security with much shorter keys - Where ECC is actually used today (TLS, Bitcoin, Signal)

An elliptic curve for cryptography has the form y² = x³ + ax + b (with constants a and b chosen so the curve has no sharp cusps or self-crossings). Pick any two points, P and Q, on the curve. Draw a straight line through them; it will hit the curve at exactly one more point. Reflect that point across the x-axis, and you get P + Q, a third point that's also on the curve. This operation, called point addition, is the entire engine of ECC. Now do something odd: add a point P to itself, over and over, k times. The result is a new point, often written kP. This repeated addition is called scalar multiplication, and it's fast to compute even for enormous k, using a doubling trick similar to fast exponentiation.

Here's the trick that makes it secure: if I show you the starting point P and the final point kP, figuring out the number k is called the elliptic curve discrete logarithm problem (ECDLP), and for a well-chosen curve it is believed to require roughly 2^128 operations to crack for a 256-bit key — computationally impossible with any known classical algorithm, even at datacenter scale. So your private key is just a giant random number, k. Your public key is the point kP, computed using a curve and starting point (called the base point) that are publicly standardized. Anyone can verify signatures using your public point, but nobody can work backward to find your secret number k.

RSA's security relies on the difficulty of factoring huge numbers, and that problem gets easier relative to key size faster than ECDLP does. To match the strength of a 256-bit ECC key, RSA needs roughly a 3072-bit key. Smaller keys mean less data to transmit, faster computation, less battery drain, and easier storage in tiny devices. That's why curve25519 (a specific, widely-audited elliptic curve) is the workhorse behind Signal's end-to-end encryption and behind SSH key exchange on most modern servers.