Georgie Bumpus

As promised (if you don’t remember the promise, go back and re-read article 2 on RSA Cryptography), this is another trapdoor function used heavily in day-to-day life. It’s considered to be even more secure than RSA, so the US government uses it to encrypt internal communications. It also provides signatures in iMessage and is used to prove ownership of bitcoin. In fact, if you’re reading this via Chrome browser, your computer is most likely using ECC (Elliptic Curve Cryptography) to secure the webpage.

But what is an elliptic curve? Confusingly, it doesn’t really have anything to do with ellipses. An elliptic curve is a curve of the form y² = ax³ + bx + c and looks a bit like one of these:

The really cool thing about these curves is that points on them have a group structure. In other words, you can do some operation, which we’ll denote by ∙, to two points on the curve and the result will be another point on the curve. In addition, there’s an identity point, and each point P on the curve has an inverse P^-1 such that P∙P^-1 is the identity point. A full discussion of elliptic curves requires an area called projective geometry, which I’ll try to explain in the next section. But don’t worry, if it all seems a bit scary you can skip the next few paragraphs and just look at the diagram to see how “dotting” points on an elliptic curve works on an intuitive geometric level.

Projective geometry is what happens when we think of infinity as something we can do maths with. Usually if we have a sum like 1 + 1 + 1 + … we would just say it diverges and forget about it. But sometimes it’s pretty helpful to actually consider infinity to be a type of number, or maybe even a set of numbers. We’re going to be working in R² : the familiar 2D plane described by (x, y) for x and y real. In this particular case, we want to think of infinity as “the endpoint of a line”. This will actually give us infinitely many “points at infinity”, because there are infinitely many lines in R² (think of y = mx + c for every possible value of m and c). In this new world, we can think of parallel lines as meeting at a point at infinity, so that we have one point at infinity for every gradient. R² with this set of points at infinity is called the projective plane, RP^2.

It turns out that one of these points at infinity is the identity of our group of points on a given elliptic curve E, and that point happens to be the point at the end of all the vertical lines. So to draw a line between that point and any other point on R² , we can just draw a line straight up. 

Now we can define our group operation! The calculations get a little hairy, so I’m just going to describe it geometrically and in the nicest case. Take points P and Q on the curve (not at infinity) with P≠Q. Because of the special properties of E, we can draw a line through P and Q which will intersect E at exactly one other point on the curve, which we label R. Now we draw a line through R and the identity point – remember, this is just the same as drawing a vertical line through R. This will intersect E at exactly one point, which we’ll call -R (this is just the reflection of R in the x-axis – can you see why by looking at the form of the elliptic curve equation?) Finally we define P∙Q = -R.

Here’s a handy graphic of what’s going on:

In the actual algorithm, we’re initially “dotting” P with itself, so we need to define P∙P. In this case, we just take the tangent at P to the curve E and define R to be the intersection of this tangent with E. Then P∙Q = -R as above.

The main idea behind the algorithm is “dotting” a point with itself some relatively large number of times. Here it is:

Some quick notes:

• Here when we say xP, we mean P∙P∙…∙P x times. 
• Modulo in 2D is very similar to the regular case we looked at before, just the modulo is taken in both directions. 
• Step 7 works because rX is congruent to xR definitionally.

The thing to note about the Elliptic Curve algorithm is how it compares to RSA: it’s considerably simpler and easier to understand, and the prime we need is only 70 digits long instead of 600. That’s still a huge number, but it’s a lot less huge, and doesn’t need nearly so much storage.

ECC is considered to be so much more secure than RSA because breaking it amounts to solving X=xP mod p on a given curve for x, and currently there is no algorithm that can do that – yet. Elliptic curves and their properties, unlike prime numbers, have only been discovered* within the last century or so. They’re also ridiculously niche and complicated, so are an active – if small – area of research. Those working on such algorithms haven’t made anywhere near as much progress (which makes sense; prime number theorists have had centuries instead of decades), to the extent that we don’t even know if the algorithm is computationally “hard” yet. By “hard” I mean whether or not the algorithm can be completed in polynomial time (for an explanation of what this means, check out the end of my last article on RSA).

Elliptic curves are genuinely fascinating objects, though: you can read about the Birch-Swinnerton-Dyer conjecture, a millennium problem about elliptic curves, here. They were also used as a tool to solve Fermat’s Last Theorem** by Andrew Wiles. This proof, unfortunately, is out of reach for me to even begin to explain. Interested readers are advised to take a Masters-level Mathematics course – and while you’re at it, maybe get to work on those algorithms…

*Or invented, depending on your thoughts on mathematical philosophy…

**That is, there are no integer solutions (x, y, z) to xⁿ + yⁿ = zⁿ, for n>2

Article 1: Substitution Ciphers

Article 2: RSA Cryptography