In 1991, the cybersecurity company RSA Laboratories in Bedford, Massachusetts published a list of 54 increasingly large numbers it had created by multiplying two prime numbers. He then challenged the computer science community to factor them – to find the original prime numbers in each case. The company even offered cash rewards for some of the solutions.
The challenge was designed to evaluate state-of-the-art number factoring capabilities. This is important because factoring—or, more precisely, its difficulty—provides various public-key cryptosystems. So advanced factoring capabilities make these cryptosystems less secure.
The challenge ended in 2007, but even today there are 31 of them RSA numbers remain unfactored. The largest is RSA-2048, so named because of the number of bits needed to represent it.
It would be easy to think that progress in factoring numbers must have stopped. But behind the scenes, a revolution is brewing in the form of increasingly capable quantum computers that are much better at factoring than conventional machines.
At the moment, these machines are not powerful enough to surpass the most powerful conventional computers. And that begs the question of when they will be.
A quantum algorithm
Today we have an answer, thanks to the work of Bao Yan of the State Key Laboratory of Mathematical Engineering and Advanced Computing in China and colleagues, who have developed a way to dramatically increase the power of quantum algorithms capable of decomposing numbers.
They used their approach to increase the size of the largest number ever factored by a quantum computer. And they say their work paves the way for quantum computers to become capable of cracking “cryptographically significant” codes like RSA-2048.
The security of public-key cryptosystems depends on the mathematical process of factorization, the opposite of multiplication. The interesting thing about multiplication and factorization is that although they are closely related, they are very different in implementation.
Multiplying two prime numbers to get a larger number is easy. But starting with the larger number and determining which primes are factors is difficult. In fact, the difficulty increases exponentially with the size of the number, and it is easy to make a number so large that a classical computer would need the lifetime of the universe to find its multiples.
This is what makes public-key cryptosystems so secure – they’re not perfect, but a conventional computer would need the lifetime of the universe to crack them.
That thinking changed in 1994, when the American mathematician Peter Shore came up with a quantum algorithm that could decompose numbers much faster than a conventional algorithm. In one wrong turn, Shor’s work raised the prospect that any public-key cryptosystem could be broken by a quantum computer in the future.
The promise of Shor’s algorithm is a major driving force in the development of quantum computers. But implementing it has proven difficult because it requires quantum computers vastly more powerful than any available.
The largest number factored by a quantum computer using Shor’s algorithm is only 21. Other approaches are more successful, but nowhere near powerful enough to handle RSA numbers. “The largest integer factored by the general method in a real physical system is 249919,” say Bao and company.
This number can be described in 18 bits. However, modern public-key cryptosystems depend on significantly larger numbers that can be described in 2048 bits or more. This is why these cryptosystems seem immune to this kind of attack, but an important question is how long it will be before quantum computers can handle them as well.
A quantum-classical hybrid
The breakthrough that Bao and co have made is to accelerate an alternative approach to Shor’s algorithm called Schnorr’s (sic) algorithm. This is a classic algorithm consisting of several steps, each of which takes time to solve.
Bao and co’s approach is to use a quantum optimization algorithm to speed up the most time-consuming step. This quantum-classical hybrid approach has the effect of dramatically speeding up the factorization process, but with a less powerful quantum computer than Shor’s algorithm requires.
The results are impressive. Bao and co used their approach to factorize the 48-bit number 261980999226229 using a superconducting quantum computer with just ten qubits. This is “the largest integer factored by a general method in a real quantum device,” say Bao and company.
All this means that the prospects for factoring even larger numbers are good. Bao and co estimate that their approach can factor RSA-2048 using a 372-qubit quantum computer.
“Such scale of quantum resources is most likely to be achieved in the near future,” they say. Indeed, IBM recently introduced a quantum computer with 433 qubits.
However, there is one important caveat. It’s not just the number of qubits that determines a quantum computer’s capability, but also the error rate, and currently quantum computers are too error-prone to make larger calculations profitable.
However, Bao and co is an interesting piece of work that suggests that RSA numbers are likely to drop like ten needles in the near future. It’s taken more than 30 years, but the RSA Factoring Challenge may finally be close to being solved.
The implications are obvious for the security of public-key encryption systems, which are still widely used. Cryptographers had plenty of time after Shor’s announcement to devise more secure ways of sending messages. Whether they succeeded should become clear soon.
Reference: Integer Factorization with Sublinear Resources on a Superconducting Quantum Processor: arxiv.org/abs/2212.12372