10.3 : RSA Encryption

RSA Encryption was introduced in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman at MIT; hence the name "RSA". On the lecture slides, it's also called Public Key Encryption (PKE) and PKC (Public Key Cryptography).

Some links you may find helpful in this section

How it Works

Let's start with a set of generated keys:


	`e` = A Public Key
	`d` = A Private Key
	`n` = Shared Public Modulo

Given that we are using PKC, we use the following encryption and decryption functions to encrypt and decrypt our message m.


	`E(m, k) = m^k^ mod n`
	`D(m, k) = m^k^ mod n`

When you look at these functions, you may have some hypothetical confusions.

"Encryption and decryption are the same function. How can we encrypt and decrypt at the same time?" When we generate e and d, they become inverses of each other. Since you most likely haven't been taught modular arithmetic yet, let's look at some inverses in math that we already know: fractions. Below, I've created two sets of keys, one for person A, one for person B. For the sake of simplicity, I've removed n the shared public modulo.


`e_A = 2, d_A = 1/2`		A set of matching keys
`e_B = 5, d_B = 1/5`		A different set of matching keys
`E(m, k) = m^k`		Encryption function
`E(m, e_A) = m^e_A`		Encrypt with `e_A`
`E(m, e_A) = m²`		Plug in `e_A = 2`
Decrypting with the Right Key	Decrypting with the Wrong Key
`D(m, k) = m^k`	`D(m, k) = m^k`	Decryption function
`D(E(m, e_A), d_A) = E(m, e_A)^d_A`	`D(E(m, e_A), d_B) = E(m, e_A)^d_B`	Plug in keys
`D(E(m, e_A), d_A) = (m²)^1/2`	`D(E(m, e_A), d_B) = (m²)^1/5`	Plug in values
`D(E(m, e_A), d_A) = m^2*(1/2)`	`D(E(m, e_A), d_B) = m^2*(1/5)`	Exponent properties
`D(E(m, e_A), d_A) = m`	`D(E(m, e_A), d_B) = m^2/5`	Simplify

As we can see, just by plugging and chugging, since e_A and d_A are inverses, they can be used together to encrypt and decrypt messages. The same applies to e_B and d_B. Since these keys are inverses, they can encrypt and decrypt each others messages. If I don't use matching keys, I don't get the message I started with.

You may also say "A message is a bunch of letters! How can I raise a word to an exponent?" Remember in the ASCII section, we learned we can use binary to represent letters. Using ASCII, we represent each letter as a number and concatenate them (smush them together) to create one number that we raise to an exponent. If we get a very long message, we can concatenate groups of numbers and then encrypt each group separately. Since we apply a modulo to the resulting exponent, this forces our value to be within a certain range, which tells us how many letters would be concatenated into one numeric part of the message.

