In the final days of 2022, the IT community was rather stirred by a study presented by a group of Chinese scientists. It claimed that in the nearest future it will be possible to crack the RSA crypto algorithm with a key length of 2048 bits – which is fundamental for the operation of internet protocols – by skillfully combining classical and quantum computing. So how real is this threat? Let’s figure it out.
Quantum basics
The theoretical ability of a quantum computer to perform ultra-fast factorization of giant integers and thus match keys for a number of asymmetric crypto-algorithms – including RSA encryption – has long been known. Our blog post explains in detail what a quantum computer is, how it works, and why it’s so difficult to build. So far, all experts have agreed that a quantum computer large enough to crack RSA would probably be built no sooner than around a few dozen decades. To factorize an integer 2048 bits long, which is usually used as an RSA key, the Shor algorithm needs to be run on a quantum computer with millions of qubits (quantum bits). That is, it’s not a matter of the nearest future, since the best quantum computers today work at 300-400 qubits — and this is after decades of research.
But the future problem has already been actively thought about, and security experts are already calling for adoption of post-quantum cryptography; that is, algorithms that are resistant to hacking with a quantum computer. There seemed to be a decade or more for a smooth transition, so the news that RSA-2048 might fall as early as in 2023 came as a bolt from the blue.
News from China
Chinese researchers have been able to factor a 48-bit key on a 10-qubit quantum computer. And they calculated that it’s possible to scale their algorithm for use with 2048-bit keys using a quantum computer with only 372 qubits. But such a computer already exists today, at IBM for example, so the need to one day replace crypto-systems throughout the internet suddenly ceased being something so far in the future that it wasn’t really thought about seriously. A breakthrough has been promised by combining the Schnorr algorithm (not to be confused with the aforementioned Shor algorithm) with an additional quantum approximate optimization algorithm (QAOA) step.
The proposed scheme of the hybrid factorization algorithm
Schnorr’s algorithm is used for supposedly more efficient factorization of integers using classical computation. The Chinese group proposes to apply quantum optimization at the most computationally intensive stage of its work.
Open questions
Schnorr’s algorithm was met by the mathematical community with certain skepticism. The author’s claim that “this will destroy the RSA cryptosystem” in the description of the study was subjected to scrutiny and didn’t stand up. For example, famous cryptographer Bruce Schneier said that it “works well with smaller moduli — around the same order as ones the Chinese group has tested — but falls apart at larger sizes.” And no one has succeeded in proving that this algorithm is scalable in practice.
Applying quantum optimization to the “heaviest” part of the algorithm seems like a good idea, but quantum computing experts doubt that QAOA optimization will be effective in solving this computational problem. It’s possible to use a quantum computer here, but it will unlikely lead to time savings. The authors of the work themselves carefully mention this dubious moment at the very end of their report, in the conclusion:
It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.
…
Besides, the quantum speedup is unknown, it is still a long way to break RSA quantumly.
Thus, it looks like even if you implement this hybrid algorithm on a classical + quantum system, it will take as long to guess RSA keys as with a regular computer.
The icing on the cake is that in addition to the number of qubits there are other important parameters of a quantum computer, like levels of interference and errors, and the number of gates. Judging by the combination of required parameters, even the most promising computers of 2023-2024 are probably not suitable for running the Chinese algorithm on the needed scale.
Practical takeaways
While the crypto revolution is once again being delayed, the buzz around this study highlights two security-related challenges. First, when choosing a quantum-resistant algorithm among numerous proposals for a “post-quantum standard”, new algebraic approaches – such as the aforementioned Schnorr’s algorithm – should be studied scrupulously. Second, we definitely need to raise the priority of projects for the transition to post-quantum cryptography. It will seem like a non-urgent matter only until it’s too late…
