An interactive intro to Elliptic Curve Cryptography
For my Master's program, I recently took a course on Applied Cryptography which I really enjoyed. I will be writing several posts on various cryptography concepts to cement what I learned
Suppose two people want to communicate privately over the internet. They could encrypt their messages, scrambling them so that only someone with the right secret key can read them. But that raises an immediate problem: how do they agree on that secret key in the first place? They can't whisper it to each other. Every message between them passes through the open internet, where anyone could be listening.
One solution is public-key cryptography: each person has two linked keys, a private key they keep secret and a public key they share openly. The keys are mathematically related, but computing the private key from the public key is so hard it's effectively impossible. That one-way relationship is what lets you encrypt messages, agree on shared secrets, and sign data to prove authorship.
The first widely used public-key systems were built on the difficulty of specific math problems. RSA relies on the fact that multiplying two large prime numbers is easy, but factoring the result back into those primes is extremely hard. Diffie-Hellman relies on a similar idea using exponents in modular arithmetic (clock arithmetic where numbers wrap around at a fixed value).
Both systems work, and both are still in use. But they share a practical problem: the keys are enormous. A commonly recommended minimum for RSA today is 2048 bits (about 617 decimal digits), but for 128-bit security equivalence RSA needs 3072 bits. As we push for stronger security, the numbers grow fast: RSA key sizes grow much faster than security targets, because the underlying factoring attacks are sub-exponential.
What if a different mathematical structure could give us the same guarantees (easy in one direction, effectively impossible in reverse) but with much smaller numbers? That structure exists, and it comes from the geometry of curves.
Drawing the curve
A mathematical equation can define a shape. Take the equation y = x 2 y = x^2 y=x2, which says "y equals x squared." To draw it, you pick values of x x x, compute y y y, and plot each resulting point on a grid. Step through the process below:
Plotting y = x² x y ( -3 , 9 ) -3
... continue reading