Suppose that Bob wants to send a private note to Alice, but Eve is the mailperson and Bob doesn’t trust her. It is very important that only Alice reads it, but Bob can’t meet her and deliver it by hand. What does he do? Here is one solution: Bob writes his secret note, then makes a copy with every letter shifted forwards three spots so that A becomes D, B becomes E, …, Z becomes C. In this way, “the password is banana” turns into “wkh sdvvzrug lv edqdqd”. Bob goes ahead and mails his letter which looks like nonsense to Eve. But if Bob and Alice agreed to this method beforehand, then Alice will be able to decode it (by shifting every letter backwards three places) and read it. Similarly, Alice can send a secret note to Bob.
This is the basic idea of cryptography: Bob encrypts a message into gibberish that only Alice knows how to decrypt. Every time you make any purchase online or fill out any important documents on a computer, you are using encryption. If you weren’t, then anyone between you and Amazon’s servers would be able to intercept and read off your credit card information.
The method of encryption used above (shifting each letter a set number of places) is called a Caesar Cipher (used by Julius Caesar around 58 BC). This cipher can be broken, meaning that if Eve is clever enough, she can look at the gibberish and guess the original message. This works because e is by far the most common letter in English. Eve can find the most common letter in the gibberish, count the number of steps from it to e, and then shift the entire gibberish message that many places to get the original.
Imagine messages as notes inside boxes, encryption as locks on the boxes, and decryption as keys to the locks. With the Caesar Cipher, the lock and the key are almost the same thing; if someone knows how to encrypt a message then they can also decrypt it. Then every person that messages Bob has to have a unique lock/key, otherwise they would be able to see each other’s messages. Consequently, Bob has to meet people in person to decide on a lock/key because there is no other safe way to communicate. But what if we could split the lock and the key — the encryption and the decryption — into two separate pieces?
Bob makes only one key and only one lock, leaving it unlocked. He duplicates the open lock and makes it widely available. If Carol wants to message Bob then she can get an open lock, bolt it with her message inside, and send it to Bob. Eve will only have access to locks and locked messages, no keys. Bob, with his one and only key, can unlock any message sent to him. No meeting people and no keeping track of keys.
This makes sense conceptually, but a working method wasn’t discovered until more than 2,000 years after the Caesar Cipher. The RSA Algorithm does this and is the encryption scheme actually used for online purchases today. To understand how it works we will need two concepts: prime numbers and the modulus operator.
Since 12 = 3 × 4, we say that 12 is divisible by 3. “Prime numbers are whole numbers greater than 1 that are not divisible by any whole number other than 1 and itself. The first few are 2, 3, 5, 7, 11, 13 …” For computers, it is easy to multiply two large prime numbers, but very difficult to take that product and see what two primes made it. To see this, try to calculate 23 × 29, then try to calculate what two primes are multiplied to get 247. You can probably do the first in thirty seconds, but the second might take you a few minutes. Your computer can multiply to get a 300-digit number in under a second, but “it recently took researchers two years to factor a 232-digit number, even with hundreds of parallel computers”.
8 hours after 7 o’clock is 3 o’clock. In a circle, turning 100° four times is the same as turning 40° once. This is the idea of modulus, first with addition modulo 12, then with multiplication modulo 360. In general, A modulo B is the remainder of dividing A by B. 43 modulo 9? Well 43 = 4 × 9 + 7, so the answer is 7. Equivalently, we say that 43 is 7 modulo 9.
We now have the language to state a useful fact: If p is a prime number and n is a whole number less than p, then the p’th power of n is n modulo p. An example: p is 5 and n is 2. Then the 5th power of 2 is 2 × 2 × 2 × 2 × 2 = 32. Indeed 32 is 2 modulo 5. Do check that the 11th power of 4 — 4 × 4 × … × 4 — has remainder 4 when divided by 11, and that 19th power of 6 is 6 modulo 19.
This is known as Fermat’s little theorem. It was stated by Pierre de Fermat in 1640, but the first published proof was by Euler in 1736. We will manipulate it to produce two different numbers: one that Bob distributes to the public — the public key — and one that only Bob knows — the private key. People who want to privately communicate with Bob encrypt their data with the public key, and then it can only be decrypted with the private key.
The problem with Fermat’s theorem as it stands is that, since primes have no divisors, there is no way to break it into two steps. However, the creators of the RSA algorithm — Ron Rivest, Adi Shamir, and Leonard Adleman — were able to take it one step further in 1977: Let p and q be prime numbers and define E = (p - 1) × (q - 1) + 1 and F = p × q. Then any number n raised to the power of E is n modulo F. If p is 11 and q is 17, then F = 11 × 17 = 187 and E = (11 - 1) × (17 - 1) + 1 = 161. So if you raise any number n to the 161st power, then take the remainder when you divide by 187, you will get back that same n. We realize this is very strange, but it can be proven (along with Fermat’s last theorem) in under a couple pages.
This is the insight to finally make the two keys. Since the combination E = (p - 1) × (q - 1) + 1 is usually not a prime number, we can write it as r × s for whole numbers r and s. In the above example, E = 161 = 7 × 23, so r is 7 and s is 23. Raising a number to the power of 161 is now two separate steps: First raise n to the 7th power then raise that result to the 23rd. Raising n to the 7th turns it into gibberish, then raising that to the 23rd gets you back the original message. r = 7 is the encryption and s = 23 is the decryption.
Bob publishes F and r, keeps secret s, and throws away E. Alice wants to send Bob the secret number 123. She calculates 123 to the power of 7 modulo 187, which is 183. Alice publicly sends this to Bob. Bob takes the encrypted message, 183, raises it to the power of 23 modulo 187 and gets back 123. The original number! This is why 23 is the decryption. Eve can only crack Alice’s gibberish, 183, using s. And to find s, she needs to find the prime factors of 187, but for larger numbers that can take years. As for encrypting letters and symbols and pictures that aren’t numbers, realize that every piece of data is a number in the machine at some level.
Details aside, now anyone anywhere can send Bob a private message without meeting him. Further, he makes the key/lock one time and can use it pretty much forever. We can see why so many major websites— Amazon, Ebay, Google, NSA.gov — use the RSA algorithm. But if Ron, Adi, and Leonard were never encouraged as students to pursue their interests, then we wouldn’t have this incredible result.
I copied most of the RSA explanation from here:
[Prime Numbers Hide Your Secrets - Edward Frenkel - June 2013] (http://www.slate.com/articles/health_and_science/science/2013/06/online_credit_card_security_the_rsa_algorithm_prime_numbers_and_pierre_fermat.html)
Public Domain Dedication.