RSA broken with quantum computer? Not yet.
There has been ??????????????????????*
*Yet another Chinese Paper on Breaking RSA with a Quantum Computer.
References:
A 2022 Chinese research paper made a big splash, and I read with relish some of the analysis by folks such as Roger Grimes, who wrote a 2019 book on the coming post-quantum crisis, and Bruce Schneier (https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html); and then, I came to the conclusion there wasn't much "there" there. When I referenced the paper in my talk at 2023 Post-Quantum Day in Washington, D.C., right after briefings from the heads of post-quantum at the National Security Agency and National Institute of Standards and Technology (NIST), there was even a bit of snickering from the audience; however, those guys were nice enough to have a beer with me afterward.
This new paper purports to use quantum annealing, a type of quantum computing, to attack public key cryptographic systems such as RSA. Annealing is actually term from materials science which refers to heating and cooling a metal to improve its properties (e.g., reduce hardness and increase ductility).
In terms of quantum computing, annealing is really interesting, and I will try to explain it as follows: Say you have a giant maze with many paths, and you want to find the shortest path to the exit. Quantum annealing helps you explore all possible paths in parallel, thanks to the unique properties of quantum bits (qubits). It works by finding the lowest energy state, which represents the best solution to the problem. And just as in metal annealing, quantum annealing begins by exploring many solutions (high energy state) and then gradually focusing on the best one (low energy state).
D-Wave Systems is a company developing quantum annealing computers designed to solve optimization problems by finding the lowest energy state of the system.
The Chinese paper from researchers at Shanghai University says that the D-Wave Advantage computer uses a "unique quantum tunneling effect that can jump out of the local extremes that traditional intelligent algorithms are prone to fall into..." and thus shows promise for cracking RSA (and also methods used in the symmetric block cipher, Advanced Encryption Standard). However, amid the media hype, let's examine a few true facts:
领英推荐
(1) The research showed promise on 22-bit RSA, the modulus (i.e., two prime numbers multiplied together) of which I could probably factor in my head, and not RSA-2048, which is the bellwether for whether public key crypto is truly dead. In this regard, there's nothing new. Quantum annealing has already been thought of as a great application for factoring large numbers in the future.
(2) D-Wave responded to the paper and said it provided "no new fundamental breakthrough in capability..." and that (breaking RSA-2048) "would require quantum processors many orders of magnitude larger than today's scale...Moreover, there are post-quantum encryption protocols available."
(3) As I learned in preparing for my 2023 BSides Tampa talk, the 2022 paper's "sublinear-resource quantum integer factorization" approach claimed it would need only 372 qubits and a circuit-depth of "thousands" to break RSA-2048. However, the integrity of the qubits is the biggest factor in their performance. At that time, for instance, the IBM Osprey quantum computer had 433-qubits; however, we didn't know (nor did IBM advertise) what its fidelity and circuit depth were. Accordingly, experts surmised the fidelity to be about 99.9% (but would need to 99.9999% for quantum applications), and its circuit depth was about 100 (but would need to be more like 1,000+).
The skinny is that we are still a few years away from RSA being at risk from quantum computers, and one should be careful about buying into the hype of articles in Newsweek and CSO Online. Instead, we should focus on:
Vigilance: keeping an eye on quantum progress and being ready to react quickly
Visioning: coming up with plans and scenarios of how to respond.
Begin planning and implementing post-quantum cryptographic solutions for secure messaging, virtual private network (VPN), identity & access management (IAM) and other network functions. Make sure these solutions are:
Great article, Jeremy! It highlights the very real threat quantum computing poses to current encryption standards. In my mind, it's a matter of when, not if, adversaries will be able to crack encryption like RSA leveraging quantum computing. The urgency of this issue is comparable to the Y2K crisis, but with potentially even more severe consequences. The unknown factor of how much encrypted data has been harvested by adversaries adds an extra layer of complexity and risk. Decrypting and potentially releasing this data could have a devastating impact on national security, businesses, and individuals.
CISO x3, Board Member, Cyber Founder
1 个月smart article and the right way to think this through.
Data-Focused Software Developer and FP Enthusiast
1 个月Also, the second paper from Shanghai University only claimed to factor a 50-bit integer, so there's even a way to go, but it's interesting.