Chinese researchers: RSA is breakable. Others: Do not panic!
Quantum computing poses a great opportunity but also a great threat to internet security; certain mathematical problems that form the basis of today’s most popular cryptographic algorithms will be much easier to solve with quantum than with “classical” computers. Recently, Chinese researchers have claimed that an existing algorithm can be used with today’s quantum computers to break the RSA algorithm, which is the fundamental basis of secure internet communication. At the same time, there are doubts about the reliability of the publication.
The basic claim of the paper, published last Christmas by 24 Chinese researchers, is that they have found an algorithm that enables 2,048-bit RSA keys to be broken even with the relatively low-power quantum computers available today.
There is nothing really new in the fact that quantum computers pose a general risk to the reliability of cryptographic procedures that guarantee secure internet communications, such as RSA open-key cryptography or the Diffie-Hellman key exchange algorithm. These procedures are based on mathematical problems that are practically unsolvable with conventional computers, butncan be solved in a few hours with sufficiently powerful quantum computers. Sufficiently large means 20 million quantum bits (qubit) in this case. The problem with this figure of 20 million is that IBM’s quantum computer – the largest quantum computer known today – can only render 433 of these 20 million qubits.
It is not an exaggeration to say that the Chinese researchers chose one of the steepest hills to climb. But can they really overcome this challenge?
Integer factorization is the most widely used infeasible mathematical problem to guarantee that the cryptographic algorithms are practically unbreakable. Factorizing a number consisting of only a few digits is trivial (15 = 3 * 5), but the required computational capacity grows exponentially along with the number of digits. For hundreds or even thousands of digits, the computational effort required is so enormous that even using the highest performance supercomputers, the time required to do the calculation would almost span the lifetime of the universe.
According to the recommendation of the National Institute of Standards and Technology (NIST), the smallest RSA key size that can be considered secure is 2,048 bits. This means approximately 600 digits, but in many cases larger keys of 3,072 or 4,096 bits are also used. There, the number of digits expressed in the decimal number system already exceeds a thousand, meaning that these keys are practically infeasible with traditional methods.
In 1994 Peter Shor already came up with an algorithm that – on a quantum computer only existing in theory at the time – would be able to perform the prime factorization with much greater efficiency than before. This breakthrough would imply that a significant part of our encryption procedures would no longer be resistant to breaking.
Has the cryptographic apocalypse arrived?
The Chinese researchers could only provide a theoretical answer to this question since the solution and the techniques outlined by them require a 372-qubit computer. Though such a computer exists within the walls of IBM, the Chinese researchers did not have this machine at their disposal. However, they did succeed in factoring a 48-bit (15-digit) number with a 10-qubit computer.
This may not seem like much of a breakthrough, but it should be noted that this is the largest number that has ever been factored using a generic algorithm. Not to mention the fact that it was possible to put a theory into practice. The question is whether it was possible to bridge the aforementioned gap. As the correspondence between Bruce Schneier – one of the iconic figures of IT security – and Roger A. Grimes – the author of several books on cryptography – revealed:
“Apparently what happened is another guy who had previously announced he was able to break traditional asymmetric encryption using classical computers… but reviewers found a flaw in his algorithm and that guy had to retract his paper. But this Chinese team realized that the step that killed the whole thing could be solved by small quantum computers. So they tested and it worked.”
You might think that the cryptographic apocalypse is here.
Keep calm and dig deep
The basis of the Chinese researchers’ algorithm relies on Claus Schnorr‘s factorization algorithm (not to be confused with Shor’s algorithm). The Schnorr algorithm works well with smaller numbers – with which the researchers themselves tested it – but falls apart with larger values. It is precisely this limitation that the Chinese researchers claim to have overcome. However, they do not mention any details, and they have not been able to prove the complete theory in practice due to the lack of a quantum computer with sufficient capacity. As Schneier cited the situation on his blog:
“So if it’s true that the Chinese paper depends on this Schnorr technique that doesn’t scale, the techniques in this Chinese paper won’t scale, either. (On the other hand, if it does scale then I think it also breaks a bunch of lattice-based public-key cryptosystems.)”
Does the uncertainty remain until someone tries the algorithm on a sufficiently large-capacity quantum computer? Partially.
There are, in fact, some signs that cast doubt on the whole story. One of these is that the Chinese researchers failed to win the $200,000 prize offered by the RSA Factoring Challenge, which goes to whoever can successfully crack a 2048-bit RSA key. Of course, you could say that they did not have the necessary hardware, but a letter to IBM to get the prize, even if it is shared, would have been certainly worthwhile.
People drawn to conspiracy theories may ask why the Chinese state did not keep the discovery for itself and started pouring money into the development of a suitable quantum computer. This would obviously cost a very substantial amount but would also bring a very substantial benefit.
At the same time, there is also strong skepticism from the scientific side. Scott Aaronson – former researcher at MIT, now at the University of Texas – made a devastating statement on his blog about the Chinese paper. Aaronson, in his pieces of research, primarily focuses on quantum computing and complexity theory, perhaps the most important fields of science concerning our topic. His three-word review about the content of the publication was: “No. Just no.” He criticized the publication in a firm tone:
“Then, finally, they come clean about the one crucial point in a single sentence of the Conclusion section: It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA. ‘Unclear’ is an understatement here. It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr’s algorithm on your laptop. And if the latter were able to break RSA, it would’ve already done so. All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen many.”
Aaronson is not alone in his opinion: many others criticize the research on the same basis, including Peter Shor, who says:
“There are apparently possible problems with this paper.”
It should also be highlighted that the research-sharing platform (arXiv), where the Chinese study was published, does not perform peer reviews, meaning that the mere fact of publication does not mean much, especially in such popular fields as quantum computing and cryptography.
Even if we are able to recognize all the research paper mills – which must necessarily be expected in a popular and highly regarded discipline such as cryptography or quantum computing – the harsh reality remains: Any encrypted data recorded today that uses a cryptographic process that does not withstand the challenges posed by quantum computers could become compromised in the not-too-distant future. As a result, it would be necessary to use algorithms that are thought to be secure against an attack by a quantum computer to mitigate the effect of the harvest-now-decrypt-later technique (as it cannot be eliminated). In the case of a cryptographic problem that received great publicity, such as Heartbleed in 2014, the market reacted relatively quickly, although it was weeks before the error disappeared from the 100,000 most-visited pages. In other cases, which have not received as much publicity, it can take years, according to statistics from Qualys Pulse. In other words, we cannot expect the introduction of post-quantum cryptography to happen much faster than this. This is just like global warming: a problem that cannot be dealt with in the future when it becomes critical; it should be dealt with in the present. The similarity is striking if we consider the fact that scientists have been scaring people with horror stories about quantum computers for decades. What seemed like a theory for a while, has now become the reality. IBM promises a one-thousand-qubit computer by the end of the year, and Google a one-million-qubit one by the end of the decade. The latter does not promise anything good, since it is only a question of data storage capacity – how much data can be accessed after RSA becomes breakable. The first to have machines with sufficient capacity will presumably be the still much-criticized technology giants and the most powerful states. Lawmakers still call for encryption backdoors from time to time, despite the warnings about the serious risks involved, but with such a technical breakthrough, they would not necessarily need to do so. However, this may have consequences that are difficult to foresee both for privacy and the outcomes of conflicts that are increasingly transferred to cyberspace.