Elliptic Curve Cryptography For Those Who Hate Maths
Elliptic curve cryptography is one of the most powerful but sadly least understood types of cryptography that is in wide use today. For those just looking for a quick answer:
TL:DR : Elliptic Curve Cryptography is the next generation of public key cryptography and based on the current understanding of maths, provides a significantly more secure foundation than the first generation of public key cryptographic systems such as RSA and Diffe-Hellman.
An Elliptic curve is a set of points to satisfies a specific math equation. The equation for an elliptic curve looks like this (This is the only math i promise).
Y² = X³ + ax + b
Whilst there are other representations of elliptic curves, technically an elliptic curve is a set of points satisfying an equation in two variables with degrees two in one of the variables and three in the other. Whilst the elliptic curve does look a lot like a pushed over LuluLemon logo, it does also have some properties that makes it a very good setting for cryptography.
The curve above has many interesting points. One of then is the horizontal symmetry. Any point on the curve can be reflected over the X axis and remain the same curve. A more interesting property is that any-non vertical line will intersect the curve in at most three places.
Breaking this down into a super simple metaphor, lets imagine this curve as a very crazy game of pool. Take any two points on the curve and draw a line through them, it will intersect the curve at exactly 1 more place. In this game of pool, if you take a ball at point A and shoot it towards point B. When it hits the curve, the ball bounced either straight up (if it was below the x axis) or straight down (f it was above the x axis) to the other side of the curve as can be seen in this image below.
Calling this pool move on two points “dot”. Any two points on the curve can in fact be dotted together.
A dot B = C
A dot A = B
A dot C = D
Now if you have two points, an initial point “dotted” with itself n times to arrive at the final point, finding out n when you only know the final point and the first point is hard. Furthering on the metaphor, imagine one person is playing pool alone in a room for a random period of time. It is easy for them to hit the ball over and over again following the rules described above, if someone is then to walk into the room and sees where the ball has ended up, even if they know the rules of the game and where the ball started, they cannot determine the number of times the ball was actually hit. They would have to run through the entire game again until they returned to the same place. This is easy to do but very very hard to undo, which is the basis for a great backdoor.
The curve we have been looking at currently is a simplified curve it is great to explain the general concept of how elliptic curves work, but it doesn't greatly represent what the curves used in cryptography look like.
For this it needed to be restricted into a fixed range, like in RSA rather than allow any value for the points on the curve, we stick to whole numbers in a fixed range. When computing the formula for elliptic curve, the same trick is used of rolling over numbers when they hit the maximum. If we pick a maximum to be a prime number, the elliptic curve is now called a prime curve and has incredible cryptographic properties.
Whilst this doesn't look like a curve in the boring traditional sense, it is in fact a curve, it’s very much like the original curve was wrapped around at the edges and only the parts of the curve that hit whole number coordinates coloured in. You can even still see the horizontal symmetry.
Returning back to our imaginary game of pool, it still applies on this curve and dot points. The equation for the line on the curve still have the same properties. More excitingly the dot operation can be efficiently computed.You can visualise the lines between the two points are a line that wraps around the borders until a point is hit. It’s as if in our game of pool, when a ball is hit the cushion on the edge of table it is magically transported to the opposite side of the table and continues in its path until reaching its point.
With this new crazy and cool curve representation you can take messages and represent them as points on the curve. Now imagine taking a message and setting it as the x coordinate, and solving for y to get a point on the curve, whilst in practise it is more complicated than this, that is the general idea.
So the output is : (71, 6), “-”, (78, 44), (80, 4), 64, 24)
An elliptic curve cryptosystem can be defined by picking a prime number as a maximum, a curve equation and a public point on the curve. A private key is a number priv, and a public key is the public point dotted with itself priv times. Computing the private key from the public key in this kind of cryptosystem is called the elliptic curve discrete logarithm function. This turns out to be the Trapdoor Function we were looking for.
So what does this all mean
The elliptic curve discrete logarithm is the hard problem underpinning elliptic curve cryptography. Despite having three decades worth of research behind it mathematicians still have not been able to find an algorithm to solve this problem that improves upon a naive approach. Unlike with factoring, based on currently understood maths there isn’t a shortcut that is narrowing the gap in a trapdoor function based around this problem. This means that for number of the same size, solving the elliptic curve discrete logarithms is significantly harder than factoring. Since its a more computationally intensive hard problem thus a stronger cryptographic system, it means that elliptic curve cryptosystems are harder to break than RSA or Diffe-Hellman.
With elliptic curve cryptography, you can use smaller keys to get the same levels of security. Small keys are becoming increasingly more important, especially in a world where more and more cryptography is done on less powerful devices such as mobile phones and IOT devices.
A great way to visualise how much harder it is to break, Lenstra introduced a concept of “Global Security”. In this paper you can compute how much energy is needed to break a cryptographic algorithm, and compare that with how much water that energy could boil. Using this measure, breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. In a drastic comparison breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth.
Finish
Now whilst this is a super light introduction into Elliptic curve cryptography is is something that you can now build upon. If you’re interested you can look further into the math or Elliptic Curve parings which is very interesting. But it is your decision if you want to dance with the devil like that.
