https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html Schneier on Security Menu * Blog * Newsletter * Books * Essays * News * Talks * Academic * About Me Search Powered by DuckDuckGo [ ] [Go] ( ) Blog ( ) Essays (*) Whole site Subscribe Atom FeedFacebookTwitterKindleE-Mail Newsletter (Crypto-Gram) HomeBlog Breaking RSA with a Quantum Computer A group of Chinese researchers have just published a paper claiming that they can--although they have not yet done so--break 2048-bit RSA. This is something to take seriously. It might not be correct, but it's not obviously wrong. We have long known from Shor's algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what's possible today. (The IBM Osprey is a 433-qbit quantum computer, for example. Others are on their way as well.) The Chinese group didn't have that large a quantum computer to work with. They were able to factor 48-bit numbers using a 10-qbit quantum computer. And while there are always potential problems when scaling something like this up by a factor of 50, there are no obvious barriers. Honestly, most of the paper is over my head--both the lattice-reduction math and the quantum physics. And there's the nagging question of why the Chinese government didn't classify this research. But...wow...maybe...and yikes! Or not. "Factoring integers with sublinear resources on a superconducting quantum processor" Abstract: Shor's algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglogN ), which is sublinear in the bit length of the integer N , making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance. In email, Roger Grimes told me: "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." EDITED TO ADD: One of the issues with the algorithm is that it relies on a recent factoring paper by Peter Schnorr. It's a controversial paper; and despite the "this destroys the RSA cryptosystem" claim in the abstract, it does nothing of the sort. Schnorr's algorithm works well with smaller moduli--around the same order as ones the Chinese group has tested--but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that's the details behind the Grimes comment) but don't give any details--and they haven't tested it with larger moduli. 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.) I am much less worried that this technique will work now. But this is something the IBM quantum computing people can test right now. Tags: academic papers, China, cryptanalysis, cryptography, quantum computing, RSA Posted on January 3, 2023 at 12:38 PM * 11 Comments Comments Emoya * January 3, 2023 1:04 PM Let the games begin... Alan * January 3, 2023 2:21 PM What exactly does "break" mean in this context? That it takes 10 million years instead of 100 million years? Bruce Schneier * January 3, 2023 2:34 PM @Alan: In this context, "break" means factor in reasonable human time. Fast enough that we normal people care. Greg * January 3, 2023 2:41 PM What are the implications if they can? Please be specific. I'd love practical examples. Eg: if RSA == public key, does that mean people can just start printing/stealing BTC? What can be DONE with such things? (For context someone told me long ago the NSA can do this, odd to see it written about a decade later with the nation swapped.) Frazzled * January 3, 2023 2:42 PM Keeping scientific research a secret is difficult. Allowing its public release, suggesting U.S. govt RSA encryption is insecure, may benefit China by disrupting military and intelligence security. Anonymous * January 3, 2023 2:49 PM I wonder how long it will take for elliptic curve cryptography to go as well - hopefully before NIST standardize quantum-resistant algorithms in 2024. vas pup * January 3, 2023 3:40 PM China cracks advanced microchip technology in blow to Western sanctions https://finance.yahoo.com/news/ china-cracks-advanced-microchip-technology-171655972.html "China has cracked a microchip design method previously only mastered by the West, in a challenge that could undermine sanctions. Using so-called extreme ultraviolet lithography (EUV) technology, transistors can be created that are just nanometers in size. The most powerful computer chips contain millions of transistors and advances in miniaturization allow for the creation of hugely powerful chips. The highly specialized technique has only ever been cracked by Netherlands-based company ASML. A EUR208bn business, ASML's chip-making secrets are jealously guarded by both the company and the West." I had no doubt they will do this because they many talented electric and other technology specialized engineers, supporting staff. Regardless of ideology, China appreciate real merits. That is why sooner or later becoming # 1 world leader. Anonymous * January 3, 2023 4:11 PM So much for Lastpass's "millions of years" estimate to crack all the vaults that were stolen. Clive Robinson * January 3, 2023 4:20 PM @ Bruce, ALL, "This is something to take seriously. It might not be correct, but it's not obviously wrong." Either way it's serious food for thought. I must admit though that if it is wrong, knowing why it's wrong, may turn out to be rather more interesting than if it's right. Clive Robinson * January 3, 2023 4:42 PM Vas pup, "China cracks advanced microchip technology in blow to Western sanctions" These days "cracks" is not the word I'd use as it carries to many adverse conitations -same as "hacks"- thanks to journalists and prosecutors. What they have done is simple to describe more elegantly. That is, "China has by independent research created a technology to use extream ultraviolet light for chip lithography of nano scale parts". I would say that it was inevitable that they would for two reasons, 1, It's known it can be done. 2, They have a need for such technology. The interesting question will be how different will the techniques or methods be, especially as it is a very many step process. That there is more than sufficient information in the public domain to be able to follow the Dutch Path is known. Thus the Chinese could end up with broadly the same method. However there has been continuing research since the original Dutch implementation, so the Chinese systen could use different methods, that might ultimately be more beneficial in some ways. I guess we are going to have to watch to see. However this news is not good geo-politically. Some US Government actions and political agendas with regards other nations in the West Pacific and South China Seas have been predicated on keeping china away from such technology... So there will be political fall out. Itan Barmes * January 3, 2023 4:49 PM The authors do not elaborate on the scalability of this method. They use a quantum algorithm called QAOA which is known to be problematic in scaling. So far is QAOA questionable in showing quantum advantage in general, let alone for such a specific and important problem. I wouldn't get worried just yet Atom Feed Subscribe to comments on this entry Leave a comment Cancel reply Login Name [ ] Email [ ] URL: [ ] [ ] Remember personal info? Fill in the blank: the name of this blog is Schneier on ___________ (required): [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comments: [ ] [loader] Allowed HTML * * * *
    1. * 
       Markdown Extra syntax via
