RSA Encryption

Resources

• Slides
• RSA Calculator Worksheet

Video Script

Let’s take a look at one modern form of encryption called RSA encryption. RSA was developed in 1977, and it was named for the three creators- Ron Rivest, Adi Shamir, and Leonard Adelman. RSA encryption uses the product of two large prime numbers to generate a key that’s used to encrypt data, and the strength of the key really depends on the difficulty of factoring that large number back into its two prime numbers. So for example, if we say our key number is 1071. Can we factor that into the two prime numbers? We could do it eventually, but we’d have to check a lot of different numbers to see what it was. So now imagine that 1071, instead of being a number with just four digits, was a number that had 64 digits in it. That’s really the size of the prime number products that we’re talking about when we do RSA encryption. And so really, the key to RSA encryption is the fact that it’s very, very difficult to factor a large number like that into the two unique prime numbers that are used to create it. So let’s take a look at how RSA encryption works to see why that’s important and why it can create a system that is easily broken if that rule doesn’t hold.

So for RSA, we start with two numbers, p and q. So I’m going to start out with p is five, and q is 17. So we’ve created two distinct prime numbers five and 17. Next, we will compute their products. So the product is n, which is qual to p times q, which is five times 17, which is 85. The other thing we’ll need to compute is Euler’s totient. And the totient of two prime numbers is actually just the number minus one. So to calculate Euler’s totient t, we would do p minus one times q minus one, which is going to be four times 16, which is 64. So we have p is five, q is 17, n is 85, and our totient t is 64. So let’s write that here. Again, we have p is five, q is 17, n is 85, and t is 64.

Now, here’s the really complicated part. We need to choose the number e less than t that is coprime to t so that they share no common factors. Then, we calculate d as the modular multiplicative inverse of e. So that e times x is equal to one mod t. This is really complex mathematics, but what it really means is we need to pick a multiple that is one more than a multiple of t. So if t is 64, we’re looking at 65 129 193, etc. So we’re finding multiples of t, 64, an adding 1, 65. 64 times two is 28, so 129. 64 times three is 193. 64 times four is 256. So we’d look at 257, etcetera. And then we choose one of these that we can factor. So let’s look at 65. Can we factor 65 into two numbers? It turns out we can. So if we set d equal to five, and e equal to 13, we get 65. And e is less than t, and it’s coprime to t. Specifically, e is prime, which is great. Two number are coprime if they don’t share any common factors other than one. And since 13 is prime, it’s also coprime to any other number, which is what we want.

So now we found d and e, which are the keys that we actually need to send and receive our ata. So let’s look at our RSA keys. We have two keys, our public key, which is going to be n and remember and n is 85 and e is five. And then we can encode using this, and we have our private key, which is 85 and 13. So let’s take a look at an example to see how this would work. If we want to encrypt the message 42, what we would do is we would take 42 to the power of five, and then we would do mod 85. So remember, the modulo operation means we divide by 85 and we keep the remainder. So if we actually do this on a calculator, you’ll find that this is equal to 77. And if you have a calculator handy, you can try this yourself. So 77 is the message that we can send as an encoded message. On the receiving end, we would take our encoded message 77, raise it to the power of 13, mod 85. And sure enough, if you calculate 77 to the power of 13, and you might need Wolfram Alpha to do this, then mod 85, you will get back the original message 42. That’s how RSA encryption works. It’s really, really simple. It’s mathematics with a little bit of flavor on top of it to make the keys.

Now, here’s the really tricky part. How do we break RSA encryption? Well, let’s take a look at our keys. Right here in both our public key and our private key, one part of that key is 85. What was 85? Remember that 85 is equal to our two prime numbers, p and q multiplied together. And since p and q are both prime, there is only one way that 85 could be factored. There are no other possible factors. And we know that we use five and 17. So if anybody can factor 85, into five and 17, then they can create t, because t is going to be four times 16, which is 64. And then using t if they have either e or d, they know that e times d would be one more than a multiple of t. And once they have that they could deduce the other half of the key. That’s what’s really important here. So RSA only works if this particular operation is very, very expensive. So to do RSA encryption, we choose numbers p and q, such that they are very, very large. And like I said, we’re talking hundreds of bits, we’re talking multiple digits long, and that’s why there’s so much computing power spent on the search for larger and larger prime numbers. Because for RSA encryption to work, we need those larger and larger prime numbers in order to construct RSA keys that we can use to send and receive data.

This is also really important later on when we talk about concepts such as computability. For example, we’re making an assumption here that the only way to factor a very, very large product of prime numbers is trying all possible prime numbers less than that number. So it’s simply brute force. Now, if we wake up tomorrow, and some mathematician has devised a better algorithm for factoring large products of prime numbers into their two primes, then all of the RSA encryption on the internet isn’t as secure anymore, because now there’s an algorithm that can do that quickly. Another fear would be that quantum computers could do this. And so if a quantum computer discovers a way to factor large products of prime numbers very quickly, it could have the same effect on RSA encryption. Now, of course, this is just one example of one encryption algorithm, but it gives you an idea of the fact that modern encryption is really built upon these ideas that there are very difficult calculations for somebody else to make if they don’t know the original numbers, but those calculations can be made very quickly for us if we know the original numbers that we used to build that key. So I hope this has been really informative. I really encourage you to try RSA encryption for yourself. It is very fun to do the math behind this. And just to see that it works exactly like you’d expect. You can go back and pick any two prime numbers for p and q, and go through this process. The hardest part is finding e and d. But there’s some really great helpers online that you can use, and I’ll link to one of those after this video so you can play around with RSA encryption yourself.