Rounding out our study of cryptology, we'll finish with the most-used cipher today. The RSA cipher (named after its creators, Rivest, Shamir, and Adleman) is a public key cipher -- an amazing type of cipher invented in the late 1970s that doesnt require the sender and the receiver to have previously shared a secret key. Public key ciphers seem to defy all logic. In a public key cryptosystem, the encipherment step and the decipherment step are two rather different things. Consequently, the "key" to such a system is split in half, into a public key and a private key.
A person, lets call her Alice, who wants people to be able to send messages to her, distributes her public key widely, possibly in a format like a phone book. She carefully guards the other half of her key, her private key, to ensure that it is kept secret. Her public key allows her correspondents to encipher a message so that only she can read it. If Bob wants to send a message to Alice, Bob looks up Alices public key in the book, writes Alice a message, enciphers it and sends it to her. Once Bob has enciphered the message, only Alice can decipher it. Bob cant even undo what he has done! When Alice gets the message, she uses her private key to decipher it.
Here are two diagrams to show the difference between a public-key system and a symmetric-key system:
Figure 1: In the traditional model, Bob and Alice must agree secretly to the same key K before they can use their cipher. Eve, an eavesdropper, must not know K for the cipher to work. [The letters above each persons box indicate what he or she knows. M represents a message being sent from Bob to Alice, and K(M) represents the enciphered message. To decipher the message, Alice simply applies K to K(M).]
Figure 2: With the public-key model, Alice freely distributes her public key PA, so both Bob and Eve know it. However she keeps her private key, PrA, secret (Bob doesnt even know it). Even though Eve knows PA and PA(M), Eve cant recover the message without Alices private key. [Again, letters near each box indicate what each person knows. M is the message Bob sends to Alice (he knows it since he wrote it, and Alice knows it since she has deciphered it). PA(M) represents the message enciphered with Alices public key. To get M from PA(M), Alice applies PrA to PA(M).]
Its helpful to think of the following analogy for a public key cryptosystem. Alices public key is like an open (unlocked) padlock, to which only she has the key (her private key). Alice hands these open padlocks out to anyone who wants one. Then, when Bob wants to send Alice a message, he puts the message in a box, puts Alices lock (her public key) on there, and locks it. Once he has done that, only Alice can open the box, since she is the only one with the right key (her private key).
With that in mind, lets turn to one such public-key system.
The RSA Cipher
The RSA cipher, like the Diffie-Hellman key exchange we have already worked with, is based on properties of prime numbers and modular arithmetic.
Why this Works
Eve, our eavesdropper, seems rather well-equipped in this scenario. She knows E, N, and C (remember C= ME (mod N)). So, you might think that it would be easy for her to discover M from what she knows. However, this is really quite difficult. The only way to recover M from C is to know D, Alices private-key. In order to compute D, Eve needs to know what Z is, and, to do that, she needs to know what P and Q are. That is, Eve needs to be able to factor N (remember, N = P*Q). Its important to know that the whole system breaks down if Eve can factor N.
Whats so hard about factoring? Well, the numbers used in RSA are typically huge (N is usually about 200 digits long), and there is no easy or fast way known to factor such large numbers. In fact, the fastest ways known are not too much faster than checking all of the prime numbers less than the square root of N, which would certainly take a while! Factoring quickly is a problem that mathematicians have worked on for thousands of years, and it seems like there is no easy answer. In fact, there are large cash prizes (up to $200,000) for people who can factor specific numbers (visit http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html for details).
The beauty of this system is that, while its hard for Eve to factor N into P and Q, its not hard for Alice to compute N from P and Q. Basically, multiplying is easy, but factoring is hard. For a simple example of this, multiply 7 and 13 in your head. Now try to factor 1001 in your head. The factors of 1001 are fairly small numbers, but I bet it took you a while to find them.
Finally, well address the issue of why MED (mod N) = M. This is obviously important for the cipher to work! However, the math behind this is a bit advanced, so if you had rather skip it, just go on to the next section.
There is a theorem called Fermats Little Theorem that states:
For any prime number p and any number a with a < p, ap (mod p) = a.
To convince yourself of this, you can try it out on a few different numbers with a few different primes (however, that wont be a proof!). Now, to extend this to two primes (remember, in our case, N = P*Q), well use an extension of this theorem that Euler proved:
If n = p*q is the product of two different primes, and a is any number such that a < n,
then a(p 1)*(q 1)+ 1 (mod n) = a.
Notice that the exponent in the conclusion of Eulers theorem is (p -1)*(q -1) + 1. This number is equal to 1 modulo (p -1)*(q -1). Also, remember that Z = (P -1)*(Q -1) in our above discussion. It ends up that for any exponent equal to 1 modulo (p -1)*(q -1), a to that power is a modulo n. By the way we constructed D from E, E*D = 1 (mod (P -1)*(Q -1)), so MED (mod N) = M.
Try working with this cipher yourself, using the RSA secret-sharing worksheet.
Now, if you ever hear anything in the news about a large number being factored, youll know why its important. Nearly everything that is transmitted over the Internet securely is sent using the RSA cipher. This includes all of your credit card transactions, your banking information, and whatever else you send back and forth online.
Since, as you have experienced, the RSA cipher takes some rather hefty computation, its fairly slow to send large messages back and forth enciphered with this cipher. Thus, in practice what is done is that two entities (for example, amazon.com and your computer) will exchange public keys and will use RSA to send each other a new secret key which they will use for another, much faster cipher called DES (or, sometimes Triple-DES). Once theyve agreed on that secret key, they abandon RSA for the much faster cipher.
In addition, RSA is used to solve the problems of authentication, non-repudiation, and many other Internet security issues. (To find out more about Internet security issues, helpful websites include