Can a quantum algorithm crack RSA cryptography? Not yet

Every CISO has encryption implementation decisions to make at a variety of levels and instances as they sort the support needed for business operations such as production, sales, support, data retention, and communication. These decisions tend to lean heavily on the “ease of use” doctrine and ubiquitousness of the various product offerings being considered. Therefore the alarming report on “research” conducted by a pool of Chinese researchers on the “possibility” that RSA cryptographic algorithm was breakable with a quantum algorithm has raised an eyebrow or two.

Quantum computing is a technology with plenty of anticipatory capabilities and the United States is investing heavily in it with a request of $844 million for fiscal year 2023 for Quantum Information Science (QIS) research and development. The recently released 2023 annual report on the National Quantum Initiative was resoundingly positive and the nation’s adversaries are no doubt going to school on it, applying their analytic thinking cap in trying to determine what may be in the “classified” version — given this report is a publicly available document for all the world to read and consume.

Stockpiling intelligence in the hopes of a quantum breakthrough

The US isn’t alone. Those adversaries, China and Russia specifically, are two nations with quantum investments, and they are reported to be stockpiling encrypted communications (storage is cheap) with the hope that downstream the technology will prove fruitful and be the magic key to open those encrypted messages and databases. It is not unusual; the World War II Venona project did much the same. The US and UK intercepted Soviet communications during the war years and beyond and when they had a cryptologic breakthrough, the content of these heretofore secrets communications were no longer secret and espionage cases began to tumble like dominos.

While the US annual quantum report touches on the many aspects of QIS, focus on the threat to vulnerable cryptographic technologies is the germane area when discussing the dubious Chinese report which implied RSA cryptography was vulnerable in the near term. Let there be no doubt the US is invested in — and marching into — the post-quantum cryptographic world with not only both eyes open, but with strategic investments and the mid-2022 identification of four quantum resistant cryptographic algorithms for standardization.

Staying on top of the global quantum game

The National Security Memorandum 10 (NSM10) contents were highlighted as especially important, as outlining the future and is worthy of CISO’s approbation. With emphasis on the whole of government approach which Biden’s administration has made their mainstay approach in the world of cybersecurity. And most importantly to “ensuring that the United States has the necessary talent to remain at the forefront of QIS and effectively update and protect vulnerable cryptosystems.”

It is with this as the backdrop that conclusions of the report “Factoring integers with sublinear resources on a superconducting quantum processor” sounded so ominous to the non-scientific/non-mathematician (like this writer), which is why CISOs need to ensure that they expand their sources of information so as to sort out what is, what may be, and what is way far away over the horizon and seemingly requires alignment of stars to make the theoretical a reality. It’s noteworthy that this is not the first time researchers have taken a stab at cracking RSA.

Debunking claims RSA can be broken

This is where the sage and rational discussion from one Scott Aaronson (who happens to occupy the Schlumberger Centennial Chair of Computer Science at University of Texas and is author of “Quantum Computing Since Democritus”) summed up the Chinese report in his blog “Cargo Cult Quantum Factoring” with a concise three-word review: “No. Just no.”

He had more to say, none of it particularly complimentary, and all of it steeped in his knowledge of various mathematical systems and algorithms (worth the read for those who enjoy a dose of science with a side of snark/humor). The bottom line, is the Chinese paper gave many the impression that RSA cryptosystem was at risk using a “near-term quantum computer.”

Aaronson adroitly parsed the Chinese document and pulled from the verbose paper the key “mealymouthed” word “might”: meaning this might be possible and that might be possible (and pigs might fly, right?). Pulling the money quote from the Chinese authors’ conclusion, “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.”

It was here where Aaronson ridiculed the authors one final time, with the observation: “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.” He concludes: “All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years.”

The takeaway for CISOs and others is that the Chinese report made the sky seem especially susceptible to falling. That was until those who know a thing or two about how math works parsed the research and pulled it apart — keeping the sky in its place, above our heads. The bottom line: Be skeptical of claims in the quantum world as the science continues to develop, albeit at a very rapid pace.