Slashdot Mirror
Israelis Crack RSA 512 Bit in Microseconds
wojo writes "According to this story, the Israeli Weizmann Institute has broken RSA 512 bit encryption in, get this, 12uS (microseconds). And if that was not enough, it's handheld using a mix of quantum and optical computing technology. I need proof, how about you?" Hey, if it's in theThe Sunday Time (UK) it must be true, right?
For all who want an explaination of what quantum computing is all about, point your browsers to http://cryptome.org/qc-grover.htm for a thorough explaination of how exactly such mammoth feats of computing are possible.
They have got Adi Shamir's TWINKLE _concept_ confused with a finished product. NTK took the piss out of this on Friday.
/.
This is a classic demonstration of how poor The Times has become. The paper as a whole and especially it's computer suppliment has been very factually challenged ever since Rupert Murdoch took over. He has attempted to make up for crappy quality with price cuts (20p for the paper some days [30cents]) and has so far failed.
The Times is the worse broadsheet paper in the UK and the sooner American's realise this (no-flamage intended), the sooner we won't have joke stories like this on
The whole issue about adding-a-bit-doubles-the-cracking-time depends on three essential assumptions:
1) Factoring products of primes is an NP problem
2) That NP != P
3) That we live in a P world
One way to solve NP problems in linear time is to break assumption number 3. This is how they used DNA to solve a (rather short) travelling salesman problem by creating a parallel environment. Should quantum computing be used, we might be able to bring our computations into the NP realm, thus solving many complex problems. Kudo's to the person who actually does this though. I doubt the veracity of the article alot.
-B
I haven't seen anyone point out the obvious red flag here.
Suppose I am part of a crack research team, and we succeed in building the world's first, working quantum computer, one capable of almost unbelievable feats of brute-force code-breaking. Imagine our conversation:
"Ladies and gentlemen, by God I think we've done it!" smiles the project coordinator. "Where do we go from here? Ideas, anyone?"
"Publish!" cries a fresh, young intern. Having barely a handful of articles under his belt, he's eager to get his name on something like this.
"Well, perhaps we should hold off, give the world time to prepare," suggests an older and wiser researcher. "This caliber of cipher is still in active use worldwide. It's protecting some pretty sensitive data." She pauses, then adds jokingly, "maybe we could sell it to the highest bidder." This is greeted by nervous laughter.
Me, I'm looking at the mess of patch wires and tangled circuit boards. The machine must cover two desktops! "Why don't we turn it into a handheld device?" I suggest.
The others are startled at first. But as they exchange looks, I see some nods and hear muttered agreement. This is the only logical course of action, and now we all know what must be done.
You state that each extra bit in the key doubles the cracking time. That statement is true only if:
- the key is a symmetric key,
- brute force is used as the cracking method.
When cracking public key cryptosystems, the first assumption is just completely wrong, and the second assumption is often not the case. In this particular case you are completely wrong -- the best known factoring algorithm is the number field sieve, with calculation time O(exp(c (log n)^(1/3) (log log n)^(2/3)). This running time is considerably below the 2^n time that you state.If you leave out the section stating that complexity doubles with each bit, then the rest of your post actually makes good sense.