How Peter Shor’s Algorithm Dooms RSA Encryption to Failure

This is the fourth article in a seven-part series on Algorithms and Computation, which explores how we use simple binary numbers to power our world. The first article, How Algorithms Run the World We Live In, can be found here.

A few years before Sergei Brin and Larry Page first incorporated their Google search engine into the business that helped build up the Internet as we know it, Peter Shor published a paper about the algorithm that was destined to break open all the locks on the connections that were supposed to keep the whole thing secure. 

Peter Shor wasn’t some malicious anarcho-hacktivist but a mathematician working for AT&T's Bell Labs looking to solve a difficult mathematical problem like every other mathematician in the field. His algorithm, known as Shor’s Algorithm, required a technology that barely existed in theory, much less reality, when he first described it in 1994.

RELATED: WHAT WILL QUANTUM COMPUTING CHANGE, EXACTLY?

There was no reason to think in the late 1990s and early 2000s that we would ever need to worry about the insecurity of RSA encryption, but now we know the truth: RSA encryption is destined to fail. Now, the improbable technology Shor used, quantum computing, is not only advancing at a rate similar to Moore’s Law—meaning that within a decade or two, quantum computers will be powerful enough to run Shor’s Algorithm and bust open RSA encryption—Shor’s algorithm itself helped inspire the development of quantum computing in the first place.

RSA Encryption Was Once Believed Unbreakable

RSA encryption, which is used to encrypt everything from files on our hard drives to confidential Internet traffic, is built on the principles of public key exchange and the computationally difficult problem of prime factorization.

For a classical computer, an efficient algorithm for finding the prime factors of a composite number does not exist, meaning that the best we can do is find an answer a little less awful than exponential time. RSA encryption is usually qualified with a bit length, such as 128-bit, 256-bit, etc., which represents the bit length of the key used to encrypt and decrypt data. So a brute-force algorithm with exponential time complexity working on a 128-bit encryption key would need to attempt 2¹²⁸ values at a minimum.

This is equal to 340,282,366,920,938,463,463,374,607,431,768,211,456 possible keys and RSA encryption keys haven't been as small as 128-bit in more than a decade. The current standard recommended key length for an RSA encryption key is 2048-bit, which is equal to (340,282,366,920,938,463,463,374,607,431,768,211,456)¹⁶ possible keys.

These numbers are unfathomable to us, but there is a way to manage and even perform operations using these numbers, something known as modular arithmetic and it’s these operations that are at the heart of the RSA encryption algorithm.

In many countries that use a 12-hour clock rather than a 24-hour clock to keep time, they use modular arithmetic all the time, literally. If it’s 11 AM and I ask you to meet me in four hours, you know that I want to meet at 3 PM. That’s because we use the number 12, called the modulus, to know when to start counting from zero again. Modular arithmetic uses this same process, only with numbers of enormous size to help perform calculations.

Like any other key exchange system, RSA encryption uses a public key and a private key to encrypt and decrypt data, except RSA encryption uses two numbers as its public key, a public exponent to use for encrypting a message and a modulus for the encrypting operation that produces the cipher. What makes this modulus so important is the fact that it is the product of two very large prime numbers and knowing those two numbers will allow you to reverse engineer the private key that unlocks the encryption.

The difficulty inherent to RSA encryption however is two-fold: the enormity of the numbers involved means you can't brute force your way to the private key and the fact that prime factorization of this unbelievably large number is something no classical computer can hope to do in trillions of years.

How Quantum Computers and Shor’s Algorithm Defeats RSA Encryption

Without getting bogged down in the finite details, Shor’s Algorithm is a three-part answer to the problem of prime factorization for any integer, so it works no matter how large the integer involved. The first part is performed on a classical computer in polynomial time, but it is only the set-up for the second and most important part. The second part requires the use of specially constructed quantum circuits to perform the quantum computation needed to find the value you need for the third part, which allows you to find the prime factors of the integer on a classical computer.

The first part of the algorithm is transforming the problem of prime factorization into an equivalent problem that is solvable, namely, finding the period of a modular operation. If you can find the period of this function using as the integer you want to factor as a modulus, you can find the prime factors fairly quickly on a classical computer with some additional calculations.

The problem is that, like prime factorization, finding the period of this modular operation isn’t something a classical computer can do in polynomial time, but Shor showed in the second part of the algorithm that using a theoretical quantum computer your could calculate this period and, most importantly, he was able to prove mathematically that this part of the quantum algorithm ran in polynomial time. After finding the period, a classical computer could use it to find the prime factors of any integer.

How Peter Shor and Shor’s Algorithm Kick Started Quantum Computing

Peter Shor showed that a theoretical quantum computer could solve an intractable mathematical problem in ways that a classical computer never could by side-stepping the need to calculate single values at a time. Quantum computers can perform operations on qubits in superposition and literally reduce the time complexity of a problem exponentially.

When Shor devised his algorithm, quantum computing didn’t exist in any meaningful way. The idea had been around for a while, but it was entirely theoretical, impractical to even attempt to build, and no one could see the utility in trying to build one since there was no example of anything a quantum computer could do that a classical computer could not.

[see-also]

By showing how a quantum computer could actually be useful in a way that classical computers couldn’t by solving a classically intractable problem in polynomial time, Peter Shor sparked the interests of researchers around the world who began their own research into quantum computing and now actual, working quantum computers are being built. It will be a decade at least before a quantum computer has enough qubits to break RSA encryption, but its end is certain and already cryptographers have opened up new avenues of research into Post-Quantum Cryptography to make sure that everything that needs to remain secure does.

After Peter Shor’s algorithm proved that hard problems for classical computers could be solved, others began looking at other hard problems that might also be solved by quantum computers, and for good reason; of the many problems that remain to be solved, the potential benefit to solving them is as enormous as the problems themselves.

The fifth article in our series on Algorithms and Computation, Algorithms, Optimization, and The Traveling Salesman Problem, can be found here.