IBM Builds A Limited Quantum Computer 317
phr1 writes "IBM has announced and Yahoo has noted that the first working implementation of Shor's
factoring algorithm. Using NMR techniques they built a seven-qubit
quantum computer and factored the number 15 into the factors 3 and 5.
This is by far the most complicated quantum computation ever done.
It's quite an amazing feat--many people thought quantum computing
was just a theoretical curiosity and Shor's algorithm could never
be implemented in practice."
if a quantum computer takes the same time (Score:2, Interesting)
Re:if a quantum computer takes the same time (Score:1, Interesting)
Re:if a quantum computer takes the same time (Score:5, Interesting)
But once the molecules are put together and they can control them properly, then nothing really stops it. That is why they say that a fundamental change in cryptography is on the horizon.
similar has been done before (Score:3, Interesting)
Re:Frightening implications (Score:3, Interesting)
Re:Frightening implications (Score:3, Interesting)
2. Most meaningful research comes from the private sector (bell labs and the like) with a few exceptions (Darpa)
3. Even if the government had quantum computer level encription it couldn't get it's self organized enough to use it for more then maybe presidential level communication.
Re:Frightening implications (Score:2, Interesting)
The NSA's budget is classified. They recruit top people in research fields (and not only U.S. citizens). The estimate I've heard is that they are more like TWENTY years ahead of civilian cryptographers. Don't be fooled by the government's outward appearance of being inept. They do get things done in certain areas where it counts.
Question (Score:2, Interesting)
I am guessing it would only be those which use factoring large numbers as their "hard" problem. Right? Obviously RSA style public key based encryption is in danger, but that just means I need to find a secure channel to exchange keys.
What implications does this have for things like IDEA or even Xoring with a big chunk of random data?
Re:You Heard It Here First... (Score:1, Interesting)
Re:Frightening implications (Score:2, Interesting)
Schneier's Applied Cryptography has a discussion of this with regard to DES. Here's my description of it (I'm doing this off the top of my head, and I'm not an expert, so please excuse any mistakes):
In the early 1970s, IBM was contracted by the US Government to create a standard encryption algorithm that companies could use to secure their communications.
IBM was given free reign to design what they wanted, with one exception: Any algorithm that they developed would have to be given to the government (NSA) to look at, and the government would have final approval. So, after some work, IBM came up with the algorithm that we now know as DES, although what they came up with is slightly different than what is in use today...
The important part of DES, the part that does the actual encrypting, is a part of the algorithm where the incoming bits are mixed. The actual mixing can be described as a matrix of numbers. The makeup of this matrix is important, as it determines whether the bits are properly encrypted. If this block of numbers has the wrong configuration, then the numbers may not be mixed in a truly secure manner.
The question then, of course, is how to determine whether a block of numbers is "secure" or not. IBM had developed a test that would check this particular property, came up with a set of numbers that they had decided would make the algorithm properly secure, and gave it all to the NSA to check.
The NSA approved the algorithm, but with one exception: They supplied a new set of numbers for the mixing block! IBM checked these new numbers, found that they satisfied their requirements for security, and, so, that is what we are using today.
So What? About 10 years later a new method of attacking ciphers was developed, called Differential Analysis. This method was brand new, nobody had ever heard about it before, and turned out to be very powerful. Of course, DES was checked to see how secure it was against this new attack, and it turns out that the security of DES depends entirely on what numbers are picked for the mixing block.
Here's the interesting part: It turns out that the numbers used in DES, the ones that the NSA itself had generated and given to IBM, were in the 2% worst of all possible blocks to be used!
Coincidence? Perhaps...although it does seem to indicate that the NSA was aware of Differential Analysis many years before the rest of the world was, and purposely sabotaged DES to make it easier to crack. Remember that the NSA is the world's largest employer of mathematicians!
Re:What this really means (Score:1, Interesting)
Quantum computing research itself, interestingly enough, has provided at least a replacement for secure communication, if not secure storage, and as far as we know, it's unbreakable (if not currently feasible). You can a stream of information encoded as quantum bits. Any attempt to access them might succeed, yes, but the intended recipient will know, because the stream has been destroyed.
You're exactly right and wrong! (Score:5, Interesting)
But you're wrong in the fact that DES IS resistant to DC. The bit S-box design the NSA gave IBM are designed to make it STRONGER against DC NOT weaker.
"As in choosing the key length , another of the NSA'a design criteria was based on making the algorithm [DES] resistant to differential cryptanalysis..." _AC_ first edition Schneier page 238
If you want to bust the NSA's chops complain that they made the key length go from 128 to (effectively) 56 bits. Now that hurt...
=tkk
NMR vs. MRI (Score:2, Interesting)