Elliptic Curve Cryptography: Part 4/4 – How Do We Use Elliptic Curves?

In the previous blog post, we discussed about elliptic curves and saw what they look like. We also looked at some of their special properties that enable it to be a good trapdoor function. But this is still very mathematical, right? The curves are great to look at and we understand general concept of elliptic curves, but how do we use them in real life? The curves denoted by those equations don’t represent the curves that are used in cryptography. In the real world, things are digitized. We need to convert things into bits and move them around quickly. So how do we do it?  

From curves to bits

In order to convert a free-flowing infinitely-large smooth curve into a fixed-size set of digitized values, we have to restrict ourselves to numbers in a fixed range. This is what RSA does too. This means that we cannot allow any value for the points on the curve. First off, we restrict ourselves only to whole numbers. As in, we cannot have floating point values. Secondly, we will only consider values in a fixed range. This means that the curve cannot extend up to infinity. In order to do that, we use a simple trick. We just roll the values over when we hit the maximum. For example, let’s say the numbers are in the range 0 to 14 and you want to add 6 and 10. If you add 6 and 10, you will get 16. So instead of saying 16, you roll over once you hit 14 and start counting from 0 again. This way, the answer will be 1. This is called modulo operation and it’s used extensively in all the crypto schemes.

What exactly is the elliptic curve cryptography system?

To define an elliptic curve cryptography system, we need to pick a prime number which will serve as our maximum. If anything goes above this, we will roll over, just we did earlier with 0-14 and 16. The next thing we need is a curve equation. As in, we need to define a curve that will be used in our system. Now we are ready to pick an initial point on the curve. This will be public knowledge. We start with this point and start applying the “EC-plus” operation to itself ‘n’ times. This number ‘n’ will be a secret, and it is called the private key. A public key is the public point dotted with itself ‘n’ times. Extracting the private key from the public key in this kind of crypto system is called the elliptic curve discrete logarithm function. This is the trapdoor function we were looking for.

As we were discussing earlier, any modern crypto system is based on a hard mathematical problem. As in, a machine shouldn’t be able to solve it easily by brute forcing the solution. In our situation, the elliptic curve discrete logarithm is the hard problem. Mathematicians have been trying to solve this for almost three decades now, and they still haven’t found an algorithm that improves upon the naive approach. Let’s consider the problem of factorization for a minute here. Machines are getting more powerful, so we have to use increasingly bigger numbers. As numbers get bigger, multiplying them gets harder because of limited memory on low-powered devices. Also, since machines are getting more powerful, factorizing a big number into two primes is getting easier. What I mean to say is, the gap between the two directions is decreasing. This is not good for a trapdoor function. Going one way should be very easy, but coming back should be very difficult.

The good thing about ECC is that, unlike with factoring, we don’t have a shortcut that is narrowing the gap in the elliptic curve trapdoor function. This means that for numbers of the same size, solving elliptic curve discrete logarithms is significantly harder than factoring. Since a more computationally intensive hard problem means a stronger cryptographic system, it follows that elliptic curve cryptosystems are intrinsically harder to break than RSA. This doesn’t depend on the strength of the machines, this depends on the strength of the underlying mathematics. As we all know, mathematical strength is the best kind of strength in any crypto system!

How do we compare this to RSA?

We have been talking about ECC and RSA a lot, and how ECC is better than RSA. But we need to a way to understand how we can compare them. In order to do that, a Dutch mathematician named Hendrik Lenstra introduced the concept of “Global Security”. Basically, to compare two crypto algorithms, you can compute how much energy is needed to break it and compare that with how much water that energy could boil. It’s an easy thing to comprehend as compared to using terminology from theoretical computer science! Using this measure, breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. That should give you a clue as to how much stronger ECC really is! To get the same level of security with RSA, we would need a key with 2,380 bits.

If it’s so good, why don’t we use it all the time?

Although ECC is fundamentally really strong, it has its own set of drawbacks. As we know, the algorithm involves taking points on a curve and repeatedly performing an elliptic curve “EC-plus” operation. For any crypto system to be used universally, it needs to be standardized first. So if the designers are not careful, it can easily be designed with a backdoor, meaning that the sequence of numbers returned could be fully predicted by someone with the right secret number. This is not a good trait! We need a really good random number generator to take care of this situation. One thing to note is that this random number generator does not change the strength of the elliptic curve technology itself. Instead, it only raises questions about the standardization process.

Because of some recent reports about hacking and spying, people are more skeptical towards the standardization process. It’s like designing a really difficult question paper for the exam, with some of the examinees already having the answers with them! Almost all of the widely implemented elliptic curves fall into this category. Besides, ECC is relatively new and there are a lot of patents surrounding this technology. So if somebody ends up designing something that infringes on someone else’s work, they might get sued. There are no known attacks on these special curves as such, but people just want to play it safe until all the doubts are clarified.

————————————————————————————————-