The Enigma Code, Zimmerman’s Telegram, the Copiale Cipher, and now … RSA? As with previously “uncrackable codes,” was the 46-year-old RSA public-key encryption system finally cracked? Chinese researchers have claimed their universal quantum algorithm based on Schnorr’s algorithm can reduce the quantum resources needed to break RSA encryption, presenting a near-term possibility that Quantum Computing will break RSA encryption.
Broadly and almost universally implemented in various web browsers, emails, VPNs, and other channels of communication, RSA is arguably the de facto standard of public-key encryption schemes. For years, companies like ours have cautioned users of its future. But with so many competing priorities, this one has frequently been ignored.
Theory Is Nearing Reality
Our blog, Post-Quantum Cryptography—Four Ways to Address the Quantum Threat warned readers of RSA’s vulnerabilities. “Quantum computing will make it extremely easy to perform brute-force attacks on PKI [Public Key Infrastructure], which forms the backbone of much of the current computing landscape.” While we could not have predicted the exact timing of quantum computing’s onslaught, it appears that Chinese researchers had claimed to beat other potential codebreakers like IBM’s 433 qubit computer (Osprey) to the punch. They have effectively “Shor”-tened the quantum timeline.
As Bruno Huttner, ID Quantique’s Director of Strategic Quantum Initiatives, notes in a recent post, “It is too early to know if this new result is as significant as it seems. My guess would be that we will see a flurry of new works and new results very soon in 2023.”
While the Chinese researchers’ paper claims to have moved the needle significantly closer to quantum computing breaking RSA, many industry colleagues and experts are expressing their skepticism. Schlumberger Centennial Chair of Computer Science at The University of Texas at Austin Scott Aaronson has stated simply, “No. Just No.” He goes on to say, “The paper claims … well, it’s hard to pin down what it claims, but it’s certainly given many people the impression that there’s been a decisive advance on how to factor huge integers, and thereby break the RSA cryptosystem, using a near-term quantum computer. Not by using Shor’s Algorithm, mind you, but by using the deceptively similarly named Schnorr’s Algorithm. … All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many.”
Many other industry experts are also not accepting the published paper at face value. In a Google Group discussion, cryptography expert Bruce Schneier stated that he was “much less worried that this technique will work now” after the paper’'s critics questioned its dependence on Shor’s algorithm.
Peter Shor, the MIT scientist whose 1994 algorithm now famously bears his name, told the Financial Times, “As far as I can tell, the paper isn’t wrong.” However, he also noted that the Chinese researchers had “failed to address how fast the algorithm will run,” and that it was possible it “will still take millions of years.” He also said, “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.”
We agree with Co-founder, President, and CEO of evolutionQ Inc. Michele Mosca’s approach to absorbing the paper’s contents. He suggests that leaders:
- “Don’t panic
- Don’t procrastinate in your migration to quantum-safe cryptography
- Plan a migration to post-quantum public-key cryptography, and ALSO be prepared for an unexpected break that works”
As experts debate the validity of the paper’s use of quantum computing to crack RSA, most agree that if this wasn’t the codebreaker, another will surface soon. Pay attention to the warnings. Protecting your data now can help you avoid disaster later.
Contact us to learn more about how Quintessence Labs Quantum-Enhanced Cybersecurity can help you build a quantum-resilient future for your organization.