Posted on 01/04/2023 10:35:59 AM PST by Twotone
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.
(Excerpt) Read more at schneier.com ...
Live by the computer
Die by the computer.
Bitcoin’s algorithm? Are they going to be able to crack it? SHA-256 seems a lot smaller than that mentioned in the article.
This will send the financial types into orbit..
Uuuh, whaaa?!? Lol!
I’ll bet the Chinese aren’t using inclusive equity math.
SHA-256 is easily defeated using rainbow tables. Schneier is one of the most credible security/crypto people in the business. He was always approachable at UseNIX with serious security questions.
breaking? more like brute-forcing
Perhaps not today, but in the near future, whatever encryption Bitcoin uses will had been cracked by quantum computers.
This is akin to but much larger than USA cracking the Japanese Navel Codes and combined with the British cracking the German Enigma codes during WW II.
China may be lying about this capability, but it’s not something we can take lying down, it could be possible, and we should be doing everything possible to counter it.
You know. Live by the sword. Die by the Sword. I just re adapted it. Man is giving control of his entire life over to the computer. Those that control the computers control man. Not to even mention AI. What is coming is not pretty.
The same has been said about every major innovation.
“What is makeable by man is breakable by man.”
“NEW
“What is makeable by man’s machines is breakable by man’s machines.”
Yes, I always said that would work. Predicted it years ago.
Sounds good, but will this work on my VIC-20?
RSA published a factoring challenge years ago. While they’ve since withdrawn the challenge, I believe all of the messages were published. If they break one of those we’ll believe them.
I'll wait for more knowledgeable freepers to tell me I'm a dummy who got it all wrong. They'll be right, no doubt!
Me too.
Uh, whats a quantum approximate optimization algorithm?
So does this mean a new PlayStation 6 will be coming out soon?
Oh come on. You can’t even compare this to anything else. The digital technological beast never existed in the past ever. That kind of power to monitor and control has never existed before.
—”Sounds good, but will this work on my VIC-20?”
Most likely you will be unhappy with the performance and need to upgrade to a C-64.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.