What is elliptic curve cryptography, and how does it work? The technology keeps your iMessages encrypted, powers Bitcoin and Ethereum, and just about every major website you visit.
Elliptic curve cryptography (ECC) is a type of public-key cryptographic system. This class of systems relies on challenging "one-way" math problems – easy to compute one way and intractable to solve the "other" way. Sometimes these are called "trapdoor" functions – easy to fall into, complicated to escape.
For example, the RSA system uses a class of "one-way" problems that deal with factorization. Every number has a unique prime number factorization. For example, 8 can be expressed as 23, and 30 is 2*3*5. If I asked you to solve (with a calculator) 13*19, you could quickly tell me that it's 247. However, if I asked you to go the other way and solve the prime factorization of 247, it would be more challenging (even with a computer).
ECC doesn't rely on factorization but instead solves equations (elliptic curves) of the form
y2 = x3 + ax + b
You can see a graph of this equation below. ECC relies on the fact that a third point can be determined, given two points on the line. Here is the graphed equation with points P, Q, and R.
Elliptic curves have some unique properties. The most important one is that a kind of operation can be defined on the curve – an operation that mathematically satisfies a set of criteria called a group. We'll use the + "operator," and you can think of it as a type of addition.
For a line that intersects three points, P + Q +R = 0, which means that P + Q = -R. Point 0 is defined as a "point at infinity" – an easy way to think about this point is to think about parallel railroad tracks that appear to intersect at the horizon.
We define inverses as the point flipped over the horizontal line of symmetry. Commutativity can easily be proven, i.e., P + Q = Q + P. Associativity is not as obvious but also holds, i.e., P + (Q + R) = (P + Q) + R. The identity element (an element that can be applied to any other element and leaves that element unchanged, e.g., "0" in addition) is the point at infinity.
You might be curious about what happens at the edge cases of the group law on elliptic curves. Points that are tangents and the leftmost tangent point on the curve. Here are some other interesting identities you can derive.
Instead of factorization as the complicated "one-way" problem, ECC applies the equation P+P (the tangent line at P) multiple (n) times. The easy-to-verify side of the equation is the starting point P and the ending point E (usually chosen to be 0). The difficult-to-compute part is determining how many times (n) P was added to itself.
There's more to it, but intuitively that's the trapdoor function and how it works. But why elliptic curves over factorization? It turns out that for the same size numbers, it's much harder for one to compute the "difficult-to-compute" side of the function for elliptic curves.
The difference is stark. Here's a chart that makes the security levels more intuitive by comparing the energy needed to compute the "difficult-to-compute" side of the trapdoor function for elliptic curves ("cryptographic hash") and factorization ("RSA modulus") based on the length of the key ("bit-lengths").
For a 242-bit RSA key, you could break the encryption with just enough energy to boil a teaspoon of water. For a 228-bit ECC-based key, you'd need enough energy to boil all the water on earth to break the encryption.
