An Introduction to Elliptic Curve Cryptography: With Math!
Modern cryptography is a very murky subject for many people, so today I will try to explain to you one of the more complex subjects, Elliptic Curves. Many of you may have heard their name before, but likely don’t know much about them beyond that. To begin, I will describe what an elliptic curve is.
An elliptic curve is an equation in the form where .
If you refer to figure 1, you can see a handy graph of what one elliptic curve looks like.
Now, elliptic curves are useful for crypto because they have some useful properties. They have an identity element (), the have an inverse (), they are associative (), and they are commutative (). This means they form an Abelian group. Which means that they behave “nicely” for how we want to use them.
In the prior section, I listed some equations that likely looked kinda familiar, but also weird because of the symbol. This symbol is similar to + that you know, but is the analogue for adding two points on an elliptic curve. To add two points on an elliptic curve, you draw a line between them, then find the 3rd point on that line that intersects the curve. Then you mirror that point across the x-axis and that point on the curve is the result of that addition. If that description didn’t make the most sense, refer to figure 2 to see a graphic depiction.
However, there are some corner cases we also need to address. What if the line between the two points doesn’t intersect the curve again? Then we say that the third point is 0, which can be thought of as a point at infinity (figure 3).
Lastly, what if we add the same point to itself. This can be done by using the line tangent to the point, and then finding the 3rd point the same way as before (figure 4).
Now that we understand what an elliptic curve is, we must address the motivation for using an elliptic curve for crypto. In traditional public key crypto, the name of the problem that makes them hard to crack is called the Discrete Log Problem. There is an analogous problem on an elliptic curve named the Elliptic Curve Discrete Log Problem. Now even though they are related problems, the time complexity of solving the DLP is less than the time complexity of solving the ECDLP. vs respectively. Thus, elliptic curve crypto is much harder to brute force a solution.
Lastly, I will provide an example of how elliptic curves can be used for crypto. I will begin with describing the traditional Diffie-Hellman key exchange involving two people, Alice and Bob.
To do D-H key exchange, Alice and Bob both public agree upon two numbers g and p that they will share. Then, Alice generates A based on her secret number and Bob generates B based on his secret number using the equations and respectively. They then publicly exchange A and B. Alice then computes and Bob computes . However, these can be rewritten as and which are the same (because these operations are commutative). Thus, they have a shared number, but an outsider must solve the DLP for either A or B using g and m to recover or which can then be used to find this secret shared number. This is visually demonstrated in figure 5
Now, we can write the elliptic curve analog by replacing the operations with .
Thus, D-H key exchange using elliptic curves looks as follows. Alice and Bob agree upon a public point P on shared publicly known curve C. Then Alice generates based on her secret number and Bob generates based on his secret number using the equations (on C) and (on C). They then publicly exchange and . Alice then computes (on C) and Bob computes (on C). These can be rewritten as and (both on c). Again, these are the same it is commutative. Again, they have a shared number (technically a point, but it can be converted to a number), but an outsider must solve the ECDLP for either or using P and the curve C in order to recover or which can then be used to find the shared secret. You can also refer to figure 6.
Now that you’ve got a basic understanding of elliptic curves, it is important to remember, “with great power comes great responsibility.” It is almost never correct to write your own crypto algorithms. You should usually defer to using public and well known implementations. It is very common create bugs in your code that weaken your implementation while still allowing it to “work”.