Chinese researchers have surprised the security community by claiming to have cracked low-level RSA encryption – the standard encryption method used for secure data transmissions around the world – using a hybrid of a quantum and classical computer. The scientists say their method could be used to defeat advanced 2048-bit RSA encryption using a 372-qubit quantum computer, something which would have major security implications.
Such a breakthrough, which could potentially leave corporate networks – and the entire internet – at the mercy of cybercriminals, was thought to be years away, and post-quantum cryptography experts are sceptical about the significance of the claims. They told Tech Monitor the methods described “won’t scale as expected” and that public-key cryptography is secure “for now”.
The quantum computing threat to encryption
There is a race against both time – and the rapidly developing quantum computing industry – to replace RSA and other standard cryptography solutions with post-quantum cryptography which could withstand attacks from such machines. These have the potential to be much more powerful than their classical counterparts, meaning they could break existing encryption methods in a matter of hours or days.
The assumption that quantum computers will eventually break RSA encryption stems from an algorithm published by mathematician Peter Shor in 1994 that has the potential to break most current cryptographic systems, including RSA, in a short amount of time. But it requires a large, stable quantum computer with millions of qubits [the unit of quantum compute power] to work, something which is likely a decade or more away from being a reality. The most advanced machine currently is IBM’s Osprey, which is due to come online later this year and will have 433 qubits.
So the new pre-print paper from researchers at the State Key Laboratory of Mathematical Engineering and Advanced Computing in Zhengzhou, China, has raised eyebrows. It proposes a different algorithm that could crack 2048-bit RSA with a low-level quantum computer.
It is based on a solution proposed by German mathematician Claus-Peter Schnorr, who wrote in 2022 that you could factor large numbers in a more efficient way, breaking the RSA code and doing so with a classical computer.
Classical quantum hybrid used to crack RSA encryption
Schnorr’s technique couldn’t be scaled to work with a regular computer, but the new paper claims to fill in the gap by using a quantum machine to take over part of the calculation, handing the rest to a classical computer. The team say they cracked 48-bit RSA using a 10-qubit quantum computer-based hybrid system and could do the same for 2048-bit if they had access to a quantum computer with at least 372 qubits.
The work reflects a greater drive towards hybrid quantum/classical solutions that includes work by the Riken Institute in Japan to connect a quantum computer to its own supercomputer, Fugaku.
Despite the claims in the paper holding a lot of promise, and hybrid solutions likely representing the short-term future of quantum computing, Ali Kaafarani, CEO and founder of post-quantum cryptography leader PQShield, said the Chinese team “failed to deliver on the promise” of its research.
“Unfortunately, both the classical and the quantum subroutines of the proposed algorithm have serious scalability issues, and in addition, the paper only focuses on the number of qubits – totally ignoring the running time of the proposed algorithm,” he says.
At the end of the paper, the team warns that “quantum speed-up of the algorithm is unclear due to the ambiguous convergence of QAOA”, which is the quantum subroutine used to solve the prime numbers and crack RSA. This suggests there is little evidence it will actually scale as predicted, Kaafarani explains.
“Note that this work is unrelated to Shor’s algorithm,” he says. “That is known to break RSA in polynomial time, and is the main reason for switching to post-quantum cryptography.”
Polynomial time refers to the amount of time it takes for an algorithm to solve a problem, and is generally considered to be good running time for a given algorithm, meaning it can scale to large input sizes without taking an impractically long time to complete.
Want to crack RSA encryption? You might need millions of years
Speaking to the FT, Shor said that the paper failed to address how fast the algorithm would run to crack 2048-bit RSA, leaving open the prospect it would not be able to complete the work in any reasonable time, and suggesting it “could still take millions of years” as it would with a classical computer.
“In the absence of any analysis showing that it will be faster, I suspect that the most likely scenario is that it’s not much of an improvement,” he said.
Bruce Schneier, security research and technologist, wrote a blog post on the findings, warning that even if this doesn't scale "it is something to take seriously" and that "in general, the smart bet is on the new techniques not working. But someday, that bet will be wrong. Is it today? Probably not. But it could be."
“We’re in the worst possible position right now: we don’t have the facts to know," Schneier added. "Someone needs to implement the quantum algorithm and see."
The moment a quantum computer breaks RSA and other cryptography solutions is known as Q-Day among researchers, and it could be anything from a few years to decades away. The significant advantage this would give to a government was cited by some experts as a reason to doubt the Chinese researchers, arguing that if they really had cracked 2048-bit RSA, the Chinese government would have classified the research.
Tim Callan, chief experience officer at security company Sectigo, says it is worth considering the risk of "harvest now decrypt later" as a method that could break RSA-encrypted data in a matter of months or even a few years, as despite not being as rapid as Shor's algorithm, it would open many sensitive secrets to potential exposure. "Think about things like state secrets or manufacturing processes as the information to worry about," Callan says.
"To prepare for RSA decryption, whether it occurs in the short or the long term, organisations must begin researching how hybrid certificates will eventually enable their agility to transition between RSA and either ECC (elliptic-curve cryptography) or quantum-safe algorithms, depending on the circumstances."
He adds: "In the event that quantum decryption becomes possible, implementing hybrid certificates provides a much-needed bridge for organisations to switch hard-coded systems from one encryption algorithm to another.”
Read more: Who are the early adopters of quantum computers? Big banks, that’s who.