Now that we've cleared up some hypothetical concerns about how these functions work, let's deal with new hypothetical concerns about how to use these functions. We have lots of numbers here: e_A, d_A, e_B, d_B, and n. We also have two functions (which are really the same thing, just with different notation so they're easier to tell apart): E(m, k) and D(m, k). We know how to encrypt and decrypt messages, but how do we know what key to use? How do we know when to use each type of key?

The answer is a lot simpler than you'd think. When we want to send a message that only one person can read, we encrypt it in a way such that only one person can decrypt it. PKE can only work if e is always public and d is always private.

Scenario

My name is Charlie, I was the Head TA for CS-164 with Dr. Stuart for five years. Being the Head TA, Dr. Stuart sent me lots of emails about students and their grades. These emails need to be private due to FERPA (fancy government policy making sure that your grades are private and won't be shared without your permission). Let's say we live in a world where emails are posted publicly; anyone can read them. This would make discussion about grades very difficult (and illegal). In order to navigate this terrifying situation, instead of finding a new method of communication, Dr. Stuart and I decide to use PKC to communicate over this insecure network.

We start by each generating a set of keys for ourselves.


	`e~C~` = Charlie's Public Key
	`d~C~` = Charlie's Private Key
	`e~B~` = Dr. Stuart's Public Key
	`d~B~` = Dr. Stuart's Private Key
	`n` = Shared Public Modulo

For the remainder of this scenario, I'm intentionally leaving out n for simplicity's sake.

Above, I use the "speech bubble" to show that we've announced our public keys (e_C and e_B) to the world. If someone would like to know our public keys, they just have to stand close enough to hear it. I don't have to see them for them to know my public key. They don't have to see me to know my public key.

I use the "thought cloud" to show that our private keys (d_C and d_B) are secret. No one can hear my thoughts, thus, no one can know my private key.

To clear up some confusion, I am the figure on the left with the colorful hair. Dr. Stuart is the figure on the right. You can tell since he is wearing glasses (I have 20/20 vision) and clearly does not have a hair care regimen.

Dr. Stuart has recently met with a student (S) about their assignment. He decides that the student should get a 90% on their assignment and would like to send me a message to update the gradebook. Knowing that our messages are public, how should he send this message so that only I can read it?

We know we have to encrypt the message in some way. To use our encryption function, we need a message m and a key k. We already know what m is. What key should Dr. Stuart use to encrypt his message with? Before we think about what key he should use, let's look at what keys he can use.

Dr. Stuart knows his public and private keys (e_B, d_B), his message (that he hasn't sent yet) m, and my public key e_C. Dr. Stuart doesn't know what I'm thinking (and I'm sure he doesn't want to either), so he does not know my private key d_C.

This means he has three keys he can encrypt his message with: e_B, d_B, and e_C. Which should he use?

To figure this out, he should then think about what I know.

I know my public and private keys (e_C, d_C) and his public key e_B. Again, I don't know what Dr. Stuart is thinking (nor do I want to) so I don't know what message m he is trying to send and I don't know his private key d_B.

This means I have three keys I can decrypt with: e_C, d_C, and e_B. Again, we have three keys. How does this narrow down our options?

Remember, matching keys are needed to decrypt messages that have been encrypted. Let's look at what Dr. Stuart and I know in a different format. I've made a table. One column has the keys that Dr. Stuart knows. One column has the keys that I know. The rows are keys that match.

	Dr. Stuart can encrypt with	Charlie can decrypt with
	`e_B`
	`d_B`	`e_B`
	`e_C`	`d_C`
		`e_C`

Now we can see, even though Dr. Stuart could encrypt with his public key, I would not be able to decrypt his message because I don't know his private key. I could decrypt with my public key, but that would require Dr. Stuart sending me a message with my private key, which he doesn't know.

This leaves him with two options. He can encrypt his message with his private key, meaning I would decrypt with his public key. Or, he can encrypt with my public key, meaning I would decrypt with my private key. Both of these options will work, but which should he use if he wants to send me a message that only I can read?

He should use my public key to encrypt the message.

Dr. Stuart sends E(m, e_C). Anyone can read this encrypted message, but that doesn't matter. Since only I know my private key, only I can compute D(E(m, e_C), d_C) to decrypt the message.

If he had used his private key d_B to encrypt the message, I could have decrypted it with his public key e_B. Unlike my private key, everyone knows Dr. Stuart's public key meaning that everyone can decrypt his message. This is not the best option for him to send me a secret message.

And that's how basic Public Key Cryptography works. This next bit will expand on PKE by adding signatures to the mix.

Signatures

After their meeting with Dr. Stuart, student S was very angry. Despite not following the instructions on the lab, they felt they deserved a 100 on their assignment, not a 90. Dr. Stuart was so unreasonable, he might as well have failed them for the class! Does Dr. Stuart not realize that those 10 points on their lab would drop their final grade by 0.38%?!?! This is absurd!

The student, outraged by facing the consequences of not reading the instructions, decides to take matters into their own hands. They know Dr. Stuart is planning on sending me a message about their grade. They also know that in order for this message to stay private, Dr. Stuart needs to use my public key to encrypt the message. This student generates their own RSA keys and sends me a message pretending to be Dr. Stuart. They write their own message, m_S = "Give S a 100", encrypt it, and send it to me.

I check my mailbox and I see I've got two encrypted messages, E₁ and E₂. I decrypt both of them with my private key.


	`D(E₁, d_C)`	`D(E₂, d_C)`
	`E₁^d_C`	`E₂^d_C`
	`(m₁^e_C)^d_C`	`(m₂^e_C)^d_C`
	`m₁^e_Cd_C`	`m₂^e_Cd_C`
	`m₁`	`m₂`
	`"Give S a 100"`	`"Give S a 90"`

Oh no. I don't know which message came from Dr. Stuart. How am I supposed to know which grade to give S? Dr. Stuart and I could find some other way to communicate beyond email, but that would be just as absurd as a 10 point deduction.

Dr. Stuart decides to put a signature on all his messages to me (more than just the classic "BLS"). We mutually agree upon a hash function to use to sign our messages.

A hash function is a one-way function that creates a unique identifier that can be used to describe messages. Let's say I wanted to create a hash function to create unique identifiers for students in my class.


	H(Student) = First letter of their first name
	H(Alice) = A
	H(Joe) = J

As you can see, H(Joe) will always produce J. This is a different value from H(Alice) which will always produce A. If a student were to tell me their name and I asked for the first letter of their name to verify who it was, I would know if Joe was pretending to be Alice since H(Alice) != J.

However, this is a very bad hash function. If I have a student in the class named "Alex", then we have a collision. Both H(Alice) = A and H(Alex) = A. Even though this is a bad hash function, if a student were to come up to me and say H(me) = A, I would have no way of knowing if their name was Alex or Alice.

Let's go back to our scenario. Dr. Stuart and I mutually decide upon a hash function to use to sign our messages. We can't use H(m) = First letter of their first name because our messages aren't about names. The hash function must have some connection to the message. Instead, we decide to use H(m) = length of the message.

Dr. Stuart is going to compute the hash of his message. He then needs to send me this message in such a way that tells me which grade he wants to give the student. How should he send me this message? Let's again look at who knows what, now with our angry student included.

Dr. Stuart can encrypt with	Student can encrypt with	Charlie can decrypt with
`e_S`	`e_S`
`e_B`	`e_B`
`e_C`	`e_C`	`d_C`
`d_B`		`e_B`
`d_S`	`d_S`	`e_B`
		`e_C`

Dr. Stuart could use my public key for me to decrypt with my private key again, but the student also can use my public key. I wouldn't be able to tell them apart.

For the signature, Dr. Stuart will encrypt the hashed message with his private key. I will then decrypt it with his public key.

Now you may think, "Wait, then the student will also be able to read the hashed message. That's illegal!" To which I say, you're right! However, you need to remember that Dr. Stuart is encrypting the hashed message with his private key, not the actual message. This means all the student will see is 11 since H(Give S a 90) = 11. This is not enough information for the student (or anyone) to know what grade the student received or which student is being talked about. Dr. Stuart's message could have been about giving Joe a 80 on his assignment since H(Give J a 80) = 11.

Even though anyone can read the hash, how can I be sure Dr. Stuart sent it? Let's look at the four messages again. Who could have sent them? Who could have read them?

Message	Encrypted Message	Who Can Encrypt?	Who Can Decrypt?
`"Give S a 90"`	`E( m_B, e_C )`	Charlie Dr. Stuart Student	Charlie
`"11"`	`E( H(m_B), d_B )`	Dr. Stuart	Charlie Dr. Stuart Student
`"Give S a 100"`	`E( m_S, e_C )`	Charlie Dr. Stuart Student	Charlie
`"12"`	`E( H(m_S), d_B )`	Student	Charlie Dr. Stuart Student

Now I can read through the four messages I have received: "Give S a 90", "Give S a 100", "11", and "12". I calculate the hash of each message: 11, 12, 2, and 2. Since I didn't receive a "2" message, I know that "11" and "12" must be the signatures that Dr. Stuart and the student sent. Only Dr. Stuart could have sent me the message "11" (since only he knows his private key). Only the student could have sent me the message "12" (since only they know their private key). Even though anyone could have sent me the message "Give S a 90", I know it has to be from Dr. Stuart. Only Dr. Stuart knows the message he wanted to send, which means only Dr. Stuart could calculate its hash and send it to me with his private key.

(I had to abandon my though cloud, the text wouldn't fit, but you get the gist) There's still a lot of text there, a lot of math, and a lot of parentheses. Let's go through it slowly and hopefully it'll be easier to digest.


	`m_B`	Dr. Stuart writes a message
	`H(m_B)`	Dr. Stuart calculate the hash of his message
	`E(m_B, e_C)`	Dr. Stuart encrypts his message with my public key
	`E(H(m_B), d_B)`	Dr. Stuart encrypts the hash of his message with his private key
	`E(m_B, e_C)`	I receive a random encrypted message
	`D(E(m_B, e_C), d_C) = m_B`	I decrypt this message from anyone with my private key
	`H(D(E(m_B, e_C), d_C)) = H(m_B)`	I calculate the hash of this message from anyone
	`E(H(m_B), d_B)`	I receive a random encrypted message
	`D(E(H(m_B), d_B)) = H(m_B)`	I decrypt this message from Dr. Stuart with his public key
	`H(D(E(m_B, e_C), d_C)) = D(E(H(m_B), d_B))` `H(m_B) = H(m_B)`	I verify that the first message from "anyone" came from Dr. Stuart

This process works for anyone. It doesn't matter if I send the message to Dr. Stuart or even if the student sends another student a message. The process is the same. It all relies on everyone's e being public and everyone's d being private.

Certificates

It's time to grade! Let me check my email to see if Dr. Stuart has sent me any updates. I've recieved a message and a signature. I use my public key to decrypt the message and see it says "Give S a 90". Hmmmm, let's check the signature to make sure this message came from Dr. Stuart. I use Dr. Stuart's public key to decrypt his message. And Dr. Stuart's public key is... Uhm... Well it's e_B... And e_B is equal to... Well, I'm sure Dr. Stuart told me once, but it appears I've fallen into the classic trap of not actually paying attention to him when he talks. I should really start listening to him more. It turns out that when professors talk, they say important things that I need to know later.

Well, what do I do now? I've completely forgotten Dr. Stuart's public key. How will I ever be able to decrypt his signature? I could ask Dr. Stuart for his public key again, but it would be really embarrassing to admit that I don't listen to him. What now?

To handle this, we introduce a Certifying Authority or a CA. This is an authority that we both trust to authenticate each others public keys. We'll say our Certifying Authority is Associate Department Head of Undergraduate Affairs for the Computer Science Department, Professor Adelaida Medlock. I chose Professor Medlock for two reasons. 1i) Her job specifically specifically deals with all things "undergraduate" and "computer science". Since Dr. Stuart is teaching CS-164, an undergraduate CS class and I am was an undergraduate student and teaching assistant, we can trust her authority in certifying our public keys. We can also trust her in authenticating our students' public keys. (Also if you're a freshman taking CS-164, it's always smart to know who your leadership is). 2) The Computer Science Department Head, Professor Jeremy Johnson, has the same haircut as Dr. Stuart and that would be too confusing in my artistic renderings. Also, now, CA can stand for both "Certifying Authority" and "Certifying Adelaida", but not "Certifying Jeremy".

Now that we have a mutually trusted CA, we can get to work. Let's give her a public and private key set (e_A, d_A).

I have received two messages from Dr. Stuart. I have his original message about the grade that he encrypted with my public key: E(m_B, e_C). This message is easy to handle, there are no extra steps here. It is decrypted with my private key (d_C). I also have the message that is his signature to verify his original message: E(H(m_B), d_B). This message will be decrypted with Dr. Stuart's public key just as normal. However, I've forgotten what Dr. Stuart's public key is.

In order to figure out Dr. Stuart's public key, I'm going to contact the CA. I will send her a message asking for his public key. I'll encrypt my message with her public key e_A (this way only she can decrypt with her private key d_A).

The CA is going to respond with two messages. First, she's going to send me a message with Dr. Stuart's public key. This will be encrypted with my public key. Second, she'll send me her signature, verifying the original message.

Now I can successfully decrypt the CA's messages, remember Dr. Stuart's public key, and decrypt his signature.

While we have already completed the decryption process, let's take a closer look at what the CA has sent me. The CA sent me E(e_B, e_C) and E(H(e_B), d_A). You'll notice that the message is Dr. Stuart's public key. Typically we use keys to encrypt messages. We don't normally use keys to encrypt keys. How does this work?

We have two options here. We can treat e_B as a message and encrypt it as such, or we can apply the computations directly.

The encryption function is defined as E(m, k) = m^k (mod N). As we mentioned before, a message is a string of letters which means it can't be raised to a numeric exponent. To handle this situation, we use the ASCII representation of the characters and concatenate them. Below, I'm using single quotation marks to denote the difference between a character and a numeric value. Let's pretend that Dr. Stuart's public key is e_B = 1029 and we have N=180919.


	`e_B = 1029`
	`'1'=049 '0'=048 '2'=050 '9'=057`	Convert to ASCII Base-10 over 3 digits
	`m=049048 050057`	Concatenate to form numbers less than `N` as our message to encrypt

We now have a string of numbers that can be encrypted using our encryption function. Each number would be encrypted separately, then sent as a string. Since the modulo operation forces all encrypted messages to be shorter than N, sending multiple numbers at once allows for messages that are longer than N.


	`E(m, e_C) = 049048^e_C mod 180919`
	`E(m, e_C) = 050057^e_C mod 180919`

Another option is to directly encrypt the key; It's already a number, so why do extra work?


	`E(e_B, e_C) = 1029^e_C mod 180919`

Since the CA's job is to send public keys, we can assume that every message we get from the CA will either be a public key or the CA's signature. This means that these certificates can be treated differently than regular messages that I'd receive from Dr. Stuart or students. If I receive a message from Dr. Stuart or a student, I should decrypt their message and then convert the numeric values into ASCII. If I receive a certificate from the CA, I should decrypt their message, then leave the numeric answer as is.

As you can see, in PKE, we can use keys in many ways. Public keys can encrypt and decrypt messages. Private keys can encrypt and decrypt messages. Keys can be sent as messages. Just as we can find the hash of a message, we can also find the hash of a key. The most important part of this process is that only the public key is shared while the private key remains private.

Practice

You're probably expecting to see some clicky JS thing I scrambled together so you can get the instant gratification of a "right" or "wrong" answer. Tough luck. Instead, here are some more "situations" for you to think about and muddle over.

The student can decrypt E(H(m_B), d_B) and tries to fool me. The student decrypts the hash and sends me E(H(m_B), d_S). Would I be fooled into thinking Dr. Stuart sent me the message "Give S a 100" instead of "Give S a 90"? Why or why not?

I contact the CA asking for Dr. Stuart's public key. The angry student, pretending to be the CA, sends me a message stating that Dr. Stuart's public key is e_S. They figure that if they pretend to be the CA, I will believe that Dr. Stuart's public key is e_S and then I'll believe that any message that can be decrypted with e_S must have come from Dr. Stuart. Would this plan work? Why or why not?