Future quantum computers could crack 2048 bit RSA encryption in 8 hours

Many people, quite rightly, worry that quantum computers will be able to crack over 70 percent of all the world’s most popular encryption technologies, rendering them useless and obsolete, and exposing the sensitive data they’re protecting to anyone who wants to read it. The main encryption technologies at risk though are the ones that encrypt data using so called “trapdoor” mathematical functions that work easily in one direction but not in the other, something that makes encrypting data easy but decoding it hugely difficult without the help of a special key.

These encryption systems have never been touted as unbreakable, but instead their security is based on the huge amount of time, in some cases Billions with a “B” of years, it would take for a classical computer to do the job and break them. In short, modern encryption methods are specifically designed so that decoding them would take so long they are practically unbreakable. But quantum computers change this thinking, radically.

These machines are hundreds of millions times more powerful than classical computers and as a result they’ll be able to break these codes with ease. And for anyone who relies on encryption today that raises a critical question, when will quantum computers be powerful enough to crack these codes? Because after that date, any data protected by this form of encryption becomes insecure.

So, inevitably, computer scientists have attempted to calculate the resources such a quantum computer might need and then work out how long it will be until such a machine can be built. And the answer has always been decades.

Today, that thinking needs to be revised though, again radically, thanks to the work of Craig Gidney at Google in Santa Barbara and Martin Ekerå at the KTH Royal Institute of Technology in Sweden. These guys have found a more efficient way for quantum computers to perform the code-breaking calculations, reducing the resources they require by orders of magnitude.

Consequently, these machines are significantly closer to reality than anyone ever suspected, and that could be a major problem for anyone who’s reliant on encryption to protect information. It’s no surprise therefore that the result will make uncomfortable reading for governments, military and security organisations, banks, and anyone else who needs to secure data for 25 years or longer.

First some background. Back in 1994, the American mathematician Peter Shor discovered a quantum algorithm that outperformed its classical equivalent. Shor’s algorithm factors large numbers and is the crucial element in the process for cracking trapdoor-based codes.

Trapdoor functions are based on the process of multiplication, which is easy to perform in one direction but much harder to do in reverse. For example, it is trivial to multiply two numbers together: 593 times 829 is 491,597. But it is hard to start with the number 491,597 and work out which two prime numbers must be multiplied to produce it.

And it becomes increasingly difficult as the numbers get larger. Indeed, computer scientists consider it practically impossible for a classical computer to factor numbers that are longer than 2048 bits, which is the basis of the most commonly used form of RSA encryption.

Shor showed that a sufficiently powerful quantum computer could do this with ease, a result that sent shock waves through the security industry.

And since then, quantum computers have been increasing in power. In 2012, physicists used a four-qubit quantum computer to factor 143. Then in 2014 they used a similar device to factor 56,153.

It’s easy to imagine that at this rate of progress, quantum computers should soon be able to outperform the best classical ones.

Not so. It turns out that quantum factoring is much harder in practice than might otherwise be expected. The reason is that noise becomes a significant problem for large quantum computers. And the best way currently to tackle noise is to use error-correcting codes that require significant extra qubits themselves.

Taking this into account dramatically increases the resources required to factor 2048-bit numbers. In 2015, researchers estimated that a quantum computer would need a billion qubits to do the job reliably. That’s significantly more than the 70 qubits or so in today’s state of the art quantum computers.

On that basis, security experts might well have been able to justify the idea that it would be decades before messages with 2048-bit RSA encryption could be broken by a quantum computer.

Now Gidney and Ekerå have shown how a quantum computer could do the calculation with just 20 million qubits, and they also showed that such a device would take just a staggering eight hours to complete the full calculation and crack it.

“[As a result], the worst case estimate of how many qubits will be needed to factor 2048 bit RSA integers has dropped nearly two orders of magnitude,” they say.

Their method focuses on a more efficient way to perform a mathematical process called modular exponentiation. This is the process of finding the remainder when a number is raised to a certain power and then divided by another number.

This process is the most computationally expensive operation in Shor’s algorithm. But Gidney and Ekerå have found various ways to optimize it, significantly reducing the resources needed to run the algorithm.

That’s interesting work that should have important implications for anyone storing information for the future. A 20-million-qubit quantum computer certainly seems a distant dream today, but actually, as quantum computers follow a development pattern similar to Moore’s Law, called Rose’s Law, it’s not as far off as people might hope. Furthermore the real question these experts should be asking themselves is whether such a device could be possible within the 25 years they want to secure the information. If they think it is, then they need a new form of encryption, like the ones being proposed already by NIST, and they need it now.

Thankfully, despite the news though for ordinary people like you and I there is little risk. Most people use 2048-bit encryption, or something similar, for tasks like sending credit card details over the internet, so if these transactions are recorded today and broken in 25 years, little will be lost.

But for governments, there is much more at stake, and there are already unconfirmed reports that the NSA are storing huge amounts of encrypted data because they know that sooner rather than later they’ll be able to break it. The messages they send today, between embassies or the military, for example, may well still be significant in 20 years time, and so worth keeping secret. And if these messages are still being sent via 2048-bit RSA encryption, or something similar, then these organisations should start worrying, and quickly.

Ref: arxiv.org/abs/1905.09749 : How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits