In the previous blog post, we discussed why RSA will not be sufficient anymore. We looked at how machines are getting stronger, and that we cannot rely on factorization as our primary mathematical foundation. We also talked a bit about what we are looking for in our new system, and then said a quick hello to elliptic curves. In this blog post, we will see what elliptic curves are. As always, we will keep the equations to a minimum, and instead, try to understand the underlying concept. Let’s go ahead, shall we?
Elliptic curves have nothing to do with ellipses
So we are finally here. We are going to see what an elliptic curve looks like. An elliptic curve is a curve that satisfies the following equation:
y2 = x3 + ax + b
Looks like a simple equation, right? Depending on different values for ‘a’ and ‘b’, the curves will take different shapes as shown in the figure here. There are many other representations of elliptic curves, but basically an elliptic curve is a set of points satisfying an equation in two variables with second degree in one of them and third degree in the other. Okay, so it looks nice and smooth, what’s so special here? An elliptic curve has some properties that make it an ideal candidate for modern cryptography.
It just looks smooth and curvy. What special properties are you talking about?
At first glance, it looks like a regular smooth curve. But if we take a closer look, we can see that it has several interesting properties. One of these is horizontal symmetry. Any point on the curve can be reflected over the x-axis and it will still remain on the same curve. Another interesting thing to note is that any non-vertical line will intersect the curve in at most three places. This will become relevant very soon!
To understand the next property, let’s take two points, A and B, on the curve and draw a line through them as shown here. The line will intersect the curve at exactly one more place, point C. Now, we draw a vertical line through this point and it will intersect the curve in another place, point D. It is basically the reflection of the point C over the X-axis. Let’s call this operation “EC-plus”. It is a random name I just made up! So if you have two points, A and B, on an elliptic curve, then the operation “EC-plus” is going to get you to point D. Pretty straightforward, right? Okay, let’s proceed.
How are these properties related to cryptography?
We can basically “EC-plus” any two points on the curve. If you apply this operation to A and B, you get D. If you apply this to A and D, you get a new point. You can just keep applying this operation to A and the resultant point, you will keep getting new points. Now, instead of starting with two different points, what if we started with the same point? As in, instead of applying the operation to A and B, we apply it to A and A. You might say that infinitely many lines pass through the point A. How do we pick a unique line? In order to deal with that, we take the tangent at point A.
If you apply the operation “EC-plus” to an initial point ‘n’ times, we arrive at a final point. Now, the interesting thing to note is that finding out ‘n’ when you only know the initial and final point is hard. It’s a very simplistic way of putting things, since there are many intricacies involved! But, for the sake of this discussion, let’s say this is what we do. It’s easy for us to keep applying this operation on a given point over and over again. We do it ‘n’ times, and then we get the final point. Now, if someone sees this final point and he knows where the initial point is, he cannot determine the number of times the operation “EC-plus” was applied to the initial point. The only way to do it is to go through the whole process by starting from the initial point until he ends up at the same final point. This is a difficult thing to do! Do you sense a pattern here? It’s easy to go one way, but difficult to come back. This is the characteristic of a good trapdoor function.
In our next blog post, we will discuss how we can use elliptic curves to build a real crypto system.