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?
Good thing that only Americans are able to do things with cryptography. I mean, if we were allowed to export our expertise, those _foreigners_ would be able to... hey, wait a mintue...
Can your IM do this?
all i have to say is: 12usecs!?
All I can say is where's the quantum VDHL code.
The message on the other side of this sig is false.
The Sunday Times also broke the 'Hitler Diaries' as a news story. We definitely need independent corroboration, plus an explanation of how this particular piece of kit might do its job in 12us.
It should be 12us, not 12uS. Seconds is designated with a small S.
So do we or don't we have a quantum computer right now? If we don't have one, as the article mentions, then what on earth is this Israeli handheld device?
Just when I've started rejoicing over being able to pay my bills via the Internet, we get this thrown at us....
.02$
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
Maybe it runs the decryption algorithm in 12 microseconds, but I don't see how it would crack a 512 bit key in that amount of time.
if you believe this I have the USS Enterprise parked in my garage, want it?
I'm a loner Dottie, a Rebel.
I wanna see hardware/software specs and some code.
I *really* think this is a hoax of the highest order.
But hey, that's just me.
aÍÍ©ÍÌÍ£Ì'̽ͩÌÍzÍYÌÍÌY
This means they are able to factorize large prime numbers. If the principle they use is a general one, (not closely tied with the size of 512 bits), then this is very troubling news. However, I think this is a phony. Presented like this without reference to teqniques used (other than "quantum computing" and "optical computing" there is still no reason to worry. So what about my 2048 bit RSA key? Will they be able to crack that as well? They are welcome to try!
Opinions expressed above are mine, and not my employees'.
I am willing to bet that the London Times read about Adi Shamir's TWINKLE concept computer and somehow thought it had already been done.
They tend to do that.
This may possibly be offsubject, and I don't know much about either, but could you use neural networks to crack Crypto?
The Weizmann institute says it has a device. Yet later in the article a member of the EIQC says that Quantum COmputers are still some ways off.
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.
--------- Beware the dragon, for you are crunchy and good with ketchup.
Now suppose that this is real.. and suppose that someone in israel has managed to put together quantum logic gates enough to crack 512bit encryption(last time I heard someone had a single nand-gate somewhat operational).. now the question being: why reveal it to the world?!? This is worth a lot of money as such.. Someone just leaked it out of the institute? Surely they understand the value of this. Why not sell it to nsa etc(or maybe they have it). They could decrypt most public key encryption at their will and now they go and announce it in SUNDAY TIMES of UK?
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.
Near the end of the article it mentions that quantum computers are still a ways off, yet according to the beginning of the article a handheld quantum computing device has been built in Israel. Both can't be true, so I'll stick with the one that agrees with everything else I've heard: these devices don't exist yet.
get that thing in with distributed.net! i wonder if i can get them to join my team... }:~)
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
icq:=22921393;
from the astounding aspect of it all, that sounds like the best conclusion..
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
Insert mind here.
At that speed it should take more than a year to crack 554 bits keys, so 1024 bits keys should still be safe!
:-))
(why isnt everyone using 1 meg keys anyway?
---
The big question seems to be this: could it be true? Or are the Israelis just pulling Europe's chain?
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?
Yes this is a very interesting read. 12uSecs is damn impressive I have to hand it to them. Even more impressive if you read the "Thermodynamic Limitations" section of Applied Cryptography (see page 157 of the second edition) where he talks about how if you were to build a dyson sphere around the sun you could still only count up to 2^192. So to brute force computers need be made of something other than matter and occupy something other than space. (go read it)
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?
My Slashdot account is old enough to drink...
Hah! Didn't take very long for Need to Know to comment: http://www.ntk.net/
The Weizmann Institute is one of the best research institutes in the world (think MIT-level). Shamir (inventor of Twinkle, co-inventor of RSA, co-inventor of differential cryptoanalysis, etc) worked (still works?) there, as does Eli Biham (differential analysis, related-key analysis, impossible differentials, and Serpent), Goldwasser, sereral others who are very presitious in the crypto community. If this were done anywhere in the world, it would probably be there.
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.
Ok first of all as i understand this "Quantum Computer" is actually some kind of optical computer that uses Quantum theory
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
:))
Those People Who Are Crazy Enough To Think That They Can Change The World Probable Can
Can anyone confirm this leak? The Times doesn't say who or where this leak came from, and the Weizmann Institute doesn't seem to have any information on it, although they do have alot on RSA and public key crypto in general. And I would think any breakthrough like this would be kept under tight wraps, Israel isn't exactly the most open nation when it comes to spy and security stuff like this. Could be a red herring thrown out to make their enemies feel a bit more insecure. I'll believe it when I see it. Maybe. .^ .^
^.
( @ )
^.
No details, scary story, Vague references to cutting edge science.
God does not play dice - Einstein
Not only does God play dice, he sometimes throws them where they
I consider it a wee bit surprising how much ignorance and self assertive a lot of reactions show. Sure, cannot be true. Sure, you all know all about Quantum Mechanics, right ? Gee, what a limited horizon for "nerds".
The article is very strange. Sometimes it speaks in past tense, as though the device has already been developed: "It claims it has developed a hand-held device that can break the code in 12 microseconds." While at other points it speaks as though the device has yet to, but will be developed: "While quantum computers may be some time off, when they are available no communication will be secure unless it is quantum."
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.
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
enough said.
:-)
hmmm I have an ATM machine near my apartment. hmmm
It's important to note that the sunday times is a very unreliable source of information. As well as serialising the Hitler diaries (which isn't quite so bad as they weren't the first or the only ones to be taken in) they've also ran various bizarre campaigns, such as insisting for a long time that AIDS wasn't caused by HIV.
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.
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.
i'm sure that article is just dripping with reality. it seems all happy in theory, but i'm even more sure this computer doesn't exist. or if it did, it only existed for the 12usec that they say it took to crack the 512bit key.
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
It is true that Adi Shamir (The S in RSA)came up with the plans for a device called TWINKLE which could theoretically break 512 bit RSA keys. (1024+ bit keys are still infeasable for the device.) However, it should be pointed out that the device HAS NOT BEEN BUILT. In fact we looked over the plans at my University and decided it was probably impossible to actually work from a purely thermodynamic point of view (the number of LEDs clocked at 10GHz would create more heat than the old ENIAC/EDSAC era computers, but would be as small as a current machine... you would need truely Exotic Cooling to make such a device work. Also it should be noted that public key crypto and symmetric crypto are different, it takes more than one bit to double the break time for public key algos (6-10 bits depending on how you figgure it) Me.
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... )
If you're not part of the solution, you're part of the precipitate.
The idea behind how the system would work is still valid, and if anyone ever does manage to make one, all classical encryption will be pretty much screwed. The technique is called Shor's Algorithm, and it is the number 1 reason that everyone wants a quantum computer (IBM, the NSA, and alots of other countries would LOVE to have one.). Check out: For details on shor's algorithm or the book Explorations in Quantum Computing by William and Clearwater. If you built one you should be able to crack RSA about as fast as you could encrypt with it.
(i dont know anything about quantum computers or encryption but...)
:-)
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..
---
how about they do us a favor and crack rc5-64. just to prove that this thing acutally exists of coarse. And if this thing is real, is there any hope for encryption? is there some type of encryption that a quantum computer takes ages to crack?
char *stupidsig = "this is my dumb sig";
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...
If you're not part of the solution, you're part of the precipitate.
... to this. Instead of speculating, let's look at the primary source:
/.ers.
"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
-- I can't think of anything witty to put here. Sorry.
Just run your encrypted text into a heisenberg compensator which is cross connected into a infinite improbability generator. After this the message still looks the same but the universe will have to be decrypted in order to read it.
:)
Linux is only free if your time has no value. Windows is only free if you threaten to use Linux.
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.
grep Need To Know, 1st October 1999 for quantum.
"None are more hopelessly enslaved than those who falsely believe they are free." -- Goethe
Now if only it was reported on "The Register" http://www.theregister.co.uk/ I would believe it more ;-)
Why do we all have the assumption that brute force is the only way to crack these large keys. Is it possible that they are not using brute force? And instead have devised some method of quickly determining the key _based on the encrypted data_?
Or is that physically impossible....
OFTC: By the community, for the community
so, working on the very shaky assumption that the Sunday Times isn't just talking out of their ass and this device could actually be created, how does this fare for Elliptic Encryption?
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?
Irritable, left-wing and possibly humorous bumper stickers and t-shirts
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...
Apart from the very unlikely fact that the story holds any truth concerning code-breaking - What does the Sunday Times mean when saying "The European Banking System"??? There's more than a dozen of different national systems interconnecting various banks, there are networks between large banks across Europe, there's Eurocheque's network and and and... Get a clue, Sunday Times!!!
If it was true you can bet that the whole research team met with an "accident" or vanished shortly after it was published along with the reporter and anyone else remotely intrested in it. Then it would either be debunked or denied. I very much doubt it exists (least publically). AFAIR the problem is not breaking the encryption using a Qmachine but actually getting the answer out of the machine.
What? Memphis was in Egypt, not Greece.
From the article...
:)
/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
Why choose white shoes?
I am so pissed. They cracked it without using a Beowulf cluster? IMHO cracking it with a beowulf cluster would surely have been a superior solution. Or at least the results would have been more accurate. Beowulf clusters are getting very popular even in kindergartens these days. And there are rumors at VA that even Santa has ordered one to handle the load before chistmas.
This is superluminal in a classical physics calculation. It would have to be a real small area the electrons and/or photons are interacting in since the speed of light is a limiting facter. If this isn't disinf then physics just changed for me.
The previous record for a privately held single machine on RSA 56 bit was 3 days with a 250,000$ machine. This comes out to, assuming technology is linearly scalable for money, 5.4e15$ (5,400,000,000,000,000$) (5.4 quadrillion dollars). Now, to scale this to 512 bit encryption, each extra bit is a power of 2 more possibilities, so this is 2^456 times the possibilies, resulting in a ~1e153$ machine (1,000,000,000,000,000,000,000,000,000,000,000,000 ,000,000,000,000,000,000,000,000,000,000 ,000,000,000,000,000,000,000,000,000,000,000,000,0 00,000,000,000,000,000,000,000,000,000,0 00,000,000,000,000,000,000$) (no name for this number) ;)
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
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.
"When you sit with a nice girl for two hours, it seems like two minutes. When you sit on a hot stove for two minutes, it
I agree that these export regulations are silly. However, This israeli project is just theory thus far.
The Sunday Times is not very good at checking it's sources. This story looks impressive but there is no guarantee they have the remotest idea of what they are talking about.
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.
Mielipiteet omiani - Opinions personal, facts suspect.
I wonder how long until gateway ships these quantium computers? Does anyone know how many FPS I will get in quake with these new things? They sound pretty fast. BTW, if I do get one of these quantium computers can any one suggest a good APG video card to use attach to it? Also is anyone working on the Linux port? I bet those microsoft dudes are working on a WinDoz 2001 port for it.... we need to get cracking!
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.
I would upgrade my 512bit keys to at least 1024 if not 2048bits but I wouldn't worry about this.
1)European Institute of Quantum Computing Network
:)
--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
# Hack the planet, it's important.
You bastards!
Beer recipe: free! #Source
Cold pints: $2 #Product
While state-of-the-art improvements such as the number field sieve obscure the details, the basic quadratic sieve is not hard to understand. One way to factor n = s * t is to find two numbers x and y whose squares are equal. x*x == y*y (mod n) implies that x == +/- y (mod s) and x == +/-y (mod t). Half the time, the individual +/- choices are the same, so x == +/- y (mod n), which is not very informative. But the other half, x == +y (mod s) and x == -y (mod t), so x+y is a multiple of s but not a multiple of t, so t = GCD(x+y, n) is easily computed.
To find those numbers x and y, the quadratic sieve steps through possible x values, and tries to factor x*x (mod n). If you're lucky, its factors are all small primes less than some bound B, and the factorization produces one row in that giant matrix to be solved, called a relation.
Choosing the correct bound B is very tricky. The higher it is, the faster you will find relations, but it also determines the number of columns in your matrix, and you need as many rows (relations) as you have columns.
To do the search efficiently, you set up a sieve (does anybody remember the sieve of Eratosthenes?) with slots for a great many possible values x, then, for each prime p less than B, it turns out that there is a simple repeating pattern (two numbers out of every p values) of which values of x*x mod n are divisible by p. So you multiply the slot by the prime p for every applicable slot, and when you're done with all the primes p, look for slots whose values are high enough to be a relation.
Now, multiplying 512-bit numbers are slow, so actually, you use logarithms. For each slot, you add log(p) and see if the result exceeds log(x*x mod n). Furthermore, you use a rough approximation (like 32 bits long) and double-check any accumulators that get close enough.
An important thing to note is that it is fairly easy to double-check results, so an approximation is adequate, as long as the number of false hits doesn't get too high. Also, missing a few relations is fine, if it helps the search rate enough to increase the number of relations that you do find.
TWINKLE basically automates this process using optics. The design uses a whole gallium arsenide wafer studded with LEDs (one per prime p), each with a filter that adjusts its intensity to be proportional to log(p). The trick to making it work is to not worry about making the filter perfect, but to measure the intensity of the LEDs and then assign them to primes accordingly. Each one is programmed to blink on at the appropriate times in a pattern of length p.
Anyway, you aim all the LEDs at a photosensor, clock the whole thing at 10 GHz and record whenever the intensity exceeds log(x*x). The receiver circuitry is tricky, but 10 Gbps fiber-optic receivers exist.
The paper is available as a postscript file in http://jya.com/twinkle.zip. Bob Silverman wrote up an overview at http://www.rsa.com/rsalabs/html/twinkl e.html .
Now suppose these Israelies really did it. Why on earth would their first prototype be a handheld device? When you develop a prototype you usually don't care about the size, you optimize that later.
That's why they're so spiffy, in a nutshell. There's an interesting article (referenced on Slashdot, ironically enough) describing Quantum Crypto.
--
Ben Kosse
Remember Ed Curry!
Yup,
"We've got a portable device that'll break 512 bit RSA in Microseconds"
Yup, just theory.
-- The act of censorship is always worse than whatever is being censored. Always.
How do you break the data "streem?" You see, if you even *READ* the data stream, Bob knows you've intercepted it and Alice can send it again.
This says nothing regarding making Alice believe that YOU are Bob (man in the middle), and it still necessitates some sort of authentication. IOW, if Alice thinks you're Bob and Bob thinks you're Alice, you still have problems, but there's no cyphering that you can do to fix that.
What I find interesting is that no one's mentioned some sort of quantum authentication yet. That kinda worries me, since at least half the point of public key cryptography is to prove you are who you say you are.
--
Ben Kosse
Remember Ed Curry!
My Netscape keeps on crashing after taking 20 minutes to load this page.(From U.S.) Sabotage? Is there a need? Anybody else experience this?
Fair warning from a kinder-nicer Rupert. Take a look over your shoulders boys
What's the name of your bank this week?
(from this page)
It's 12 s.
Hands in my pocket
The "Bible Code" isn't cryptography. Well, not cryptography by mere mortals.
/. always strip leading spaces, even when us silly posters use 'pre' tags? Anyway...
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.
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
They used a diffrent kind of technology, in thory. Quantum tehcnology can be used to calculate diffrent things at the same time. each bit (I belive this is correct) can be tested in both on and off. So you could test *every* key, in the amount of time that the EEF's technology took to crack one.
"Subtle mind control? Why do all these HTML buttons say 'Submit' ?"
ReadThe ReflectionEngine, a cyberpunk style n
The article says only that this device has been designed, not that it has been built. The article says only that the device is capable of doing quick code breaking, not that code breaking has been done this fast. The article is very misleading, but not actually incorrect.
If it did that key in just 12 microseconds, how come they didnt try and crack RC5-64? Now, THAT would prove it pretty damn fast :))
Not exactly. Essentially, a quantum computer of 8 bits can do an operation on all of the possible variations, i.e. 0->255. To expand this, a 56 bit quantum computer could go through all the variations of a 56 bit key in one pass.
Why the arbitrary number 8? quantum computers can superimpose data on any bit (or qubit, or whatever). for 8 bits, you would need 8 qubits, for 512, you would need 512. The dificulty would be building a bus with 512 bit depth, so it would be more exspenisve, esp with current technology.
"Subtle mind control? Why do all these HTML buttons say 'Submit' ?"
ReadThe ReflectionEngine, a cyberpunk style n
I don't see why, the laws governing planitary motion are based on gravity. since it is in a non inertial frame of refrence, the equasions don't need to change, regardless of the center of the Univerce.
"Subtle mind control? Why do all these HTML buttons say 'Submit' ?"
ReadThe ReflectionEngine, a cyberpunk style n
factors of 29: 29 and one.
:)
Hell, I can even factor 31337
"Subtle mind control? Why do all these HTML buttons say 'Submit' ?"
ReadThe ReflectionEngine, a cyberpunk style n
There seem to be two issues in this article (both of which seem completely suspect)
- can the RSA be broken effeciently?
- and can these people really build a quantum computer with this kind of power? (handheld, no less)
Mabe one of these is true. The first one is a
little bit more believable. But _both_ at the same
time from the same institute?
Nah.
heh, there is one simple reason 1/2 of those bible code books are no good: THE LANGUAGE!
the torah was given to the hebrews in hebrew!
listing letters and playing with them in english is NOTHING... it has no relation to what was given, and is therefore random...
now, if the analysis were done in hebrew...
Talk is cheap - show the math. Is this the new terrorism? "We can break the European banking encryption in 12 microsec.s so better kiss our ass?"
I don't buy it, not even in Euro's.
Large or small it doesn't matter. That's what a prime is
If this is true it would be a huge breakthrough for the computing field. Why does the story give so few details. I'm going to wait to see what Bruce Schneier says about it in his newsletter (if he even says anything).
While I'm at it, people, please learn the difference between symmetric and public key systems and bits and bytes. You look quite silly if you don't. Bruce's site (or book) is a good place to start looking for a clue.
Do I smell? I smell home cooking
It's only the river, it's only the river.
Clearly a different encryption method is required; likely it will require the encryption and decryption computers to be quantum.
Ok, I might be mentioning some things that people already said but here are a few things that popped into my mind upon reading the article in The Times:
1) Most of the comments I have read all talk about the fact that quantum is bulky and too big to fit into a handheld device, while I am not disputing this, because I don't know to much about quantum computing, the article never mentions anything about the handheld device being quantum. It says: "mixture of quantum computing and special optical technology" which to me reads like it could be a ton of different machines, and not all the proccessing was done inside the handheld device.
2) "As one member of EIQC, who wished to remain anonymous, predicts: "While quantum computers may be some time off" This quote right here is very misleading to me. A member of EIQC said this, but the EIQC had nothing to do with this device. This device was developed by the Israelis, not the EIQC, and I am not even sure if Israel is even a member of the EIQC.
Any help with this would be much appreciated.
--Patryn
US Gov't just 'relaxed' crypto rules... think a gift from their strategic Mid East partners made them feel easy about this decision? FWIW, the crypto export issue is, and has always been, a liberal dose of red herring, a neccessary distraction from the Real Issues. What are they, you might ask? Try the high-volume mutual call monitoring system Echelon, for one, not to mention the steady legislative erosion of US domestic telecom privacy rights. Check the fine print of the most recent telecom bill. Think the US is really interested in ciphered traffic between hackish types? Maybe for amusment purposes, but that's not the big ticket, baby.
Big Daddy, Johnny, Burp, Aunt Zelda, Scott, Slurp, Big Momma
Well, it actually exists 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.
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)?
>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.
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.
It was done in hewbrew.
well, although i agree that the guy to whom you are replying doesn't have a clue... as far as i understand, there is no way in general to "try every key at the same time". i feel that it is more likely there is some more specific algorithm that is able to factor numbers or something like that.
for example, it is not the case that every NP complete problem can be solved (in polynomial time) by a quantum computer (yet!).
-sh_mmer
Interested in learning Chinese or Japanese? check out Chinese/Japanese-English Dictiona
12 us is very short -- 6000 cycles on a 500 MHz machine. It would be a nice trick if you could _decode_ 512 bit RSA given the two factors that fast.
Maybe that's what they've done. Cracking RSA would take a _massively_ parallel effort or unheard of clock rates. But electrons shifting orbits does take finite time, and so do nuclear
reactions (measured in "shakes" 10^-14s IIRC).
-- Robert
But that is somewhat questionable. I thought this technology wasnt exactly ready yet.
Juln
Factoring 512-bit rsa is known to be doable,
.... ;-)
and has been done in public before (recently,
I think).
Using quantum computing to implement massive
parallelism is also possible, at least in theory.
If these guys are for real, then 1024-bit
RSA may also be vulnerable, and in fact larger
keys which are feasible to calculate on a
conventional computer may also break soon.
So... the bottom line is that either this is
a hoax, or else it's not only plausible, but
actually true, in which case the computer security
world is about to be turned on its head!
Interesting times
-- Idan
Quantum encryption defeats the man-in-the-middle attack . How it does so is a question that requires you to do a little bit of research . Sorry but you are still thinking like a Newtonian . :P Your Squire Squireson squireson@bigfoot.com
Aranov-Bohm experiment ( sp? ) showed that the wave nature of a particle is botha real thing ( not merely a mathematical construct ) and that it
carries information at an infinite speed . Einstein and contemporaries reffered to it as a "spooky action at a distance " .
The information can therefore be carried instananeously between the different particles .
Einstein was wrong about a great many things .
We have yet to reconcile relativity with quantum mechanics .
Your Squire
Squireson
There's no reason for a sig here.
"'It was the best of times, it was the blurst of times?' Stupid monkey!"
All roads lead to The Simpsons
-- This and all my posts are in the public domain. I am a lawyer. I am not your lawyer, and this is not legal advice.
but I thought that with a quantum computer it didn't matter what the length of the key was since it checks all the possible combinations at once. maybe it takes the exact same time to crack a 512 bit key as a 1024 bit key.
Maybe this is why export restrictions are relaxed now, since the NSA/FBI can now crack anything /anywhere.
Now the trick is , to not define new encryption, but to hide the data you wish to transmit in normal data so as not to initiate a 'crack attempt' afterall, if the dont know you have a hidden message they wont attemt to crack it. This is going to be the new art in future, HIDING INFORMATION, not wierdo encryption 58945984958bites with 8174th primes. Get original.
What a clever man that God person must be. Dictates the Bible exactly in such a way that the version that was translated into English (we may have to change our perception of who the chosen people are...) and edited by King James, comes out with the ultimate truths. (If you just look at the *right* bits, that is)
Amazing.
regarding NP complete problems you are correct because there are no quantum computers yet (known). If a so-called quantum computer existed and it could solve an NP complete problem in polynomial time then by defination it could solve every one of them. The normal defination (with only 1 exception) of an NP complete problem is to formally prove that to solve the proposed NP complete problem is equivalent to solving an existing NP complete problem. Therefore any NP complete solution will solve the whole class of (formally proven) NP complete problems. Note that some problems are refered to being NP complete without any formal proof, i.e. the 'Natural Language' problem. -Duncan
Duncan Watson
No, the translation loses all the codes. The only way to get them is to use hebrew words in the original hebrew manuscript.
Btw, they tried this with other documents including all the works of Shakespear, the bible rearranged, the bible backwards, etc and they didn't get nearly the same results (I think they tried 1M documents and none worked)
This was published in a statistic journal (not sure which).
Cheers,
Allen
to reply: 3->e
"DNA is God's contribution to the Open Source movement"
Ok, let's go scientific... They mention optics and quantum stuff, which probably means, that they are using photons as information carriers. Now the photons are "wave packets" with corresponding wavelength/frequency. The frequency of visible light is approximately 10^15 Hz (cycles per second), and the corresponding wave period is proportional to 10^(-15) sec. Thus in 12 usec one can radiate something like 12*10^(-6)/10^(-15)=12*10^9 (12 billions) periods of wave corresponding to visible light. Even if they are not using visible light, this will correct the number only by 1 or 2 orders of magnitude (one should also keep in mind, that photon is not exactly one period of the wave but rather a wave packet. Conclusion: something is definitely wrong here, because it should be pretty damned hard to crack 512 bits key, having only 12 billion information carriers in posession ;-). Just my $0.02
Here we go (thanks to NTK Hard News 01-10-99):
Okay, so it's easy to knock TIMES INTERFACE, but surely we can't have been the only ones who read their piece this week that claimed, almost in passing, that Israel's WEIZMANN INSTITUTE have built a "hand-held" quantum computing cracker that can break RSA-512 in less than a second. Woah. Let's just take a second to let that sink in. According to the Times' unquotable sources, that means strong crypto is a solved problem. Of course we're sceptical: sounds like the spooks have, in their excitement, heard about Shamir's TWINKLE prototype, got their photons tangled, and think they've found the holy grail: a quantum computing solution for *all* bit sizes. Perhaps the question is not, how the hell did this happen, but why are the spooks spreading this story now? Maybe they don't realise that the protection against TWINKLE is to just up the bit size a little bit?
Hmmm. Yes. Quite.
--Nick
I agree with your stuff about NP-completness. But (extremely simple) quantum computers have been built, and have run real algos. Read about it here http://cryptome.org/qc-grover.htm (stolen from another post on /.). Makes great reading for people like me who have never dared go into the realm of quantum computing (being a computer scientist but not a quantum physicist!).
no comments
This is going to be the new art in future, HIDING INFORMATION
Actually, its a really old art. It's called STEGANOGRAPHY. I think it is named after some ancient greek (Steganos?) -- probably a general.
Mulder's masking tape cross signal is a good example. The sender and receiver must be the only people to know about the message for it to be secure.
You can already get programs (I think SCRAMDISK is one - haven't used it) that hide text inside images. Unless this approach is combined with some more conventional form of cryptography (involving a key) the only security is afforded by nobody knowing which images contain the messages.
+++++
+++++
The harder you look the less you see. That's what we're up against.
Rather often, cryptographers and even more often journalists want small cool looking numbers.
:)
The solution is simple: do precomputation. Then apply an algorithm that's blazingly fast. Of course, that's often cheating, but...
In this case, assuming that they are using the TWINKLE device, there might have been a confusion between the time needed for the device to produce linear relations (but which should be much more than 12us anyway) and the time needed to actually factor the number with the Gaussian elimination step of the Number Field Sieve.
However, my guess would be that it is at best a theoretical model and at worst a hoax. Three days, or even one week would already put down the world economy at once, so 12us...
Can someone moderate down this Beowulf crap ? I mean , must we read it in every slashdot story ? I am stein , the one who will never give you his personal data , just because YOU think he should. home at http://surf.to/stein
Hmmm... anyone bother to do this with two languages of Torah and actually notice what does and doesn't coincide?
I would be quite impressed if G-d actually managed to not only embed messages in the original Scriptures, but also make his creation evolve languages in such a way that any translation of the Torah can be found to have the same messages in the same places, albeit in different languages.
Does anyone ever *think* when they try to analyze the mind of something so much higher than themselves?
mindslip
two things i'd like to append to that:
there are no periods the way it's
thrown into their search program.
they basicly enter it in all as one
big line.
they also said that books such as
war and peace didn't return any
relevant results.
many skeptics said they
found lots of ludicrous stuff,
but they were using the english
versions, not formatted the "correct"
way.
but now that i've finished playing
devil's advocate (*groans @ pun*)
also i should point out that the
origional non-translated versions
they are using contain no vowels,
so 'hitler kills europe' would look more
like "htlr klls rp"
pfft.
-adam
javanet.com/~user
um, actually it is done in the hebrew version, and all in one big long line, the way some passage instructs that you're supposed to.
i'm not validating it, just trying to state the facts...
-adam
javanet.com/~user
is why you'll always be a page 3 girl, and never allowed to write an article again :)
[duck]
See what Need To Know said about this article... last week. The established opinion seems to be that The Sunday Times got TWINKLE mixed up with other stuff in their foggy heads and is now talking out of their ass.
[
I neglected to read the original article. I just thought it was confirmation that one was completed. I was surprised no SlashDot readers were familiar with at least the concept or remember reading it on slashdot before (search using the word twinkle). I originally read about it in an article from the Volume 155, Number 23 (June 5, 1999) issue of Science News. There is a paper Written by Adi Shamir from the Weizmann Institute of Science (which is in Israel) about the device. I wrote an e-mail to Adi Shamir but I haven't gotten a response. Here Is the Abstract of the paper for those that don't want to dl the paper.
Abstract The current record in factoring large RSA keys is the factorization of a 465 bit (140 digit) number achieved in February 1999 by running the Number Field Sieve on hundreds of workstations for several months. This paper describes a novel factoring technique which is several orders of magnitude more efficient. It is based on a very simple and held optoelectronic device which can analyse 100,000,000 large integers, and determine in less than 10 milliseconds which ones factor completely over a prime base consisting of the first 200,000 prime numbers. The new technique can increase the size of factorable numbers by 100 to 200 bits, and in particular can make 512 bit RSA keys (which protect 95% of today's E-commerce on the Internet) very vulnerable
I neglected to read this article until this morning. I just thought it was confirmation that one was completed. I was surprised no SlashDot readers were familiar with at least the concept or remember reading it on slashdot before (search using the word twinkle). I originally read about it in an article from the Volume 155, Number 23 (June 5, 1999) issue of Science News. There is a paper Written by Adi Shamir from the Weizmann Institute of Science (which is in Israel) about the device. I wrote an e-mail to Adi Shamir but I haven't gotten a response. Here Is the Abstract of the paper for those that don't want to dl the paper.
Abstract The current record in factoring large RSA keys is the factorization of a 465 bit (140 digit) number achieved in February 1999 by running the Number Field Sieve on hundreds of workstations for several months. This paper describes a novel factoring technique which is several orders of magnitude more efficient. It is based on a very simple and held optoelectronic device which can analyse 100,000,000 large integers, and determine in less than 10 milliseconds which ones factor completely over a prime base consisting of the first 200,000 prime numbers. The new technique can increase the size of factorable numbers by 100 to 200 bits, and in particular can make 512 bit RSA keys (which protect 95% of today's E-commerce on the Internet) very vulnerable
Unless I'm mistaken (it could happen), a quantum computer could break a key of any length in constant time, up to the number of qubits that it is able to maintain. That last part is the important disclaimer, since making qubits behave correctly (i.e., making them collapse correctly and not prematurely) is really hard, and gets harder the more you try to use.
Last I heard (and I don't claim to be at all up-to-date), getting a quantum computer to maintain 4 qubits, so as to factor 15 into 3 and 5, would be considered quite a feat. A 512-qubit computer would work on the same principles, and would factor 512-bit numbers just as quickly as it would factor 15, but I'm as skeptical as everyone else as to whether they've managed to construct such a thing.
Even if they have, it doesn't follow that larger keys are vulnerable: even if they managed the amazing feat of building a 512-qubit quantum computer, it still wouldn't be able to factor numbers larger than 512 bits. Breaking a four-kilobit keys would require yet another three and a half kilo-qubits, which they don't necessarily have.
On the other hand, making the leap from a couple of qubits to 512 would suggest that they have developed a technique for adding qubits fairly easily, perhaps with polynomial or even linear cost, in which case they would be able to make one with four kilo-qubits, a mega-qubit, or whatever, without exponentially greater effort.
David Gould
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}
-Aug 13: Shamir announces Twinkle
as of now, they're still in place... I think the real point is technology is changing too quickly for "digital certificates" or any encryption-based 'official ID' system to be taken seriously. Meanwhile, most people are uninformed. They think "SSL" means secure, and see this as a complicated black box.-Aug 26: Panel suggests getting rid of export restrictions. href="http://cryptome.org/LIB42.htm">here.
-Sept. 14: Clinton announces restrictions will be changed.
There are four sides to this: consumers & business, the government, clueful hackers & programmers, and bad guys. The first three groups have legitimate interests to protect, and need to be protected from the fourth group. The third group (slashdot types) have to tell the government what they want, and have to inform consumers what encryption means.
This deserves a much longer rant, but less boring...
It was the German magazine Stern that broke the Hitler diaries. It had nothing to do with the Sunday Times. The reputation of the Sunday Times is quite good, really.
It must be true, that's why Clinton eased up on exporting crypto.
We must have stolen it from isreal...
Now the feds don't care if we export PGP to russia...
:P
--
You would crack RSA because you want business to notice you. RSA being cracked means money will be stolen.
Furthermore, if you haven't heard about quantum processing then you should get yourself acquainted v.soon! Whether it's one year or 20 years away, the advent of popular quantum computing will make your average processor no more than a toy. (That is, if it isn't already).
Uh... Integer factorization is in NP, but it is not NP-complete. It is unknown, but considered unlikely, whether a quantum computer will be able to solve NP-complete problems in polynomial time. In other words, a quantum computer is NOT equivalent to a non-deterministic Turing machine. If they really have a working quantum computer, which would be incredible at this point (like having an SR-71 10 years after the Wright brothers started to fly), then they could solve RSA without the private key nearly as quickly as with it.
You could accurately calculate how many primes there are OR get a close approximation. You can count in either prime or non-prime numbers. You could make a low tech brute force machine first, then improve it with algorithms. Supercomputers add. Quanta can almost replace transistors. Opitical waves with consistent analog waves from the influence of molecules can be used as bits in streams. The was already enough optical ram for a buffer five years ago. Factoring first to find primes isn't necessary in a quantum computer. This is all magic. A hard-wired system wouldn't need to start over every time especially a quantum system. Reading quantum bits is difficult so you should let it cycle. The memory state of the "bits" isn't important until it is set before running. The difficult to build stuff can be piped.
Yeah, and who are you to say? Can u proove anything?
Doofus. Much of the Torah was actually written in Aramaic. The rest was likely translated into Aramaic at some point then turned back into Hebrew. Every currently available version of the Bible is a translation. Here's a link.
This was published in a statistic journal (not sure which).Double Doofus. You support a bogus claim and don't even provide a source. Here's an excellent anti-Code site: http://www.ma.huji.ac.il/~drorbn/Codes/
Of course, this has nothing to do with this Quantum Computation story, except that it's vaguely related to Israel, and it's a crock too. QC is thankfully a ways off yet. But yes, if it works, QC could crack a key of arbitrary length in microseconds.
Please down-moderate the Coward's message, it's flatly wrong. First, QC isn't done on a chip, it uses a super-cooled row of ions in a vacuum sealed chamber. To factor a number with X bits, you need X in the row. The computation is performed by superposition of 2^X simultaneous quantum states, in theory taking only microseconds. Here's a link.
From the article: "As one member of EIQC, who wished to remain anonymous, predicts: 'While quantum computers may be some time off, when they are available no communication will be secure unless it is quantum.'"
This is just very, very bad journalism. Someone worked out a theory on paper and this newspaper thought it would be cool to say that it was already done. No one ever reads those big, thick journals, anyway, right?
No, there is no evidence here that this actually happened. I have friends who are working hard on making Q-computing real. As far as I know, they're all still using Sparcs and Macs, not Fairydust TWINKLE Imaginary machines. In all benchmarks I've seen, real computers completely outperforms imaginary hardware.
-------- oops! I posted!
Right, and the Israelies have one of these, handheld model none the less...
Makes sense when I can't find any evidence of anybody at Berkley or MIT having a working prototype, lots of theoretical papers, but has anybody done a Linux port yet??
regardless of who is blowing hot air out his/her ass about how much they know about QC, I seriously fucking doubt that the Israelies have a HANDHELD Quantum Computer cabable of cracking RSA 512, let alone in 12 microseconds...
Gnothe se Auton
It's no good. bad. Free kevin?! no, but really the crackers are good for the economy.
Joseph Elwell.
It is not what I know that counts, it is what is going to turn the most heads. Cracking RSA relatively trivially may be huge news to cryptobuffs and those who rely on it, but its not going to be a huge industry. That this is the only claim that i've read, makes me a little incredulous to say the least.
If you've spent hundreds of thousands of dollars, if not millions, is your first announcement really going to be "We can topple public key cryptography"? It is far more likely going to be a statement as to its marketable potential
I acknowledge the typos reported above. With the two corrections the constant obtained is 1.2e-15, :) ...
resulting in a estimate of 2,337 secs, or 195 million times as long as a 512bit key. That is approx 40minutes btw. Sorry for the carelessness (hey at least I put a ? next to 0.012
All of what you say is true, but not applicable to quantum computing. The article even says "While a regular computer works through each sum one at a time, a quantum computer can do every operation at the same time."
You need to read up on quantum computing...
I saw this comment in M2, and thought I might reply even if nobody sees it.
Try -- works for me, but you gotta use <TT> instead, plus use the <BR> tag at the end of each line. <PRE> doesn't automatically wrap, which means you could arbitrarily set the page width by not using a linebreak. <TT> does pretty much the same thing, except it allows the text to automatically wrap, and you have to use <BR> to force line breaks.
I've done this before, and we'll see if I have it right... (Preview ruins any control characters you type in the browser, so that < reverts back to < when you're ready to submit, at least in my browser (Windows IE5 at the moment).
BANANA
P
P
L
E
Then again, I could preview, hit the BACK button when it's OK, then SUBMIT. Guess it just goes to show TMTOWTDI...
--
--
E2 IN2 IE?
Hi all.
Q CDNA) & TWINKLE T winkle) and come
after reading the article concerning the Weizmann Institute, I contacted Adi shamir, Senior faculty member and developer of the TWINKLE theory.
The following is his reply:
Date sent: Wed, 6 Oct 1999 10:22:50 +0200
From: Adi Shamir
To: deleted@deleted.net.au
Subject: Re: 512bit RSA cracked?
Hi,
I never talked with the author, and as far as I am concerned there is
absolutely no basis for the story. The only scientific paper I published
on the theoretical design appeared at the CHES conference in August,
and can be downloaded from www.jya.com/twinkle.eps
Best wishes,
Adi Shamir.
I also posted a message on the PGP-users list to see if anyone else had any information.
Sam Simpson, who maintains the ScramDisk site, replied with the following links.
This story seems to mix details of QC
(http://www.scramdisk.clara.net/pgpfaq.html#Sub
(http://www.scramdisk.clara.net/pgpfaq.html#Sub
up with some bizarre story that is totally factually incorrect.
Yep, good ol' Sunday Times does it again.
Not American? Get PGPi http://www.pgpi.org