Slashdot Log In
Israelis Crack RSA 512 Bit in Microseconds
Posted by
Roblimo
on Sun Oct 03, 1999 01:14 PM
from the everybody's-submitted-this-one dept.
from the everybody's-submitted-this-one dept.
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?
This discussion has been archived.
No new comments can be posted.
Israelis Crack RSA 512 Bit in Microseconds
|
Log In/Create an Account
| Top
| 244 comments
(Spill at 50!) | Index Only
| Search Discussion
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
good thing...? (Score:3)
Are they stupid.. (Score:3)
Re:No Way. (Score:3)
See, quantum computers don't do things serially like standard computers. They perform their operations on the entire data set all at once. It doesn't matter if the data set has 1 item or 1 billion items, it takes the same amount of time.
This is known as superposition. I don't know a terrible lot about the theory, but you can find out more at The Center for Quantum Computing [qubit.org]. This Quantum Computing Tutorial [weizmann.ac.il] is difficult to understand if you haven't done at least a little comp sci, and the one at qubit.org [qubit.org] is better for people who've never heard of quantum computing at all.
---
Re:Prove it (Score:4)
Put into perspective (Score:3)
Anyway, lets look at something. Even with a 512 bit number, we can look at a 513 bit number and it should be twice as complex. A 520 bit number is 256 times as complex. It grows at a rate of 2^n. Which is basically useless from an algorithmic point of view, as most useful algorithms should be around n^k where K is a constant or some derivation thereof.
Let me show something. I use a 2048 bit gnupg key (I'm paranoid okay?). This comes out to be 2^1536 times more complex. Thus (courtesy of my handy Ti-85 calculator) it should take about 2.892x10^457 seconds to factor. This comes out to be roughly 9.17x10^449 years.
The only issues that come up are the following. What are the energy requirements for such a device. Do they grow linearly or exponentially? Also what with keyspace does it increase exponentially or linearly. If it is only a linear growth then yes my 2048 bit key is as good as swiss cheese against this and I better come up with a damn good one time pad system.
I couldn't tell from the article, but it sounds as though part of this is based of Shamir's idea on how to factor 512 bit numbers. I seem to remember there was some mathematical oddity that allowed them to be easier for some reason. Can someone fill me in?
W.R.O.N.G pure and simple. (Score:5)
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
Re:Put into perspective (Score:4)
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
the "I am a hoax" red flag (Score:4)
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.
Does Not Feel Believable... (Score:3)
Firstly, it doesn't address just what is supposed to be "broken" in 12 microseconds. I'm not sure that one would be able to decrypt a message of meaningful size with the private key in that period of time.
Secondly, there's a real mixture of "apparent reality" and "future fiction."
It doesn't make sense for both of the following to be true:
The one claim suggest that there is an actual implementation; the other suggests that implementation is still off in the future.
Thirdly, it does not appear to address the consideration that a huge amount of the security of these systems come not simply in the "cool algorithms" being used, but from the careful use of protocols. Recognizing actual information within a message requires analysis of the protocol, and that's something that cryptanalysis does not, in and of itself, address.
RSA-512 may not be of vast strength; the article still does not strike me as believable.
(Aside: I was in a bookstore yesterday and saw Yet Another Book on Codes. Bible Codes, as it happens, but there has been, of late, an increase in the number of books on Real Crypto on bookstore shelves. I can generally evaluate the quality of the book by a 5 second riffle through the pages; if I don't notice large numbers of mathematical equations, I consider that the book is ludicrously worthless. In the case of Bible Codes, large numbers of equations would indicate Probably Serious But Still Worthless... )
You're overreacting... (Score:3)
"After an Israeli research institute said it could break Europe's banking codes in less than a second, a initiative has been launched that could result in unbreakable codes."
Notice the would "could." Not "did," not "has," but "could." This means it hasn't happened yet.
"[Weizmann Institute] claims it has developed a hand-held device that can break the code in 12 microseconds."
Again: claims to have developed a device. Not "cracked a huge RSA key in a completely scientific test."
This offers no proof whatsoever, nor does it go into detail about what the "device" is, except to say that it uses a "mixture of quantum computing and special optical technology." Is this Twinkle? It being a full-fledged quantum computer would be *shocking*, since the most I've heard a quantum computer be able to handle is 5 qbits. Twinkle seems much more likely, and has less repercussions: the attack can't be extended to larger primes in the same amount of time.
What about the RSA implementation? It would be fairly easy to crack an insecure implementation of RSA.
Instead of rasing our blood pressue with speculation and conspiracy theories, let's wait until some facts come through. If this was really that important, it would be making waves in the crypto community instead of impressing
Stop spreading misinformation (Score:4)
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.
Re:W.R.O.N.G pure and simple. (Score:3)
(i) The device is handheld, but uses quantum computing.
plainly bollocks; in order for the quantum state to preserved for any useable length of time WHATSOEVER would require huge amounts of cooling equipment. you're not going to get a handheld device which can cool things to a fraction above absolute zero.
(ii) Holding a quantum state for 12uS, or even long enough to do something of use is sheer fantasy, at least by todays standards.
(iii) If this story were true, it would announce two of the most fundamental breakthroughs in computer science and physics in recent memory; the Times ran this on the inside page of it's supplement, and it has languished there since the 29 September before anybody took notice of it, and then only slashdot. This is implausible, to put it mildly.
(iv) We know about TWINKLE, and this is more than likely to be the machine in question. It does not make any use of quantum computing, at least according to the details we know.
(v) "COULD break European banking codes in under a second"
note the could. 12us defies belief... for RSA 512. make that RSA-40, though, and it seems perhaps plausible that TWINKLE could manage it in under a second (tho 12us still seems implausible). RSA-40 is the standard encryption used throughout europe for all e-commerce deals, including those used by customers dealing with on-line banks. things are starting to make some sense.
(vi) secure quantum communication using entangled photons is nothing new; the research has been going on for some time. The hack probably got confused by this, leading to all the nonsense about breaking RSA.
If it was true, we'd surely have heard more about it by now. it'd be BIG news.
Re: Bible Code (Score:3)
Anyway, the idea behind the Bible Code is that the first five books of the Bible were dictated to Moses by God, as tradition says. If you take every Nth character (skipping spaces?) you will get words scattered among the garble. That's standard statistics and nobody sees any significance in it.
The "Bible Code" explores the shocking, *shocking*, discovery that if you look at *two* different periods you occasionally get words that intersect and are actually meaningful. E.g., you might see something like
H
K I L L S
T
L
E U R O P E
R
Except it would actually look like a scrabble board. Why does
Cue spooky music. The authors made a big point of the fact that they warned the late Israeli leader Rabin (?) that his name appeared with "assassinate", but the warnings were ignored. This is a "prediction" like that skeptics demand, right? Not really. The problems with the Bible Code are:
1) there are often multiple hits on the same concept. BC supporters claim that it's proof of humanity's free will, but many of use are skeptical.
2) there are a lot of garbage hits (e.g., something along the lines of "Hitler" and "peacemaker".) Oh yeah, that's free will again!
3) the same algorithms applied to modern texts produce similar amazing hits. I remember one of the skeptic magazines discussed the amazing prophecies encoded in Moby Dick.
In my view, one shared by many statisticians, the Bible Code is nothing more than proof that if you look hard enough you will eventually find a monkey wildly typing away at "Romeo and Julies". If you assume the first five books of the bible contain 2^16 symbols, then explore every pair of periods between 2 and 2^12 (so you'll get sentence of at least 16 characters), you'll have a sequence of (approximately)
2^16 * (2^12) * (2^12)/ 2 = 2^39
symbols, or on the order of one trillion symbols. No wonder it takes powerful computers weeks to find "meaningful" combinations. It's not because God hid His message well, it's that the message space is so huge.
Basis for the Article (Score:3)
Well, it actually exists [eiqc.org] and it actually was started last Monday. However, several things on the site itself point to the fact that quantum computing has not been developed that can crack RSA 512.
The first bit of evidence is a quote that is on the front page of the site: "NASA are now planning on the basis that Quantum Computing will be mainstream within five years" --Dennis Bushill, Chief Scientist, Langley Research Centre of NASA
Now if the organization was founded in response to the actual development of a quantum computer, I don't think that that quote would be up there. It would say something like "Quantum computing is a reality, and we need to do something NOW"Additionally, it seems to me that the Sunday Times got a lot of its information from the site's news section which mentions the TWINKLE project. The TWINKLE project says that 512 bit encryption could be cracked (meaning if this thing were ever to be developed), and I think that that is where the Times figured it could write After an Israeli research institute said it could break Europe's banking codes in less than a second
After reading the site and rereading the article, it seems to me that the (mis?)information is a collection of three things.... a description of the *potential* power of a *to be built* quantum computer, a misread of the TWINKLE project, and a very creative interpretation of the European Institute of Quantum Computing's website.
Actually, if you read the article with this in mind it never actually *says* that they have the device or the encryption has been cracked. The only thing that it explicitly says this is: "It claims it has developed a hand-held device that can break the code in 12 microseconds." which more than likely is a misinterpration on the reporter's part of something the Weizmann Instutite mentioned than actual fact.
All in all, I think that the Sunday Times has done a horrible job of reporting this, and should be held responsible for the misinformation that they are spreading.