Elliptic Curve Cryptography: Part 2/4 – Why Do We Need It?

In our previous blog post, we discussed public key cryptography and how it works in general. The RSA is so powerful because it comes with rigorous mathematical proofs of security. The authors basically proved that breaking the system is equivalent to solving a very difficult mathematical problem. When we say “difficult”, what it means is that it would take trillions of years to break it even if all the supercomputers in the world were to work in parallel. By the way, this is just one encoded message! The problem in question here is prime number factorization. It is a very well-known problem and has been studied for a very long time. So if it’s such a difficult problem, why do we need something new? What’s the problem here?  

What’s the drawback?

If we were to brute force this problem, it would take a very long time. So people started working on specialized algorithms to tackle this. Algorithms like General Number Field Sieve were created to deal with this problem, and it has been successful to some extent. This is at least better than guessing all possible combinations to factorize the given number!

One of the biggest issues at hand is that the gap between the difficulty levels of multiplication and factorization is decreasing. As in, multiplying large numbers is becoming more difficult with increasing size of the numbers. Also, factoring large numbers is becoming easier as we have more powerful machines now. Since we have more resources available to decrypt the messages, the size of the keys needs to grow even faster. This means that we need to deal with bigger numbers with each passing day. This is not a sustainable situation for low-powered devices like mobile phones and tablets, because that have limited computational power. So we cannot rely on this formulation much longer. This gets us to the main point at hand. Even though RSA is fundamentally very strong, we cannot trust it to be the ideal system for the future of cryptography. We need a public key system based on a better trapdoor.

What do we need in a new system?

In order to design a new system, we need to understand what’s expected of the new system. One of the most important requirements would be that it should be mathematically strong. As in, it should have a strong mathematical base and machines shouldn’t be able to solve it easily. Ideally, we need something that will do the same job faster and something that will occupy a smaller amount of space. As the computers are getting stronger, we would need something that will not require us to constantly increase the size of the key in order to keep up with the machines. This is where elliptic curves come into picture.

Welcome to the wonderful world of elliptic curves

Once people realized the limitations of RSA, they started looking into different mathematical formulations. They basically looked for problems beyond factorization that can serve as good trapdoor functions. In 1985, mathematicians proposed crypto algorithms based on an abstruse, yet beautiful, branch of mathematics called elliptic curves.

But what exactly is an elliptic curve? How does the underlying trapdoor function work? The thing with elliptic curves is that it’s not straightforward to understand. Factorization is a simple concept to understand, because we have done it many times before. I will try to keep it as simple as possible, but things to going to get a little tricky from here on out. Let’s talk more about it in our next blog post.

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