https://michelf.ca/projects/php-markdown/extra/

[Preview] [Edit]

[Submit] 

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

- Friday Squid Blogging: Grounded Fishing Boat Carrying 16,000 Pounds
of Squid

Sidebar photo of Bruce Schneier by Joe MacInnis.

About Bruce Schneier

[Bruce-Schn]

I am a public-interest technologist, working at the intersection of
security, technology, and people. I've been writing about security
issues on my blog since 2004, and in my monthly newsletter since
1998. I'm a fellow and lecturer at Harvard's Kennedy School, a board
member of EFF, and the Chief of Security Architecture at Inrupt, Inc.
This personal website expresses the opinions of none of those
organizations.

Related Entries

  * LastPass Breach
  * LastPass Security Breach
  * Failures in Twitter's Two-Factor Authentication System
  * Regulating DAOs
  * Recovering Passwords by Measuring Residual Heat
  * Leaking Passwords through the Spellchecker

Featured Essays

  * The Value of Encryption
  * Data Is a Toxic Asset, So Why Not Throw It Out?
  * How the NSA Threatens National Security
  * Terrorists May Use Google Earth, But Fear Is No Reason to Ban It
  * In Praise of Security Theater
  * Refuse to be Terrorized
  * The Eternal Value of Privacy
  * Terrorists Don't Do Movie Plots

More Essays

Blog Archives

  * Archive by Month
  * 100 Latest Comments

Blog Tags

  * 3d printers
  * 9/11
  * A Hacker's Mind
  * Aaron Swartz
  * academic
  * academic papers
  * accountability
  * ACLU
  * activism
  * Adobe
  * advanced persistent threats
  * adware
  * AES
  * Afghanistan
  * air marshals
  * air travel
  * airgaps
  * al Qaeda
  * alarms
  * algorithms
  * alibis
  * Amazon
  * Android
  * anonymity
  * Anonymous
  * antivirus
  * Apache
  * Apple
  * Applied Cryptography
  * artificial intelligence

More Tags

Latest Book

A Hacker's Mind

More Books

Support Bloggers' Rights! Defend Privacy--Support Epic

  * Blog
  * Newsletter
  * Books
  * Essays
  * News
  * Talks
  * Academic
  * About Me