Cryptography 101: Elliptic Curves (Somewhat) Demystified
This is part of a larger series of articles about cryptography. If this is the first article you come across, I strongly recommend starting from the beginning of the series.
In the previous article, we briefly discussed some of the ideas that underpin a good portion of the most widely used cryptographic techniques out there.
We haven’t yet discussed why groups and modular arithmetic are useful for cryptography. But as you may guess, the general idea is that it allows us to craft problems that are so hard to solve, that it’s practically impossible to crack them even at the expense of astounding amounts of computational resources. So for example, why does a digital signature work? Well, because producing a valid signature is fairly simple with knowledge of a secret key, but impossibly hard without it.
We’ll deal with these considerations later on. For now, I believe it more fruitful to focus on other groups that help make the problems to solve even harder — and this is where elliptic curves come into the picture.
What are Elliptic Curves?
A curve is usually defined by an equation. In the case of elliptic curves, the equation E (which is actually a reduced form, but we’ll go with it) looks like this:
But wait… What does this have to do with groups? This is just a curve after all!
Let’s recap what we’ve learned so far, shall we? A group is defined by a set (let’s call it 𝔾), and a binary operation involving two elements of 𝔾, and producing an output that is also in 𝔾. If we can think of a way to use elliptic curves so that we obtain a valid set and binary operation, then we find ourselves a group.
And surely, there is something we can do!
The group operation
Take any two points P and Q in the elliptic curve, then draw a line through those points. Some basic substitutions show that there will (almost always) exist a third point of intersection. Then take that point, imagine the x-axis is a mirror, and reflect it vertically. Congratulations, you have now arrived at the point R = P + Q!
This process is called the chord-and-tangent rule. And it is, in fact, the group operation that we’re seeking.
The first time I saw this, I recall thinking “what a strange process”. I remember asking myself: why on Earth do you need to flip the third intersection point? And after taking a deeper dive into the subject, all I can say is this: explaining the reason why this makes sense is very far out of the scope of this article. I’ll just ask you to trust me that everything is perfectly sound, at least for now.
You can try this yourself in a graphical tool like Desmos or GeoGebra.
One component down, still one more to go — we also need a set. And since the chord-and-tangent rule maps two points on the elliptic curve to another one, it follows naturally that we’ll be working with a set of points on the elliptic curve. But there are two problems with this, namely:
- Most of the points on the elliptic curve are real-valued, meaning that the coordinates may not be integers. And it’s important that they are: otherwise, we may have rounding errors when computing P + Q.
- There’s an infinite number of points on the curve, and we’re after a finite set.
So how do we solve these problems?
Finding a suitable set
Turns out that some elliptic curves have an infinite number of integer-valued points, this is, points like P = (1,2). Because of this, our first problem disappears somewhat magically with an adequate selection of elliptic curve. Let’s assume that we know how to do that, and focus on the second problem.
There’s a neat trick to turn an infinite amount of integers into a finite set, and we’ve already seen it in action. Can you guess it? That’s right, the modulo operation!
As an example, if we choose q = 11, then the point P’ = (11, 13) on the curve would really be the element P = (0, 2) in our group! See how we applied the modulo operation on each coordinate?
Formally, we say that the elliptic curve is defined over a finite field, so any point that’s “out of range” is just mapped back into range with the modulo operation. This is denoted as:
And there you have it! We now have a set, and a way to compute the result of “adding” two points. But do we? Something’s missing…
The group identity
Take a look at the following picture. What happens if we try adding P + Q in this scenario?
We can immediately see that there’s no third point of intersection! Panic ensues. Does this mean our construction doesn’t work?
Luckily, the crisis is readily averted by defining a new group element, denoted O. Think of it as the a point at infinity — which is not really what happens, but may help conceptualization. This new element has an interesting property, given any point P on the curve:
Doesn’t this ring a bell? Isn’t this exactly what happens when adding zero to any number?
Indeed, this behavior is important in group theory — the role zero plays on the group of integers, and the role O plays on elliptic curves is that of the identity of the respective groups. Adding this element to our set makes it complete — and we can now add two points and always have a valid result.
We’re not done though. There’s one more small detail that we need to cover.
Point doubling
What happens if we try adding P + P? To try and follow the chord-and-tangent rule: we need a line through the two points in the operation, but here… There’s only one! So as the name suggests, we’ll need to consider the line tangent to the elliptic curve at P.
As before, we find another intersection point, flip it, and find P + P, which we shall conveniently denote [2]P. In an absolute struck of inspiration, this operation was named point doubling.
Calculating P + [2]P then proceeds as usual: draw a line through the two points, flip the third intersection point, and voilà! You just got [3]P. Do this again, and you’ll get [4]P. And here, we can observe something peculiar: adding P four times (P + P + P + P) yields the same result as adding [2]P + [2]P!
As innocent as the previous statement looks, it’s actually the most powerful tool we have when working with elliptic curves. Suppose we want to compute [12384162178627301263]P. Doing this one point at a time would take a really long time — but by correctly applying point doubling, the result can be obtained exponentially faster!
This hints at the extremely hard problems that were mentioned at the beginning of this article. And as we’ll soon discuss, this is precisely the kind of hard problems that enable cryptographic constructions based on groups to exist!
Summary
We have just defined elliptic curve groups. They are just a bunch of integer points, which we can add, and which are inside of a range thanks to the modulo operation. Usually, when elliptic curves are mentioned in literature, it means the group, not the curve. If the curve needs specific mention, it’s often called the affine curve.
If you feel like this right now:
All I can say is that this can be hard to wrap your head around upon first contact, but once it sinks in, it feels fairly natural. Give it some time, and don’t hesitate to reach out if you have any questions!
Also, you can play around with elliptic curves in this website.
Our basic groundwork is in place. In the next article, we’ll examine what we can do with our knowledge of elliptic curves. We’ll look at a scheme for asymmetric encryption, and another one for digital signatures. Stay tuned!
