-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
> > This is true on current technology, but MIT, US Govt., England > etc. etc. are working on quantum computers that can break DES in > a few min. How much computer power do these governments have? > Way beyond terahertz, but have they hit petahertz? > Well, first.. You should gain a good feeling for the difference between linear growth and exponential growth. As you add bits to a crypto system's keysize, the computing power needed to do an exhaustive brute force attack increases exponentially. As you increase the clock speed of a computer, you only increase the computing power linearly. So if a super computer running at 100 gigahertz (I kept this intentionally low) can break a 56-bit system using an exhaustive brute force attack in 1 minute, it would take a twice as much computing power to break a 57-bit system under the same method.. If we keep following the progression, we will clearly see the difference between exponential growth and linear growth. Clock speed keysize - ------------- --------- 200 Ghz 57-bit 400 Ghz 58-bit 800 Ghz 59-bit 1.56 Thz 60-bit ... 50 Thz 65-bit ... 1.56 Petahertz 70-bit ... 6871947673600 Petahertz would be needed to brute force the same system with double the keysize.. 112-bits.. This is why distributed computing is a good idea, but it will never beat exponential growth, because it can only achieve a linear increase in computational power. This is a problem inherent in an exhaustive brute force approach. I read someone mentioning something about using differential cryptanalysis on 3DES... Something like that would certainly be the way to go, but differential cryptanalysis won't even work on single DES.. It'll only work if you're using reduced rounds.. (I'm pretty sure I'm right on this, but please correct me if I'm wrong). So, everyone turns to quantum computers as the next big thing for code breaking. Peter Shor's quantum factoring algorithm is magic.. If you're got enough qbits, you can pick a number less than N, feed in an f(x), do a quick FFT, and boom.. You can divine the original factors. This is great for breaking an asymmetric cryptosystem like RSA. But it's not going to do anything against a symmetric block cipher like DES or 3DES. What we need for that is a way to do an exhaustive brute force using quantum computing. Well, a quantum computer is certainly suited for doing brute force operations.. It could theoretically do everything in a single massive parallel step. The tricky part is getting the system to decohere into the correct superposition that contains the solution. Luckily, Lov Grover has provided us with an algorithm that can do that.. And I believe he even proved that his algorithm is the fastest way to do a search using quantum computation. The runtime of this algorithm is O(sqrt(N)). In short, polynomial runtime... This is much better than the linear improvement we saw before using conventional computation, but it's still not enough to keep up with exponential growth.. Assuming a quantum computer can perform quantum operations (inverting about the average) at the same speed as the hypothetical supercomputer used in the example before, a 112-bit symmetric block cipher could be cracked using exhaustive brute force on the quantum computer at about the same speed as the conventional computer. But, a 256-bit cipher on the quantum computer would take the same time/power as a 128-bit cipher on the conventional computer... Which turns out to be something like 8.98 x10^17 years. So I guess what I'm saying is.. Exponential growth is hardcore. Using existing quantum computing algorithms, there is a significant threat on ciphers that are based around the problem of factoring, and a mild threat against those who aren't. But until someone figures out some new quantum algorithms, if you simply use crypto systems that aren't based on factoring, and double your keysizes.. You don't really even have to worry about the theoretical possibilities of quantum computation... - -- Jon Erickson Cryptologist and Security Designer Caspian 415.974.7081 D49B 4561 1078 0A72 DDF3 7250 8EF4 4681 587E 41DD 1728748 -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com> iQA/AwUBPDSnT470RoFYfkHdEQJDxgCfePbd1+LdL66BchBIVgCFXTD7Yx0AmwZh U4f2CFwOHb0SMtiSn/Ye/SnH =avFp -----END PGP SIGNATURE-----
