Elliptic Curves introduction
·
Elliptic curves often feel like mathematical magic. Somehow, with relatively simple arithmetic operations on points, we can build secure cryptographic systems. But the underlying ideas are actually not that difficult once we break them down step by step.
An elliptic curve is simply a collection of points that satisfy a specific mathematical equation. These points live inside a finite field of numbers, and special rules define how points can be combined with each other.
Surprisingly, these simple rules are enough to build powerful cryptographic systems.
So how do these points get calculated? The curve is defined by an equation and the points on the curve are the solutions to that equation. Let’s take a simple example of a very small curve that we can use for demonstration purposes. The curve is defined by the equation:
y^2 = x^3 + ax + b
Where a and b are constants that define the shape of the curve. For our example, let’s use a = 2 and b = 2. So our equation becomes:
y^2 = x^3 + 2x + 2
However, we now have infinite points on the curve, since we can use any value for x and y. To make things work for cryptography, we need a finite field of numbers. We can do this by using a modulus. A modulus acts like an analog clock. After hour 12 on a clock, we don’t get hour 13, instead we “wrap” back to hour 1. (At least, on an analog clock. Things get a little more complicated with digital clocks, but let’s not go there).
In our case, we decide to use a modulus of 17, which means that when we reach the number 17 we wrap back to 0. So our equation becomes:
y^2 = x^3 + 2x + 2 (mod 17)
This means we now have a finite set of values for both X and Y, namely 0 to 16. But not every combination of X and Y forms a valid coordinate on the curve. A point is only valid if its X and Y values satisfy the formula above. (Technically and mathematically, there is an extra special point at “infinity”, which acts a bit like the number zero, but we can ignore that for now).
Without going through all the math, with such a small finite field, we can figure out all the points on our curve. We can do this brute-force, since we have a very small curve. You cannot do this easily on a regular curve that we use for cryptographic purposes).
The points:
(0,6)
(0,11)
(3,1)
(3,16)
(5,1)
(5,16)
(6,3)
(6,14)
(7,6)
(7,11)
(9,1)
(9,16)
(10,6)
(10,11)
(13,7)
(13,10)
(16,4)
(16,13)
Now, just because we can calculate all the points on the curve does not mean that these points are ordered in that way. Elliptic curves do not work like a regular number line where you move from the first point (0,6) to the second point (0,11) and so on. The points are not arranged in any particular sequence, and there is no concept of a “next” point or “previous” point. They are simply valid points that satisfy the curve equation. However, we can still perform mathematical operations on them.
Let’s assume we pick one point on the curve and call it our base point, often referred to as the generator point G. For our example, let:
G = (5,1)
On this tiny toy curve, we can more or less arbitrarily choose any point as our generator point. On real cryptographic curves, however, the generator point is carefully chosen so that it has special mathematical properties that make it suitable for cryptographic use.
At this point, we could calculate something like 2G, which means we want to add the point G to itself (G + G). We could also calculate 3G, which means we want to add G to itself three times (G + G + G), and so on.
To do that, we need a little bit of math, but it’s fairly straightforward and we don’t need to worry about that now. Let’s assume that we can easily calculate these operations, and here is what we get starting at G = (5,1):
2G = (6,3)
3G = (10,6)
4G = (3,1)
5G = (9,16)
6G = (16,13)
7G = (0,6)
8G = (13,7)
9G = (7,6)
10G = (7,11)
11G = (13,10)
12G = (0,11)
13G = (16,4)
14G = (9,1)
15G = (3,16)
16G = (10,11)
17G = (6,14)
18G = (5,16)
19G = (0) (infinity point)
20G = (5,1) == G
21G = (6,3)
22G = (10,6)
As you can see, when we hit 19G we get the special infinity point we mentioned earlier, and after that we wrap back around: 20G = G = (5,1), 21G = 2G = (6,3), etc. This means that our toy curve contains 18 finite points plus the special point at infinity, giving us a total of 19 points in the group.
This is basically all you need to know about the points on the curve and how we can do operations with them. We have a finite set of points, and we can do mathematical operations on those points to get other points. This is the basis for all the cryptographic operations we can do with elliptic curves.
Diffie–Hellman key exchange
Let’s do some basic cryptography with this toy curve.
We can try something called Diffie–Hellman key exchange. This is where two parties agree on a shared secret over an insecure channel. Both will send information to each other, but an eavesdropper will not be able to figure out the shared secret even though the two parties are communicating over an insecure channel.
So we have Alice and Bob. They both agree on the curve they want to use and the generator point G. In our case, they will be using our toy curve and now that the generator point G is defined as point (5,1).
Alice chooses a random number a, and Bob chooses a random number b. These numbers are their private keys and will be kept secret.
Alice picks a = 5, and Bob picks b = 11.
Alice calculates her public key A by computing:
A = aG
As you can see, it works the same way as we calculated 2G, 3G, etc. We are just multiplying the generator point G by a scalar a. Which is a fairly quick and simple operation (note that on our small curve we could also look it up in the table above, but on a real curve we would have to do the math to calculate it).
With a = 5:
A = 5G = (9,16)
Bob calculates his public key B by computing:
B = bG
With b = 11:
B = 11G = (13,10)
Alice sends her public key A to Bob, and Bob sends his public key B to Alice. Everybody can see these public keys , that’s fine. They are public after all.
Now Alice does the following:
S = aB
Alice takes Bob’s public key B and multiplies it by her private key a. This gives her the shared secret S. With a = 5 and B = (13,10):
S = 5B = 5(13,10) = (6,14)
Note that we are not working with the G point, but with bob’s point B. The math stays the same, we are just repeatedly another point to itself using scalar multiplication. We can do that with any point on the curve, not just the generator point.
At the same time, Bob does the same thing:
S = bA
Bob takes Alice’s public key A and multiplies it by his private key b. This also gives him the SAME shared secret S. With b = 11 and A = (9,16):
S = 11A = 11(9,16) = (6,14)
What happened is that taking Alice’s secret number of steps from Bob’s public key gives the same result as taking Bob’s secret number of steps from Alice’s public key.
We can show it in math as well:
S = aB = a(bG) = (ab)G
S = bA = b(aG) = (ba)G
S = 5(11G) = (5*11)G = 55G
S = 11(5G) = (11*5)G = 55G
Because the group wraps around after 19G, we can reduce the scalar modulo 19:
55G = (55 mod 19)G = 17G
17G = (6,14)
This looks easy because we can simply look up that (9,16) equals 5G and (13,10) equals 11G. But on a real-world curve we have an astronomical number of points, and we cannot simply look up coordinates. We need to do the math to compute 5G and 11G, and crucially, it’s not feasible to go from a point back to the scalar that produced it. That problem is called the Elliptic Curve Discrete Logarithm Problem (ECDLP), and it’s where the security of the curve comes from.
A public key point is a visible representation of a secret scalar multiplied by the generator point. And we can do all kinds of math with it to build all kinds of neat security operations.
So by just doing a bit of math, sending the result over to the other party, and they doing a bit on math, both parties have the same secret. Without knowing one of the private keys (which never gets send over the wire), an eavesdropper cannot figure out the shared secret, even though they can see all the public information. This is the magic of elliptic curve cryptography!
There are many more cryptographic constructions built on elliptic curves, but they all rely on the same underlying idea: performing arithmetic on curve points in a way that is easy to compute in one direction, but extremely difficult to reverse.