Quantum Computer Comes Closer to Cracking RSA Encryption

Shor's algorithm performed in a system less than half the size experts expected

3 min read
Quantum Computer Comes Closer to Cracking RSA Encryption
Illustration: Science Photo Library/Getty

Quantum computers are often heralded as the future of smarter searching and lightning fast performance. But their amazing mathematical skills may also create grave security risks for data that has long been safely guarded by the premise that certain math problems are simply too complex for computers to solve.

Now computer scientists at MIT and the University of Innsbruck say they've assembled the first five quantum bits (qubits) of a quantum computer that could someday factor any number, and thereby crack the security of traditional encryption schemes.

Much of the world’s digital data is currently protected by public key cryptography, an encryption method that relies on a code based partly in factoring large numbers. Computers have traditionally struggled to do the calculations based on factoring, so data transferred in this way remains secure. On Tuesday, 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.

Experts thought such a calculation would require at least 12 qubits. Chuang and his team did it with 5

“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, however, have a leg up over 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.

In their latest work, Chuang and his team wanted to create a quantum computer capable of factoring larger numbers than 15. And for that they’d need a type of quantum computer that stored its qubits in a stable fashion.

“It's the kind of thing that I'm sure governments will not appreciate very much—encryption that is guaranteed by the laws of physics”

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. 

Measuring a qubit knocks it out of superposition and thereby destroys the information it holds. Restricting the measurement step to the fifth ion kept the four involved in the computation from being corrupted.

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. In January, the U.S. National Security Agency posted a FAQ on the risks.

“I think people are starting to get freaked out about it,” Green says. “They still think it's anywhere from 15 to 30 years away but data can last a very long time. The good news is most of the data we had doesn't have to be kept secure for 30 years, but some of it does.”

Even though his work may someday break the code of modern digital security, Chuang sees his experiment as an opportunity to point out vulnerabilities and push security experts to find even more secure solutions for the next generation.  

“This particular demonstration is about breaking security of a well known cryptosystem,” he says. “This is, in a sense, an arms race. As long as we break one, create one.”

Specifically, Chuang expects to see quantum encryption methods that will inscribe sensitive data into the very states of atoms. “It's the kind of thing that I'm sure governments will not appreciate very much—encryption that is guaranteed by the laws of physics,” he says.

The Conversation (0)