Quantum Computers on Verge of Breaking RSA Encryption

Much of the world’s digital data is currently protected by public key cryptography, and this stronghold is provided by the underlying cryptographic algorithms. An encryption method relies on a code based partly on factoring large numbers. Computers have traditionally struggled to do the calculations based on factoring the numbers because it requires tremendous compute power, so data transferred in this way remains secure. Two pioneers of this method, Whitfield Diffie and Martin E. Hellman, won the 2015 Turing Award, the highest honor in computer science. The thrust of their work underpins the most widely used encryption method in the world called the RSA algorithm. They have assembled the first five quantum bits of a quantum computer that could someday factor any number, and thereby crack the security of traditional encryption schemes.

RSA was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology. Public-key cryptography, also known as asymmetric cryptography. RSA has become the most widely used asymmetric algorithm. RSA derives its security from the difficulty of factoring large integers that are the product of two large prime numbers. Multiplying these two numbers is easy, but determining the original prime numbers from the total factoring is considered infeasible due to the time it would take even using today’s supercomputers.

“RSA is used everywhere,” says Matthew Green, a computer scientist who specializes in cryptography at the Johns Hopkins Information Security Institute. “Every time you make a web connection you’re probably using RSA encryption. Whenever you send a text message on an iPhone, you’re using RSA encryption.”

Quantum computers are superior to traditional computers when it comes to factoring. A classical computer uses bits of information, 1s and 0s. A quantum computer uses what are called qubits, which can be a mix of both 1 and 0 simultaneously and which exist in a delicate quantum state called superposition.

Peter Shor, an MIT math professor, came up with an algorithm to factor large numbers with a quantum computer in 1994 but had no way to test it. In 2001, Isaac Chuang, an MIT physicist, and electrical engineer, managed to use this algorithm to factor the number 15, but the quantum system he used could not be scaled up to factor anything more complicated. They turned to a quantum computer prototype called an ion trap. In these, the qubits are a string of ions held in place by an electric field and manipulated using pulses of laser light. They needed four qubits to perform Shor’s factoring algorithm and a fifth to act as the output.

Chuang and his collaborators found that the five-atom quantum computer successfully calculated the factors of 15. Previously, experts thought such a calculation would require at least 12 qubits to complete. Chuang says the five-ion model can be scaled up to factor much bigger numbers as long as the ion trap can hold its qubits in place. The team published its results in this week’s issue of Science.

Though a functional quantum computer of the necessary size to crack RSA encryption is still far off in the future, the threat that such a computer poses still resonates among digital security experts.

-Sugandha Sharma