In my previous blog, the RSA cryptographic algorithm was showcased an example of the “unreasonable effectiveness of abstract mathematics” in the applied sciences. While RSA is still the most widely used security algorithms today, it is not a bed of roses. More people are using mobile devices such as hand phones, palmtops and other handheld devices to do online transactions. These devices aren’t built for performing big calculations needed to ensure cyber-security. For one thing, they have much less memory and slower processors than the computer sitting on your desk. Moreover, the bandwidth on which mobile devices transmit information is much narrower than is available over telephone lines or cables. The increasingly large numbers that RSA needs to stay ahead of hackers makes it unsuited to the limited capabilities of mobile devices. What then?
Enter elliptic curve cryptography (ECC). This takes us to another realm of mathematics, arguably more abstract that prime number factorization that underpins the RSA algorithm. But ECC is fascinating in its own right and provides security security than RSA. Although not in widespread use as of today, ECC is the future of public-key cryptography.
To briefly recall, modern cryptography is founded on the idea that two keys are needed, one to encrypt the data (the public key) and the other to decrypt the data (the private key). Such systems are known as public key cryptographic systems. All public key cryptographic system operates on a set of algorithms where it is easy to process data in one direction but difficult to undo the data. Algorithms with such characteristic – easy in one direction, difficult in the other – are known as trapdoor functions. RSA is an example. It relies on the fact that multiplying prime number is easy but factorizing them is potentially difficult. ECC also operates as a trapdoor function but using elliptic curves instead of prime numbers.
ECC: The Basic Idea
An elliptic curve is the set of points that satisfy a specific mathematical equation. The equation for an elliptic curve looks something like this:
y2 = x3 + ax + b
That graphs to something that looks an omega turned on its side, where each half is symmetric about the horizontal (x) axis.
What does a curve like this to do with cryptographic security? The answer lies in several interesting properties of elliptic curves.
Property #1
Any non-vertical line will intersect the curve in at most three places.
Take any two points on the curve (say A and B illustrated below) and draw a line through them. It touches A, B and one more point.
Now imagine the curve as the setting for a bizarre game of billiards. You take a ball at point A and shoot it toward point B. When it hits the curve, the ball bounces either straight down (if it’s above the x-axis) or straight up (if it’s below the x-axis) to the other side of the curve. Mathematicians call this billiards move on two points a “dot.”
Any two points on a curve can be dotted together to get a new point. Thus, A dot B = C as shown here:
We can also string moves together to “dot” a point with itself over and over like
A dot A = B
A dot B = C
A dot C = D
… and so on.
The usefulness of this bizarre game for cryptographic security is this: suppose you have an initial point “dotted” with itself n times to arrive at end point. Finding out n when you only know the first point and the end point is hard. In the language of statistics, there are too many “degrees of freedom” to nail the correct path. Another way of looking this is to imagine that you played this bizarre game alone for a random period of time. Your friend walks into the room and sees where your ball has ended up. It is extremely hard for him to determine n, the number of times the ball was struck to get to there. This is so even if he knows all the rules of the game and where the ball started! This makes elliptic curves very good trapdoor functions. Hitting the ball n times to get somewhere is the easy part, figuring out what n is given the initial and end point is very difficult.
Real Life ECC
The simplified curve above is great to look at and explains the general idea of elliptic curves, but it doesn’t represent what the curves used for cryptography look like. For this, we have to restrict ourselves to numbers in a fixed range like in RSA. Instead of allowing any value for the points on the curve, we limit ourselves to whole numbers in a fixed range, crunching out the formula for the elliptic curve (y2 = x3 + ax + b) by using the same trick of rolling over numbers until we hit the maximum. If we pick the maximum to be a prime number, the elliptic curve is called a prime curve, which turns out to have excellent cryptographic properties.
Here’s an example of a curve (y2 = x3 – x + 1) plotted with whole number points represented with a maximum of 97:
Had we plotted the curve will all whole numbers, it would like the smooth omega-shaped curve shown earlier. But with a maximum point value of 97 imposed, our “curve” is a scatter plot of points. While this hardly looks like a curve in the usual sense, it is. The equation for a line on the curve still has the same properties. And if you look closely, you can still see the horizontal symmetry. Moreover, the dot operation can be computed as we did before with a smooth curve: imagine the line between two points as a line that wraps around at the borders until it hits a point the edge of the board (the max) and then is magically transported to the opposite side of the table to continue on its path to an end point.
So What?
Like RSA, an ECC system 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. The elliptic curve discrete logarithm is the hard problem underpinning ECC. So hard that even after three decades of research, mathematicians still haven’t found an algorithm to solve this problem efficiently. The “hardness” of the ECC log function is the reason why cryptographic systems built upon it can be trusted for providing a high level of security.
To get a sense of all this, computer scientists have compared how much energy is needed to break an RSA or ECC system with how much water that energy could boil. It turns out that breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. In contrast, breaking a 228-bit elliptic curve requires enough energy to boil all the water on earth. By this measure, breaking a 228-bit RSA system requires ten times as much energy as 228-bit ECC system. The superior efficiency of ECC becomes especially important when smaller keys are required to deliver the same levels of security, as in a world where more and more data is processed on less powerful devices like mobile phones.
So What?
Like RSA, an ECC system 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. The elliptic curve discrete logarithm is the hard problem underpinning ECC. So hard that even after three decades of research, mathematicians still haven’t found an algorithm to solve this problem efficiently. The “hardness” of the ECC log function problem is the reason why cryptographic systems built upon it can be trusted for providing a high level of security with smaller keys than the RSA algorithm.
To get a sense of this, computer scientists have compared how much energy is needed to break an ECC versus an RSA system with how much water that energy could boil. It turns out that \breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water, whereas breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth! For this level of security with RSA, you’d need a key with 2,380 bits. Said differently, ECC gives a “bigger bang for the buck” than RSA. This superior efficiency of ECC becomes particularly important in situations where smaller keys are required to deliver high levels of security such as when data is processed on less powerful devices like mobile phones.
Video:
Elliptic Curve Cryptography: An Overview (presenter: John Wagon, Dev/Central)
Credits and Further study:
This post draws heavily from an excellent and more detailed presentation of ECC by Nick Sullivan “A Relatively Easy to Understand Primer on Elliptic Curve Cryptography” (https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/2/