RSA Encryption
Is it safe to send credit card numbers over the internet? This is what encryption and RSA is all about. But to really appreciate RSA you need to understand the problem of Public Key encryption.
Suppose you want to tell a friend a secret number. No problem. The two of you meet someplace where no one can see you or hear you, and you tell your friend the number.
But suppose you can't meet. Instead you have to leave the number on the refrigerator door where everyone can read it. Well, if you can meet at least once, ahead of time, where no one can see you or hear you, then you can decide on a code. For example, you could decide to "multiply the number by 531 and then add 2". Somebody reading the number wouldn't know how to decode it. They wouldn't even know that your method was multiply and then add. For example, you could have coded the number by the rule "change every odd digit by subtracting 1, and change every even digit by adding 1 and then write the number backwards".
The problem is you can't meet. And it is even worse. You are standing on opposite sides of a room and have to yell at each other. There are thousands of people in the room listening to everything you say. How can you tell the number without everyone else knowing? This is exactly the problem of Public Key encryption. You are buying laundry soap over the internet from Acme Detergent, Inc. and the company wants your credit card number. Whatever information you send to the company and whatever instructions the company sends to you goes over very public pathways and is viewable by thousands of hackers who have nothing better to do then try and get your credit card information.
Fortunately, both you and your friend have computers to do calculations. This is what your friend yells to you to do.
Raise the secret number to the 13th power.
Take the answer and divide it by 391
Tell me the remainder. You yell back 225.
What was the secret number? How would a hacker go about trying to figure it out?
To illustrate: Suppose the secret number is 123.
Raising to the 13th power is 12313 = 1474913153392179474539944683
Dividing by 391 and
Taking the remainder gives: 12313 "Mod 391" = 225
So the hacker knows, 13, 391 and 225. And the hacker knows exactly what mathematics was done. One way to figure out the secret number is by brute force. In this case the numbers 13, 391 are so small it would be possible to start at 2, raise it to the 13th power, divide by 391 and see if the remainder was 225. If not try 3, and keep going. This is an elementary loop program on a computer.
BUT: On the internet the numbers are not small. Imagine that instead of 13, a 2-digit number, there was a 100-digit; and instead of 391, a 3-digit number, there was a 200-digit number. Then brute force would not work. It would take to long.
This is Public Key Encryption. A company (in our example I am the company) announces to the world two numbers (E=13, M=391) and the algorithm (1) raise your secret number to the E=13th power (2) divide by M=391 (3) send back the remainder. Anybody needing to communicate with the company uses these two numbers and this algorithm. This is secure from a brute force attack by choosing (E,M) large.
But how do I (the company) decode the message 225 and get the original number 123 back? The answer is: I have a special Decoder Number!
The Decoder Number The company has another number which it keeps locked up in a vault, written on rice paper in invisible ink. For the illustration above the Decoder is 325. The company uses special recipe --- called an algorithm --- similar to the coding recipe above, to decode the message. Here's how it works.
Decoding. Remember that the sent, encoded message was 225.
Raise the message 225 to the power of the Decoder; i.e. compute 225325
Divide this result by 391
And take the remainder: 225325 Mod 391 = 123: The original message!
If you know the theory underlying this, finding the decoder number is deceptively easy. Take 391 and factor it into two prime numbers. 391 = 17*23. Subtracting 1 from each of the factors we get (17-1)*(23-1) = 16*22 = 352. Now find the first number D so that (D*13-1)/352 is an integer (simple to do on a computer). D will be the Decoder Number. BUT...This is easy only if you can factor 391 into its two prime factors! Now 391 is relatively small --- only three digits. Factoring really big numbers --- hundreds of digits --- is not an easy chore: even with high-speed computers it can take centuries.
Here is how a business can create the numbers (E, M) and the decoder number D.
Find two large prime numbers and set M = P*Q. In this example P = 17, Q = 23 and M = 17*23 = 391
Pick some number E > 1 which is relatively prime to
(has no factors in common with) the number (P-1)(Q-1). In this example, E =
13, which has no factors in common with (17-1)(23-1) = 352 =
25 * 11.
Calculate D so that (D*E-1)/[(P-1)(Q-1)] is a whole number. In this example (325*13-1)/[(17-1)(23-1)] = 12 and 325 is the first number that makes the division a whole number.
Returning to the hacker, everything depends upon being able to factor 391=17*23. This is of course easy for a 3-digit number like 391 but would take too long for a 200-digit number.
To summarize: the algorithms (recipes) are very simple. The protection comes from the size of the numbers.
Why does this work? To understand the Setup and Decoding and why the numbers are chosen as they are, you have to read up on some number theory. One good text, that has a complete discussion of RSA (and other cryptographic schemes) is Number Theory with Computer Applications by Kumanduri and Romero (Prentice Hall). You can also visit the website http://www.di-mgt.com.au/rsa_alg.html or use a search engine to find others.
How secure is RSA? Hackers are always looking for schemes to break codes. So far, RSA is pretty good, especially if the numbers are very large. Yet, we don't know for sure that it will always be so.
Is there a fast way that we don't know about yet to factor a large number into primes?
Is there a fast way to find the decoder number without factoring M?
Is there a fast way to decode the message without finding the decoder number or factoring M?