RSA Encryption
I did a bit of reading on RSA encryption in order to prepare myself to explain Shor's algorithm on this blog. Then I realized that there's no way I can explain Shor's algorithm without doing something more generic and explaining some of the simpler algorithms first. But, having already read up on RSA encryption, I didn't want to just let that knowledge leak out of my brain without writing something about it. So I'll start by quoting from this website, which has a quick explanation of how RSA works:
Follow all that? Now finding prime numbers isn't costless--it takes a computer time to do so, and to do all those calculations. If I recall correctly, it's O(N3), meaning that the number of operations the computer has to perform is some constant times N cubed, where N is the bit length of the encryption code. The constant and any smaller terms are ignored.1 This is the reason you create keys which are only 2048 bits long, even in the largest key used in RSA. That's 2 kb, or .25 kB (since a byte has 8 bits). Now even something as simple as this post is 4.9 kB long (I checked), and since the plain text has to be smaller than PQ, so you couldn't encrypt this whole post using your key. What you'd have to do instead is break this post into chunks, and use the key to encrypt each chunk, then send each encrypted piece to the person on the other end. That means that you'd use the same key 20 times in order to encrypt the whole thing. As I mentioned in my earlier post, using a key multiple times makes it possible to attack an encrypted message by simply trying every possible value of D until you get something that decodes all those chunks into something that makes sense. Of course, RSA has another brute force method of attack. Since the attacker will have PQ, E, and C, he can try every possible value of T in the equation T^E mod PQ until he gets C. Since the cipher text is unique, he will have definitely found the plaintext when he finds the T that works. Unfortunately for him, that will only solve for one of those chunks--it gives no information on the other ones. If, instead, he tries every possible value of D, he'll need some sophisticated algorithms to decide whether his value of D gives him a sensible message for all the chunks. Both of these are bad ways of trying to solve this problem, though. These algorithms are both O(2N), the only appreciable difference being the constant out in front. The fastest method of attack is trying to factor PQ, which is only O(2N/2)--the method which the author of the article says will take until the sun burns out (This isn't the fastest algorithm for factoring a large product of primes. I believe the fastest is O(exp(N/3)), but it's still very slow.). However, if you have a quantum computer, you can use Shor's algorithm, which is O(N2log(N)). This factors large products of primes faster than they can be produced.
1I'll be using this notation a lot in this post, despite the fact that it's been a while since I've done these calculations and there's a good chance I got a lot of the numbers wrong. By which I mean slightly off, not that I'm just guessing or anything. Honest!
- Find P and Q, two large (e.g., 1024-bit) prime numbers.
- Choose E such that E is greater than 1, E is less than PQ, and E and (P-1)(Q-1) are relatively prime, which means they have no prime factors in common. E does not have to be prime, but it must be odd. (P-1)(Q-1) can't be prime because it's an even number.
- Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). Mathematicians write this as DE = 1 (mod (P-1)(Q-1)), and they call D the multiplicative inverse of E. This is easy to do — simply find an integer X which causes D = (X(P-1)(Q-1) + 1)/E to be an integer, then use that value of D.
- The encryption function is C = (T^E) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation. The message being encrypted, T, must be less than the modulus, PQ.
- The decryption function is T = (C^D) mod PQ, where C is the ciphertext (a positive integer), T is the plaintext (a positive integer), and ^ indicates exponentiation.
Your public key is the pair (PQ, E). Your private key is the number D (reveal it to no one). The product PQ is the modulus (often called N in the literature). E is the public exponent. D is the secret exponent.
You can publish your public key freely, because there are no known easy methods of calculating D, P, or Q given only (PQ, E) (your public key). If P and Q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence can factor your modulus into P and Q.
Follow all that? Now finding prime numbers isn't costless--it takes a computer time to do so, and to do all those calculations. If I recall correctly, it's O(N3), meaning that the number of operations the computer has to perform is some constant times N cubed, where N is the bit length of the encryption code. The constant and any smaller terms are ignored.1 This is the reason you create keys which are only 2048 bits long, even in the largest key used in RSA. That's 2 kb, or .25 kB (since a byte has 8 bits). Now even something as simple as this post is 4.9 kB long (I checked), and since the plain text has to be smaller than PQ, so you couldn't encrypt this whole post using your key. What you'd have to do instead is break this post into chunks, and use the key to encrypt each chunk, then send each encrypted piece to the person on the other end. That means that you'd use the same key 20 times in order to encrypt the whole thing. As I mentioned in my earlier post, using a key multiple times makes it possible to attack an encrypted message by simply trying every possible value of D until you get something that decodes all those chunks into something that makes sense. Of course, RSA has another brute force method of attack. Since the attacker will have PQ, E, and C, he can try every possible value of T in the equation T^E mod PQ until he gets C. Since the cipher text is unique, he will have definitely found the plaintext when he finds the T that works. Unfortunately for him, that will only solve for one of those chunks--it gives no information on the other ones. If, instead, he tries every possible value of D, he'll need some sophisticated algorithms to decide whether his value of D gives him a sensible message for all the chunks. Both of these are bad ways of trying to solve this problem, though. These algorithms are both O(2N), the only appreciable difference being the constant out in front. The fastest method of attack is trying to factor PQ, which is only O(2N/2)--the method which the author of the article says will take until the sun burns out (This isn't the fastest algorithm for factoring a large product of primes. I believe the fastest is O(exp(N/3)), but it's still very slow.). However, if you have a quantum computer, you can use Shor's algorithm, which is O(N2log(N)). This factors large products of primes faster than they can be produced.
1I'll be using this notation a lot in this post, despite the fact that it's been a while since I've done these calculations and there's a good chance I got a lot of the numbers wrong. By which I mean slightly off, not that I'm just guessing or anything. Honest!
