-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 I'm going to talk about Grover's algorithm and Shor's algorithm, plus a good bit on computational complexity theory. The two algorithms are completely different and tackle completely different problems. When I talk about computational complexity theory I'll tie the two algorithms together to show how and when each one is used.
Please bear with me. This is going to be long. > So I take your word for it, that 256 bit keyspace searches are > infeasible, even in the quantum-computer world. I assume that advances > in factorization are comparably insignificant...? As mentioned, Grover's is the best we can do for quantum speedups to brute-forcing. Grover's algorithm is a technique for using quantum mechanics to search through a database of N entries in time proportional to the square root of N, using an amount of storage proportional to the logarithm of N. This is important because brute-forcing a key can be thought of as searching through an unsorted database trying to find the right entry. In math we'd say these two problems are isomorphic to each other. "Isomorphic", for the purposes of this email, just means that we can convert one problem into a different problem with some trivial transformation. As with most things in math the real definition is a little more involved, but this one will work for our purposes. For instance, multiplication and division are isomorphic to each other. To divide by 3, just multiply by 1/3. To multiply by 3, just divide by 1/3. Etcetera. That's isomorphism in a nutshell. Please remember what isomorphism means; you're going to see it again later in this email. Searching through an unsorted database and brute-forcing a key are isomorphic to each other. So we do a trivial transformation on the brute-forcing math problem to convert it into a database search problem, and then we sic Grover's on it. Now, that said, Grover's has limits. Its first constraint is that it doesn't make problems trivial. It just increases our ability to deal with them. Brute-forcing a 128-bit cipher using a traditional computer is a ridiculous proposition, but using Grover's, it becomes as hard as brute-forcing a 64-bit cipher... hard, but possible. So the best way to defend against exhaustive key search in a quantum world is to either (a) trust that quantum computing is going to remain "in just a couple of years" for the next few decades (which may very well be true), or (b) multiply your key sizes by a factor of 2. The principal reason why AES supports a 256-bit key is because of the possibility of quantum computing and Grover's algorithm. Brute- forcing a 256-bit cipher with Grover's is as hard as brute-forcing a 128-bit cipher with a conventional computer... absolutely ridiculous. :) > Then... It would seem that quantum computers poses no threat to > traditional cryptography -- helped by increases in key sizes...? Quantum computing poses no threat to symmetric cryptography. Asymmetric cryptography, however, gets a little funky. Shor's algorithm uses quantum mechanics to solve the integer factorization problem (and, I believe, the discrete logarithm problem) in extraordinary short time. The downside of Shor's is it requires an insane amount of memory--you need two qubits for each and every bit of the number you're trying to factor. So if you're trying to factor a 2048-bit RSA key, you need over four _thousand_ qubits. Our current largest quantum computer is about fifteen qubits. When this monstrously huge quantum computer was demonstrated by IBM, it created a huge hue and cry in the press. Most cryptographers dismissed this as much ado over nothing. Schneier is apocryphally quoted as saying "yeah, any RSA modulus with fewer than eight bits is now truly fucked." But wait, the good news doesn't stop there. Not only is quantum computing a long way off from being able to tackle RSA and/or El Gamal, but Shor's algorithm is _only_ applicable against asymmetric systems built on the integer factorization problem and/or the discrete logarithm problem. For instance, Lamport signatures are a perfectly valid asymmetric signature scheme that are secure even against quantum computing. If and when quantum computing develops to the point where a research lab gets a couple of hundred qubits together, the OpenPGP working group will almost certainly add asymmetric algorithms that are highly resistant to quantum computing. Now for the real head-bending things. Why is it there's such an efficient way to solve the integer factorization problem and the discrete logarithm problem, but such an inefficient way to brute- force a key? Computational theory is the branch of mathematics that's concerned with the fundamental limits of what computers can do. In computational theory, we have several different classifications of problems, depending on how much time and space are required to solve them. There are _tons_ of different complexity classes. The ones we're going to be talking about here are P, NP, and NP-COMPLETE. A problem is said to be in P if and only if it can be solved in an amount of time proportional to its input. For instance, the bubble sort runs in time proportional to the square of its input. Bubblesorting one hundred elements takes a hundred times larger than bubblesorting ten elements. A problem is said to be in NP if and only if verifying the answer for the problem is in P. For instance, factorization is clearly in NP. If I tell you that 37 and 73 are the two factors of 2701, you can easily multiply 37 and 73 together to prove it. Since, once given an answer, proving the answer is in P, we know that the problem of finding the answer must be in NP. NP-COMPLETE means "this problem is one of the hardest problems in NP". "Hardest" here has a very precise meaning which I'm going to mostly gloss over. You can think of it as "a problem is in NP- COMPLETE if it is isomorphic to another NP-COMPLETE problem". (This raises the question of "so how do we find the first NP-COMPLETE problem?" Ah, well, that's why we have so much respect for Stephen Cook, who thunked down a couple of hundred pages of mathematical proof establishing a problem called SAT as the hardest problem in complexity class NP. Once Cook had done his heroic feat of mathematical hacking, all that us Johnny-Come-Latelies have had to do is show other problems are isomorphic to SAT.) Finally, you can always punt a problem into a higher complexity class. If you want to, you can convert a P problem into an NP- COMPLETE problem... but you can't convert an NP-COMPLETE problem into a P problem. That would be a downward punt, and it's not allowed. Got all that? Great. Now it should be easy to follow the rest. When we brute-force a key, we are effectively punting the problem up into NP-COMPLETE. That means it's _really, really hard_. When we discover mathematical weaknesses or flaws in a cryptographic algorithm, if there's determinism we can exploit, then we're tackling the problem in a much lower complexity class. That means it's much easier. Shor's Algorithm applies to two specific problems that live in NP. Grover's Algorithm applies to _every_ NP-COMPLETE problem. Shor's Algorithm is as fast as it is because it's (a) highly specialized and (b) solves an easy problem. Grover's Algorithm is as slow as it is because it's (a) highly general and (b) solves a very hard problem. ... One last word. Computational theory purists will tear this email to absolute shreds. After all, how can I talk about quantum computing without talking about complexity classes BQP or the P=NP problem or...? The worst part about it is, _they're absolutely right_. You're asking a very, very detailed and technical question that requires a ton of disciplined study just to learn the language needed to describe the boundaries of the problem. If you really want to know this material, you need to take a graduate-level course in computational theory and a strong undergraduate course in quantum physics. You'll also need enough background in mathematics not to go running screaming from the room when people start talking about Hadamard matrices and discrete Fourier transforms and everything else that goes along with it. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (Darwin) iQEcBAEBCgAGBQJGJr5QAAoJELcA9IL+r4EJn/YIAIxyk7mP5SH/rxOxjCe3M+AH A8NOgKDMf8Ty9DtRRVedLVOjnZccHJaiK2IqHWu5IcvYQSMK4ljHkclqvtnp9QWq VVquVUakq7gceG4R1BYukdsIoZJY9eatH6n8/wZTdG6V+mzw3RQQyrzuPA6azStr iFaGuPraKXndnCVYqvsu3sMPq59ZBU4biAn0H59WGlZ8nr8a6GY8JFSu26aE3jUJ QLJLj6xPU7cS2+a0v3bZYWdTdwjDp9vrc26QzIk1gnX51Ity9+fJb7SO1/ZKvban LGXg6fKkKB0E5wDP8P6mLuSkm94a9oTAaQ+L0zHMVLtGJ+xP4FjbsrHoOiAF130= =YkAE -----END PGP SIGNATURE----- _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
