RSA Encryption 🔐
The Problem
Alice wants to send a secret message to her friend Bob. The message is the single letter “C.”
How can she confidentially deliver this message, assuming that her sworn enemies, Mallory and Eve, might peek at its contents while it is in transit?
Example
The “Lock” 🔒 (AKA the public key): (5, 14)
- This pair of numbers is public, and is used by Alice (the sender) to encrypt messages.
The “Key” 🔑 (AKA the private key): (17, 14)
- The first number in this pair of numbers is private, i.e. only known by Bob (the receiver). This pair is used to decrypt messages.
- Alice encrypts the message “C” using
(5, 14).
a. First, “C” is converted into an integer. In ASCII, “C” maps to the integer 67. But for simplicity, let’s say it maps to 3 instead.
b. Then, 3 is encrypted.3⁵ mod 14 = 5. - Alice sends the result, 5, to Bob. If Mallory or Eve peek and see this message, it tells them nothing.
- Bob decrypts the result using (17, 14).
a.5¹⁷ mod 14 = 3.
b. The result is 3. Bob maps 3 back to a character, which is “C”, to get the original message!
Lock & Key Generation
Now you may be wondering — how do those two pairs of numbers get generated? Let’s answer that question.
Note that, in our example, Bob generates these two pairs of numbers. He gives everyone access to the first pair of numbers (5, 14), but keeps the second pair secret (specifically the first part 17, the second part 14 is in the first pair and thus is public) so only he can decrypt messages. Now, here’s the process.
1. Choose two prime numbers, p and q. In real life scenarios, they should be large (for security), but we’ll choose small numbers to make things easier.p = 2q = 7
2. Compute n = p * q. This is the modulus we used in the previous example.n = 2 * 7 = 14
3. Compute Φ(n), which is known as Euler’s totient. This counts the number of positive integers less than n which are coprime to n (i.e. integers whose GCD with n is 1). There happens to be a nifty equation for this (since p and q are relatively prime).Φ(n) = (p — 1) * (q — 1) = 6
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (bolded, italicized integers are coprime with 14)
4. Compute e (for encryption) such that:1 < e < Φ(n) andGCD(e, Φ(n)) = 1
Since Φ(n) = 6 in our case, we only have these options: 2,3,4,5. And only 5 meets the second criterion.
5. Compute d (for decryption) such that:d * e ≡ 1 mod Φ(n)d * 5 ≡ 1 mod 6
This means d can be 5, or 11, or 17, and so on. We’ll choose d = 17.
That’s it, we’re done! We now have:
The “Lock” 🔒: (e, n) = (5, 14)
The “Key” 🔑: (d, n) = (17, 14)
As shown before, senders can use the first pair of numbers to encrypt messages, and the receiver can use the second pair of numbers to decrypt messages.
Why Does This Work?
The basic principle underlying RSA is that for all integers 0 ≤ m < n, it is practical to find positive integers e, d, and n such that:(mᵉ mod n)ᵈ mod n = m and such that even if e and n are made public, it is extremely difficult to find out what d is.
Note: in our example, m was 3.
In other words, this means it’s relatively easy to find three numbers such that, if we apply them in a two-part formula to a number m, we get that same number back. The magic part is, we can publicize two of those numbers so that anyone can apply the first part of the formula, and we can do so without compromising the third and final number (which is necessary to compute m).
There’s one key point we glossed over on the last page — what makes it so difficult to find d? This is an important question to answer, as this difficulty is what makes RSA secure.
Let’s review what information is publicly available: everyone knows what e and n are, and everyone knows that d * e ≡ 1 mod Φ(n) d * e ≡ 1 mod ((p — 1) * (q — 1))
Thus, the most obvious way to find d is to find p and q, and then solve for that equation. However, this requires computing the prime factorization of n (remember, n = p * q), and if n is really big, then this problem is really hard. As for why it’s hard — well, that’s out of our scope, but you can check out the resources to learn more.
Digital Signatures
One last thing before we’re done. In the example, we saw how RSA can be used to encrypt a message, so that it can be securely delivered to its recipient.
RSA has another common use case — digital signatures. Continuing with our previous example, if Bob wants to digitally sign a message, i.e. prove that a message comes from him, he can encrypt it with his private key, (17, 14). Notice that before, this was used for decryption. Now it is being used for encryption! This means that anyone can decrypt the message with Bob’s public key, (5, 14).
If the message is decrypted with (5, 14), the result will be reasonable. If it is decrypted with something else, the result will be gibberish.
Note that this method assumes that everyone trusts that (5, 14) is indeed Bob’s public key.
Resources
- Eddie Woo’s RSA videos
https://www.youtube.com/watch?v=4zahvcJ9glg
https://www.youtube.com/watch?v=oOcTVTpUsPQ - https://en.wikipedia.org/wiki/RSA_(cryptosystem)
- https://sites.google.com/site/danzcosmos/why-rsa-encryption-is-secure
- TCP/IP Illustrated, Vol. 1: The Protocols (Ch. 18)
