Israelis Crack RSA 512 Bit in Microseconds 244
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?
good thing...? (Score:3)
wtf!? (Score:1)
/. shut down for revealing secrets 20 yrs early (Score:1)
Prove it (Score:2)
Ack! (Score:1)
Ouch... (Score:1)
The only comfort is that it sounds expensive, so I don't think that we normal users of internet banking have anything to worry about yet... But the day I find a page on the net with the details of one of these devices, I'm gonna stop using internet banking..
Which will be a shame, since it's so much easier to use internet banking than to go to your local branch office....
-just my
No Way. (Score:1)
Re:Confused (Score:1)
---
Not even (Score:2)
Hardware Spec (Score:1)
I *really* think this is a hoax of the highest order.
But hey, that's just me.
Troubling news? (Score:1)
London Times. (Score:1)
They tend to do that.
Neural Nets and Crypto (Score:1)
So which is it? (Score:1)
I am guessing that this means the Weizmann Institute has designed a machine that theoretically could crack RSA 512 encryption IF AND WHEN it can be built.
Are they stupid.. (Score:3)
Ooops! (Score:1)
And here's where I breathe a long sigh of relief, because I use a 2048-bit DSA key in GnuPG. Even if it isn't true, I'm sure that the state-of-the-art in cracking techniques (such as those used by the US' No Such Agency) can crack RSA 512-bit in a very short time. Yes, I think I'll be using my long keys for a long while to come.
holy cows! (Score:1)
from what i understand though, rc5 is just static in its method, while pgp is more flexible. im wondering if this thing would stand a chance against pgp.
begin shameless plug:
btw, my team # 10133, smartasses online
end shameless plug
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:Troubling news? (Score:1)
yeah (Score:1)
then again, it's stuff like this that could be true, and due to the incredulity of it all, we don't take it seriously, and they go change all the rules on us while we're not looking because now they have the power to
Re:No Way. (Score:1)
Re:Ouch... (Score:2)
---
Re:Neural Nets and Crypto (Score:1)
On the other hand, quantum computation, like biological computation, can solve a certain class of problems much faster than conventional computers.
For example, quantum and factorization, biological and string matching.
Noone that I am aware of has shown that quantum or biological computation can solve a general class of problems faster.
Re:Prove it (Score:4)
Re:wtf!? (Score:1)
uS- microseconds
uF- microfarads (most common) etc.
hmm, >554 bit key still safe? :) (Score:1)
(why isnt everyone using 1 meg keys anyway?
---
Hoax or not... (Score:2)
I say this: does it really matter? Since when has the presence of an actual threat over the presence of a perceived threat really meant much in international politics? If the Israelis can convince the world they can do it, without ever proving it, they've succeeded either way.
Personally, I think that better encryption for banking systems is a good thing. I don't want anyone messing with my money, and as stated in a previous post, I like internet banking. So, regardless of whether or not this is a hoax, it's causing an increased notice of cryptography issues. The more people that are aware of security and crypto problems in computing, the better.
Regardless, if it's not a hoax, imagine the implications of the quantum computing! Is it closer than we think?
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?
Relevant links. (Score:1)
No info on their site (Score:1)
It's possible (Score:1)
OTOH, I haven't been keeping up on the state of quantum computing research, so I don't know if something like this could be built. (I remember that several stories about Twinkle made it sound like it actually existed, while it's just a design).
Given the general public's clue-lessness about crypto, I'd wait for some confirmation, preferably by the Weizmann Institue itself.
Why i think this is true (Score:1)
Second you ask why didnt they release it to the world or whatever? Dont you think that it would be mutch more usefull to the israeli military having people not know they could decrypt there messages?
also aparently to an article i read somwhere the NSA etc only tell people that they can crack encryption 10-20 years after they figured out how to so this could be a long time comming and we only hearing about it now
:))
Corroboration? (Score:1)
^.
( @ )
^.
Re:Put into perspective (Score:1)
Be very very worried, oh paranoid one.
---
This sounds rather hoax like (Score:1)
Re:holy cows! (Score:1)
Will or has (Score:1)
The article also confuses Quantum computing with Quantum Cryptography. The whole thing may just be the work of a confused journalist confusing a proposed, speculative design with something that has been built.
Re:Not even (Score:1)
Guess I can't have that USS Enterprise then, huh?
Re:wtf!? (Score:1)
Re:London Times. (Score:1)
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:Ooops! (Score:1)
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
Re:hmm, >554 bit key still safe? :) (Score:1)
Re:Ooops! (Score:1)
Are the algoritms and piece of software used for encryptions (PGP, RSA, etc.) able to trivially scale to an arbitrarily large # of bits? It might be a good idea to start thinking of 10,000 bit keys.
I think not (Score:1)
Their computer coverage is particularly bad. Their feature on the Tomlinson spy incident (where a list of MI6 spies was posted on the web) was so silly it was hard to read itwithout cracking up laughing. A friend bought that day's issue just so he could show it to people for amusement value.
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.
This requires some thought (Score:1)
If they have deduced (either from their earlier work, or from new theorums) a fast and effective way of cracking keys, this could raise more than a few eyebrows. Depending on how general it was (the earlier published results applied to any algorithm with any key-length), this could mincemeat e-commerce and cause havoc with commercially sensitive Internet traffic.
I -suspect- that it'll turn out that it's 12us PER KEY CHECKED, rather than to actually crack the code, UNLESS they've found an effective means of factorising primes. Given they need the "quantum computer" element, I suspect it's more the former. Even so, a massively parallel quantum computer testing keys in parallel would slice through keys like a hot knife. Given that nobody has built a "quantum computer" (at least, in the accepted sense), it seems likely this is a theoretical result, rather than an actual one.
There is another possible translation, though - that the "quantum computer" stuff was an aside that the institute threw in and the journalist picked up on as central. Journalists tend not to let the facts get in the way of a good story. This suggests that there's a high-speed computer, capable of a high key-rate, in Israel. No great surprise, there. Hardly qualifies as news, unless it exploits some fundamental weakness in the algorithm or can factorise primes at a high rate.
Re:Prove it (Score:1)
-
Re:wtf!? (Score:1)
NOT TRUE! (Score:1)
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... )
Even if it dosn't work now... (Score:1)
Re:hmm, >554 bit key still safe? (Score:1)
If you have enought "particles" you can crack any kind of encryption? Then, how can a quantum cryptography system be more secure? just curious, i m a lost here..
---
i want prove (Score:1)
char *stupidsig = "this is my dumb sig";
Re:Confused (Score:1)
> do its job.
*We* have? Are you involved in this? Information please?
Quantum computing, even in a limited form, is going to change the face of the 'net real fast. I know the theoretical work says it could be done this fast, but can these things actually be built already?
The Matrix is going down for reboot now!
Stopping reality: OK
Troubles With Banking... (Score:2)
The Internet is only the latest place where cryptographic systems are being used to implement security; DES has been used for years to secure ATMs, and the present availability of DES-cracking schemes establishes that that is undercut by available technologies.
If "quantum computing" were to undercut Internet-based crypto schemes, it would undercut all of the presently constituted cryptographic distributed banking protocols, which would be Quite A Bad Thing, irrespective of your rejoicing or lack thereof...
Re:Put into perspective (Score:1)
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
Simple way to defeat this (Score:2)
:)
Re:wtf!? (Score:1)
WTF would of course be watts * teslas * farads.
Cheers -- ewd
"Only entropy comes easy." -Lewis Mumford
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:i want prove (Score:1)
three words (Score:1)
grep Need To Know, 1st October 1999 [ntk.net] for quantum.
Re:This requires some thought (Score:1)
>some fundamental weakness in the algorithm or
>can factorise primes at a high rate.
Hell, if they can factorise primes at any rate, i'd say that constitutes a major breakthrough. Public Key cryptography relies on factoring large numbers, commonly the products of 2 primes. This is a possible task. Factoring a prime number is an impossible task.
Assumption? (Score:1)
Or is that physically impossible....
what about elleptic encryption? (Score:1)
How do you go about brute-forcing elliptic encryption, and is it similar to brute-forcing RSA? could this RSA-killing device be adapted to do EE?
just curious. i have very little idea of how elliptic encryption works, or how it's broken. Can anyone explain for me?
Possibly... (Score:1)
Since we haven't proven P!=NP, & encryption algorithms may hold intentional or unintentional backdoors that the Net may pick up on & train itself against, NNs may be useful after all. I remember reading in Applied Crypto that the NSA's tweaks to the DES algorithm resulted in much more linear transformations being applied. Smaller Nets can easily pick up on linearly separable data, & this was my 2nd flash of insight into thinking that the Crypto & NN communities ought to do lunch sometime.
If you're really interested in this topic look into "Brain-state-in-a-box" nets. Warning: be prepared to think in n-dimensional space, where n is the number of bits in the key...
European Banking System??? (Score:1)
Re:Not even (Score:1)
Slight side issue - Quantum Encription. (Score:1)
/BEGIN/
The second aspect of Quantum computing, however, will help to make information more secure. Using a feature called "quantum entanglement", information could be sent between two computers that could not be eavesdropped upon without the two computers' knowledge. Because quantum physics dictates that monitoring a subatomic particle changes its state; not only would an eavesdropper announce his presence, but the message would be garbled.
/END/
As I read this, they are implying that this would be some kind of unbreakable One-Read-Only type of information stream. Anyone snooping the information would invariably change the information, and thus be instantly detected.
Ok, so we break the Data Streem hard, and once we capture the incoming data, we then re-encode and spoof it to the intended receiver?
"'A hacker wouldn't know where to start,' says Jonathan Curtis of Quantum Electronic Devices."
I guess that means I'm not a hacker then.
Nipok Nek
Re:Assumption? (Score:1)
Re:LOL :) (Score:1)
> Then it would either be debunked or denied. I very much doubt it exists....
So are you the one who wisked away the team and reporter?
--
It's October 6th. Where's W2K? Over the horizon again, eh?
almost superluminal (Score:1)
Calculations: Result? Physically impossible (Score:2)
So, assuming they spent a billion dollars making this 1 chip, they're still getting a 1e144 times better buy on computing power than modern day computers. Excuse me while I cast "Disbelieve" on this article
Not to mention the physical impossibilities involved (such as, our favorite, the speed of light versus the smallest pathways we can make)
Honestly, if we had a chip with a 144 orders of magnitude better performance than today's computers, there is no way it would only be mentioned in an article on encryption. There would be hundreds of companies competing for the rights; the net would be flooded with places trying to get this chip to the market. 144 orders of magnitude! a computer that costs a penny being more powerful than the most powerful supercomputers in the world! think about this.
Don't believe what you read.
- Rei
Not very believable (Score:2)
The sotry doesn't seem very believable. The most recent reports were of quantum computers able to factor the number 4. Although breakthroughs happen, I doubt that any breakthrough of this magnitude happened. It's sort of like someone suddenly building a pentium III when everyone else was building 8088 or m68ks. In addition the lack of details make the story pretty suspect.
Ummmm, no (Score:1)
I agree that these export regulations are silly. However, This israeli project is just theory thus far.
Unreliable source (Score:1)
The 'Hitler Diaries' were a different case altogether, the decision to publish them was allegedly taken by Rupert Murdoch himself - even though they were considered possible forgeries.
If they *were* faked, Lord Dacre could be - and was - blamed. Either way, it sold papers.
Re:Does Not Feel Believable... (Score:1)
Nobody uses RSA to encode the message. Everybody uses RSA to encode a standard "symmetric" key. That decodes the actual message.
The RSA challanges aren't even encoded messages. Just bunch of large numbers, that are a multiple of two primes. If you can factor those, you know you can crack RSA.
Roger.
Not so black and white. (Score:1)
The relationship between the US gov't and the Israeli gov't isn't that black and white. Its more complex than that. I certainly wouldn't count on the Israelis to willingly share the technology with the US unless they NEEDED the US gov't to develop this thing.
Also, according to the article this machine is just theory, a working model has yet to have been built. I wouldn't be the least bit suprised of US firms are well ahead of them.
One thing many people fail to realize is that there is more money in the consumer market than there is government. So baring any government regulations preventing them from disclosing or patenting this technology, or cost issues (eg: such a machine can only be built for ~500K minimum); an astute person would approach the private sector first.
Re:This requires some thought (Score:1)
Factoring the product of two LARGE primes before the Universe decays into thermal radiation is slightly more complicated and requires either Orac (unless he's busy taking a close-up look at a Black Hole :), or an as-yet unknown (at least to the public) algorithm which can either generate primes faster than currently possible, or determine the factors directly, by some currently unknown means.
Re:Neural Nets and Crypto (Score:1)
You can pick apart my paper at http://www.erols.com/mkatshym/Ex tendedEssay.ps.bz2 [erols.com].
Michael Katz-Hyman
mkatshym@erols.com
Re:wtf!? (Score:1)
Re:Not very believable (Score:1)
--------
"I already have all the latest software."
Re:No Way. (Score:2)
The real question is what sorts of lengths you can generate. Currently, I think they have constructed 5 bit quantum computers (anybody care to enlighten me?), but have yet to apporoach the 512 bit length needed for serious factorization.
IIRC, the TWINKLE device they mentioned here is a *theorectical* device that generates numbers that have a good chance being prime factors of the RSA key in question. A real (a.k.a. normal) computer then checks these numbers in hopes of stumbling accross the solution.
I think the Times has confused a paper with something that exists. After all, why would you tell banks you can crack their encryption when you could create some accounts for yourself? : )
This is a complete sham (Score:1)
I would upgrade my 512bit keys to at least 1024 if not 2048bits but I wouldn't worry about this.
Re:Confused (Score:1)
---
Here are some reasons why you should doubt this (Score:1)
--Ever heard of them, no.
--Here is the real info:
The institute was founded a few weeks after news leaked from the Israel's Weizmann Institute that it was using a mixture of quantum computing and special optical technology to break the RSA-512 code, the system used by the European banking system. It claims it has developed a hand-held device that can break the code in 12 microseconds.
2) Those of you on cryptography@c2.net know about Shamir.
--Shamir (the S in RSA) theorized something called TWINKLE, the 'special optical technology' that the institute is referring to is very similar to TWINKLE.
As Keith Dawson writes about the article in the times, "Is there any truth to this?" -- my answer, yeah, it is called recycled PR.
-Davidu
Oh my God, they killed RSA! (Score:1)
Beer recipe: free! #Source
Cold pints: $2 #Product
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:Calculations: Result? Physically impossible (Score:2)
The contest you're thinking of is a very different one than attacks on RSA -- it is probably the RC5-56 factoring challenge, which was tackled early in the life of distributed.net. The algorithms are very different; RSA is public-key, or asymmetric, cryptography, while RC5 (like DES) is a private-key, or symmetric, algorithm. These are very different families of algorithms.
Just as the algorithms are very different, key lengths simply can NOT be compared between the two. Most public-key cryptosystems rely on the difficulty of factoring large primes; private-key cryptosystems work on a variety of principles, but many current private-key cryptosystems are based on Feistel networks (for the curious, references in the literature are plentiful). In any case, private-key cryptosystems can generally use any integer as a key -- while a public-key system must select from a much sparser space (roughly, the set of primes; the integer n has approximately a 1 in n chance of being a prime).
RSA-512 has been attacked and solved before (see http://www.rsasecurity.com/rsalabs/factoring/rsa1
Re:Stop spreading misinformation (Score:2)
On another note, I would guess the article left out a small detail, the optical machine they were working on solved the second half of the seive, the half they used a Cray on in the earlier story. The pre calculations needed to setup the problem in terms the optical machine can handle took a few months of spare cpu cycles from some small amount of computers (under a 100 as i recall?). If they have discovered how to reduce that to near constant time then this would probably be the end of RSA type algorithms. There are still quite a few public key algorithms out there, so we might still have to wait for the quantum computers to come out before public key crypto is dead.
Thanks for correcting that 2^n comment, it was might have misled alot of people.
Caveats on this comment as well: complexity given above is ASYMPTOTIC. It has (logically) nothing whatsoever to do with any finite n, or set of n. It says nothing about them. Specifcally the running time says nothing about the relationship between 512bit and 2048bit factoring. However it is standard practice to assume that it does, and this practice (while not grounded in rigorous proof) tends to work out.
Re:Put into perspective (Score:2)
It is. Given a proposed solution (i.e., a factorization) it is trivially verifiable in polynomial time, regardless of which of any number of reasonable modern computational models you wish to use.
2) That NP != P
Granted, since otherwise the problem is bounded by a polynomial.
3) That we live in a P world
How very technical of you. What is that supposed to mean?
If what you are trying to arrive at are sufficient conditions for a lower-bound on the complexity of integer factorization you are likely wasting your time. If I remember correctly it is known that Factorization is in the intersection of NP and co-NP (someone correct me if I've forgotten), but it has not been shown NP-complete (and is thought not to be).
But this says little about time required to solve (lower bounds) which are a more difficult matter all together. Depending upon your computational model it may be a trivial problem (consider the model where a machine can perform factorizations in one step -- then this is a constant-time problem). The point being that some magical computational system (here everyone reads "quantum computing", but it could be any magic-like technology -- and preferably less like vaporware in my opinion) or algorithmic revelation may reduce the problem quickly to tractability.
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.
Re:Stop spreading misinformation (Score:2)
"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))."
For large n, (log log n)^(2/3) is less than (log n)^(2/3) so it seems as though
c (log n)^(1/3) (log log n)^(2/3) is less than c (log n)^(1/3) * (log n)^(2/3) which is c log n.
Hence exp(c (log n)^(1/3) (log log n)^(2/3)) is less than exp( c log n) = n^c. This implies factorization is polynomial.
Am I missing something? Actually your parentheses aren't balanced so I may have misinterpreted by assuming a missing right paren at the end.
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.
I'l believe it when I see it. (Score:2)
Ok first off, this is just a claim. One that is absolutely unverified. You tell me, why would they be so quiet about this thing? Why make a claim about being able to crack RSA, but not actually do it? Why crack RSA? There are so many larger things they could do which would garner more attention.
Secondly, this is just a claim, a second hand one at that. They never even stated that they "HAVE" cracked RSA, they said they could.
The word "could" can be interpreted many different ways. Could can be: They've created a working proof of concept, and this technology could crack RSA, they think, in X microseconds (2 billion dollars and 10 years later). And a few thousand variations thereof.
This whole story, or atleast the way its being interpreted just doesn't compute. So I repeat, I'll believe it when I see it. Care to wager that they won't have a single 512bit RSA actually cracked within a year with this technology (let alone in X seconds)?
There's nothing special about DNA computers (Score:2)
The most interesting aspect to DNA computing is that it employs the physical/chemical properties of molecules to structure a problem solver.
But the only real advantage is that these problem solvers are small and cheap, so you can apply a great many of them to the problem.
The overall computation is still naive brute force. In fact, it's not even coordinated (across all the "computation units").
The only reason it's of interest is simply because you can create such a lot of very small computers each trying one step of a brute force search...they still have to do (on the order of) the same number of steps as a program on a single processor machine.
Now I don't care how small you think a molecule is, you'll need a bloody big test tube to search a 512-bit key space.
Defining the significance of NP-complete problems to lay-people often involves showing them how for very small problem sets *there aren't enough atoms in the universe* to solve it.
DNA computing has nothing what-so-ever to do with quantum computing.
Re: Bible Code (Score:2)
"'It was the best of times, it was the blurst of times?' Stupid monkey!"
All roads lead to The Simpsons
That's too bad. (Score:2)
Joseph Elwell.