Chinese researchers claim to have broken RSA with a quantum computer. Experts aren’t so sure.
Researchers in China claim to have reached a breakthrough in quantum computing, figuring out how they can break the RSA public-key encryption system using a quantum computer of around the power that will soon be publicly available.
Breaking 2048-bit RSA — in other words finding a method to consistently and quickly discover the secret prime numbers underpinning the algorithm — would be extremely significant. Although the RSA algorithm itself has largely been replaced in consumer-facing protocols, such as Transport Layer Security, it is still widely used in older enterprise and operational technology software and in many code-signing certificates.
If a malicious adversary were able to generate these signing keys or decrypt the messages protected by RSA then that adversary would be able to snoop on internet traffic as well as potentially pass off malicious code as if it were a legitimate software update, potentially enabling them to seize control of third-party devices.
These issues are a key part of the threat that quantum computing poses to traditional cryptography. In a white paper published by the U.K.’s National Cyber Security Centre in November 2020, experts warned that because almost all of today’s widely-used public-key cryptography systems depend for their security on the difficulty of factoring very large numbers, they would be easy to crack with a large-enough general purpose quantum computer.
The Chinese researchers’ paper, titled “Factoring integers with sublinear resources on a superconducting quantum processor,” features one of the first claims that this can now be practically achieved. They argue that they can break the 2048-bit algorithm using a 372-qubit quantum computer. There are some caveats, however. They only had access to a 10-qubit device to practice on and were unable to demonstrate their hypothesis on anything larger than 48-bits.
Many experts are questioning their findings. The paper itself has been shared through the preprint service arXiv without any meaningful peer-review, something which would generally be considered a necessary minimum standard to weigh the scientific value of a research paper.
A discussion about the paper on Google Groups challenges whether the paper claims that its method for factoring 2048-bit integers is actually any faster than classical methods. Both that discussion, and analysis by cryptography expert Bruce Schneier, warns that the researchers’ algorithm relies on a controversial paper by the German mathematician Peter Schnorr which, while proving an ability to factorize numbers on the scale of the 10-qubit computer used by the researchers, “falls apart at larger sizes.”
Schneier wrote that after the criticism of the paper’s dependence on Schorr’s algorithm was raised with him he was “much less worried that this technique will work now.”
According to the arXiv publication, the authors are affiliated with some of China’s most prestigious universities, including several State Key Laboratories which receive direct funding and support from Beijing. Security experts who have spoken to The Record said they expected that a scientific breakthrough with such a significant security impact would be classified by the Chinese authorities.
Historically there have been examples of such information leaking out against the wishes of the ministries in Beijing. Alibaba Cloud was reportedly sanctioned by the Ministry of Industry and Information Technology after a worker there was credited with disclosing the Log4J vulnerability to the Apache Software Foundation instead of to the Chinese government.
The Cyberspace Administration of China had introduced stricter rules a few months before, in July 2021, around disclosing vulnerabilities for companies operating within its borders. For its part, Microsoft last November accused state-backed hackers in China of abusing these vulnerability disclosure requirements in an effort to discover and develop their own zero-day exploits.