In 1991, the cybersecurity company, RSA Laboratories in Bedford, Massachusetts published a list of 54 increasingly large numbers that it had created by multiplying two prime numbers together. It then challenged the computer science community to factorize them — to find the original prime numbers in each case. The company even offered cash prizes for some of the solutions.
The challenge was designed to assess state-of-the-art capabilities for factoring numbers. That’s important because factoring — or more precisely its difficulty— secures various public key cryptosystems. So advanced factoring capabilities make these cryptosystems less secure.
The challenge ended in 2007 but even today 31 of these RSA numbers remain unfactored. The largest is RSA-2048, so-called because of the number of bits required to represent it.
It would be easy to think that progress in factoring numbers must have stalled. But behind the scenes a revolution has been brewing in the form of increasingly capable quantum computers, which are much better at factoring than conventional machines.
For the moment, these machines are not powerful enough to outperform the most powerful conventional computers. And that raises the question of when they will be.
Quantum Algorithm
Today we get an answer thanks to the work of Bao Yan at the State Key Laboratory of Mathematical Engineering and Advanced Computing in China and colleagues who have developed a way to dramatically boost the power of quantum algorithms capable of factoring numbers.
They use 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 codes of “cryptographic significance”, such as RSA-2048.
The security of public key cryptosystems depends on the mathematical process of factoring, the reverse of multiplication. The interesting feature of multiplication and factoring is that even though they are closely related, they are vastly different to perform.
Multiplying two prime numbers together to get a bigger number is easy. But starting with the bigger number and working out which primes are factors is hard. In fact, the difficulty increases exponentially with the size of the number, and it is straightforward to make a number so big that a classical computer would need the lifetime of the universe to find its factors.
That’s 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.
This thinking changed in 1994, when the American mathematician Peter Shor came up with a quantum algorithm that could factor numbers much more quickly than a conventional algorithm. In one foul swoop, Shor’s work raised the prospect that any public key cryptosystem could be cracked by a quantum computer in future.
The promise of Shor’s algorithm has been a major driving force in the development of quantum computers. But implementing it has turned out to be tricky because it requires quantum computers significantly more powerful than any that are available.
The largest number factored by a quantum computer using Shor’s algorithm is just 21. Other approaches have been more successful but nowhere near powerful enough to tackle the RSA numbers. “The largest integer factored by a general method in a real physical system is 249919,” say Bao and co.
This a number that can be described in 18-bits. However, modern public key cryptosystems depend on significantly bigger numbers that can be described in 2048 bits or more. That's why these cryptosystems look safe from this kind of attack, but an important question is how long it will be before quantum computers can tackle them too.
Quantum-Classical Hybrid
The breakthrough that Bao and co have made is to speed up an alternative approach to Shor’s algorithm, called Schnorr’s algorithm (sic). This is a classical algorithm consisting of several steps that each take 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 factoring process but with a less powerful quantum computer than is necessary for Shor’s algorithm.
The results are impressive. Bao and co have used their approach to factor 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 co.
All this means the prospects for factoring even larger numbers are good. Bao and co calculate that their approach could factor RSA-2048 using a quantum computer with 372 qubits.
“Such a scale of quantum resources is most likely to be achieved in the near future,” they say. Indeed, IBM recently unveiled a quantum computer with 433 qubits.
There is an important caveat, however. It's not just the number of qubits that determines the capability of a quantum computer but it's error rate and at the moment, quantum computers are too error prone to make larger calculations profitable.
Nevertheless, Bao and co's is interesting work suggesting that the RSA numbers are likely to fall like ten pins in the near future. It’s taken more than 30 years, but the RSA Factoring Challenge could finally be close to being solved.
The implications are obvious for the security of public key encryption systems, which are still widely used. Cryptographers have had plenty of time since Shor’s announcement to come up with more secure ways to send messages. Whether they have succeeded should shortly be revealed.
Ref: Factoring integers with sublinear resources on a superconducting quantum processor : arxiv.org/abs/2212.12372
