Karmarainbow wrote:

Thanks for your reply. I'm not sure I follow. According to EP, public key encryption can be hacked using a quantum computer with a base time of 1 week. Presumably because the quantum computer is able to try multiple brute force attacks simultaneously. PGP public key encryption has a 128 bit key. From googling there doesn't seem to be a huge difference between a 128 bit and a 256 bit scheme: they should both take billions of years to crack, but EP says that public encryption can be cracked in a week with a quantum computer. So I don't understand why using AES256 is any more secure than the public key encryption that can be hacked. Am I missing something? Thanks

The fundamental assumption of cryptography is that there are some mathematical processes that are simple to perform but difficult to reverse. At its most simple, we can consider prime factorization. Finding the product of two primes is simple mathematically, because multiplication is a simple and fast process, even for large numbers. Multi-digit multiplication can be taught to primary-grade school children, after all. Finding which two primes make up a given number, meanwhile, is rather difficult. Take, for example, the number 2701. Finding its two prime factors is a slow and laborious process. This is known as a "trapdoor function"; it's easy to fall in (multiplication), but difficult to climb out (factorization). By using such trapdoor functions, you can encrypt a message in a reasonable amount of time (say, 10 seconds), yet someone who wants to crack the encrypted message has to work for a painfully long time (say, several million times longer than the age of the universe). When a message is encrypted with a key made up of n binary digits, the most general approach to cracking the encryption on that message is to try every single key of length n. This will take 2^n calculations. If we assume that a modern computer can make 100,000,000 encryption calculations per second, it will take about 10 nanoseconds to encrypt a message, 10 nanoseconds to decrypt a message, and 5 seconds to crack a message encrypted with a key 32 binary digits long. If we double the length of they key to 64 binary digits, it will take over 584 years to crack the encrypted message... and maybe about 20 nanoseconds to encrypt and decrypt it if you have the key. Mathematicians and computer scientists tend to label this computational complexity using a form of notation called "big O notation". For example, cracking the hypothetical cryptosystem mentioned above takes O(2^n) times for a key of length n. This means that for a key length n, it will take a*2^n operations on a computer to solve the problem, where a is a constant. For almost all practical purposes, a is insignificant, so we need only concern ourselves with the 2^n part. Most public-key cryptosystems use modular arithmetic and the process of exponentiation to encrypt messages. This is where the multiplication and factorization comes in. They take advantage of the fact that it's easy to multiply numbers, but difficult to factorize them. Factorizing a number takes O(e^(1.9*(log(N))^(1/3)*(log(log(N)))^(2/3))) time; it's actually a little easier than trying every single number! However, it's still slow enough that for a big enough n, such as n=1024 bits, it would take thousands or even trillions of years to crack the encryption. This is all, mind, using conventional computers. Quantum computers are a little different. When conventional computers search through an unsorted list of n entries, they have to go through all the entries one-by-one; this will take O(n) time. Quantum computers, meanwhile, can search through unsorted lists in O(n^0.5) time. Since trying all the keys is the same as searching through an unsorted list, this means that when trying all 2^n different n binary digits long keys, a quantum computer can do it in O(2^(0.5*n)) time. A 128-bit long key becomes as effective as a 64-bit key, a 256-bit key can be solved as fast as a 128-bit long key, etc. Secondly, quantum computers can solve integer factorization problems in O(log(n)^3) time, which is [i]really fast[/i]. On a conventional computer capable of 10^15 calculations per second (about what modern supercomputers can do), 2048-bit RSA would take 130 times the age of the universe to crack this. On a quantum computer capable of just a million calculations per second, cracking 2048-bit RSA would take just 48 minutes. What's worse for RSA's security is that increasing key length does nothing! Against conventional computers, increasing the key length to 8196 bits increases time to some 10^30 times the age of the universe... but against a quantum computer it increases time to less than three days. In the competition between those who make the keys longer, and the people making faster quantum computers, the people with the quantum computers will quickly win. To return to the original topic, AES-256 can be cracked in about O(2^254.4) time (basically forever) on a conventional computer, or O(2^127.2) time on a quantum computer (also basically forever). Similarly, while [i]many[/i] public-key cryptosystems are weak to cracking by quantum computers (because they rely on integer factorization being computational hard), not [i]all[/i] do. The [url=http://en.wikipedia.org/wiki/McEliece_cryptosystem]McEliece cryptosystem[/url], for example, is a public key cryptosystem that is not weak to any known quantum computational algorithm. If implemented, a conventional computer could break it in O(2^n) time, and a quantum computer in O(2^(0.25*n)) time. (Slightly faster than simply searching through all 2^n options, but this is insignificant because you can just quadruple the length the key to compensate; this is not considered a "weakness" in the cryptographic sense.) I like cryptography! ^w^