WEBVTT 00:00:00.000 --> 00:00:04.090 In the previous segment we saw how to build public key encryption from trapdoor 00:00:04.090 --> 00:00:08.390 functions, in this segment we're going to build a classic trapdoor function called 00:00:08.390 --> 00:00:13.295 RSA. But first let's quickly review what a trapdoor function is. So recall that a 00:00:13.295 --> 00:00:17.283 trapdoor function is made up of three algorithms. There is a key generation 00:00:17.283 --> 00:00:21.056 algorithm, the function itself, and the inverse of the function. The key 00:00:21.056 --> 00:00:25.313 generation algorithm outputs a public key and a secret key. And in this case, in 00:00:25.313 --> 00:00:29.786 this lecture the public key is going to define a function that maps the set X onto 00:00:29.786 --> 00:00:33.882 itself. Which is why I call these things trapdoor permutations, as opposed to 00:00:33.882 --> 00:00:37.978 trapdoor functions, simply because the function maps X onto itself, whereas a 00:00:37.978 --> 00:00:43.356 trapdoor function might map the set X to some arbitrary set Y. Now given the public 00:00:43.356 --> 00:00:47.819 key, the function, as we say, basically defines this function from the set X to 00:00:47.819 --> 00:00:52.914 the set X. And then given the secret key, we can invert this function. So this 00:00:52.914 --> 00:00:57.401 function F evaluates the function in the forward direction, and this function F 00:00:57.401 --> 00:01:02.059 inverse, which means the secret key SK, computes F in the reverse direction. Now 00:01:02.059 --> 00:01:06.489 we say that the trapdoor permutation is secure if the function defined by the 00:01:06.489 --> 00:01:11.033 public key is in fact a one-way function, which means that it's easy to evaluate, 00:01:11.033 --> 00:01:15.404 but without the trapdoor, the secret trapdoor, it's difficult to invert. Before 00:01:15.404 --> 00:01:20.076 we look at our first example of a trapdoor permutation, I want to do a quick review 00:01:20.076 --> 00:01:24.467 of some necessary arithmetic facts that we're gonna need. And in particular, 00:01:24.467 --> 00:01:28.632 let's look at some arithmetic facts modulo composites. So here we have our 00:01:28.632 --> 00:01:33.192 modulus N, which happens to be a product of two primes, and you should be thinking 00:01:33.192 --> 00:01:37.864 of P and Q as roughly equal size numbers, since particular P and Q are both roughly 00:01:37.864 --> 00:01:42.407 on the size of square root of N. So both are roughly the same size. Recall that we 00:01:42.407 --> 00:01:46.834 denoted by ZN the set of integers from zero to N minus one, and we said that we 00:01:46.834 --> 00:01:51.318 can do addition and multiplication module N. We denoted by ZN star the set of 00:01:51.318 --> 00:01:55.801 invertible elements in ZN. So these are all the elements, which have a modular 00:01:55.801 --> 00:02:00.925 inverse. And we said that actually X is invertible if and only if it's relatively 00:02:00.925 --> 00:02:05.928 prime to N. Moreover, I also told you that the number of invertible elements in ZN 00:02:05.928 --> 00:02:11.147 star is denoted by this function phi(N). So phi(N) is the number of invertible elements in ZN 00:02:11.147 --> 00:02:15.814 star, And I told you that when N is a product of two distinct primes, then in 00:02:15.814 --> 00:02:20.788 fact phi(N) is equal to (P - 1) times (Q - 1) and if you extend that out, you 00:02:20.788 --> 00:02:26.007 see that this is really equal to (N - P - Q + 1). Now remember that I said 00:02:26.007 --> 00:02:30.858 that P and Q are on the order of square root of N which means that P + Q is 00:02:30.858 --> 00:02:35.675 also on the order of square root of N. Which means that really phi(N) is on the 00:02:35.675 --> 00:02:41.050 order of N minus two square root of N. So, in other words, it's very, very close to 00:02:41.050 --> 00:02:45.158 N. Basically, subtracting the square root of N from a number, this is from, N is 00:02:45.158 --> 00:02:49.425 going to be a huge number in our case, like 600 digits. And so subtracting from a 00:02:49.425 --> 00:02:53.533 600 digit number, the square root of that 600 digit number, namely a 300 digit 00:02:53.533 --> 00:02:57.534 number, hardly affects the size of the number. Which means that phi(N) is really, 00:02:57.534 --> 00:03:01.908 really, really close to N, and I want you to remember that, because we will actually 00:03:01.908 --> 00:03:06.122 be using this now and again. And so the fact that phi(N) is really close to N, means 00:03:06.122 --> 00:03:11.094 that if we choose a random element modulo N It's very, very, very likely to be in ZN 00:03:11.094 --> 00:03:15.633 star. So it's very unlikely that by choosing a random element in ZN, we will 00:03:15.633 --> 00:03:20.085 end up choosing an element that is not invertable. Okay. So just remember that, 00:03:20.085 --> 00:03:25.479 that in fact almost all elements in ZN are actually invertible. And the last thing 00:03:25.479 --> 00:03:30.939 that we'll need is Euler's theorem, which we covered last week, which basically says 00:03:30.939 --> 00:03:36.332 that for any element X in ZN star, if I raise X to the power of phi(N), I get one, in 00:03:36.332 --> 00:03:42.527 ZN. So in other words, I get 1 modulo N. I'll say it one more time because this 00:03:42.527 --> 00:03:47.466 is gonna be critical to what's coming. Again X to the phi(N) is equal to 1 modulo 00:03:47.466 --> 00:03:51.997 N. So now that we have the necessary background we can actually describe the 00:03:51.997 --> 00:03:55.927 RSA trapdoor permutation. This is a classic, classic, classic construction in 00:03:55.927 --> 00:04:00.811 cryptography that was first published in Scientific American back in 1977, this is 00:04:00.811 --> 00:04:05.576 a very well known article in cryptography. And ever since then, this was 35 years 00:04:05.576 --> 00:04:10.340 ago, the RSA trapdoor permutation has been used extensively in cryptographic applications. 00:04:10.340 --> 00:04:15.110 For example, SSL and TLS use RSA both for certificates and for key exchange. There 00:04:15.110 --> 00:04:19.452 are many secure email systems and secure file systems that use RSA to encrypt 00:04:19.452 --> 00:04:23.515 emails and encrypt files in the file system. And there are many, many, many 00:04:23.515 --> 00:04:27.690 other applications of this system. So this is a very, very classic, crypto 00:04:27.690 --> 00:04:32.541 construction, and I'll show you how it works. I should say that RSA is named for 00:04:32.541 --> 00:04:37.150 its inventors, Ron Rivest, Adi Shamir and Len Adleman, who were all at MIT at the 00:04:37.150 --> 00:04:41.758 time they made this important discovery. So now we're ready to describe the RSA 00:04:41.758 --> 00:04:46.425 trapdoor permutation. To do that, I have to describe the key generation algorithm, 00:04:46.425 --> 00:04:50.159 the function ƒ and the function ƒ−1. So let's see. So the way the key 00:04:50.159 --> 00:04:54.826 generation algorithm works is as follows: What we do is we generate two primes, P 00:04:54.826 --> 00:04:59.143 and Q, each would be, say on the order of 1000 bits, so, you know, roughly 300 00:04:59.143 --> 00:05:03.751 digits, and then the RSA modulus is simply going to be the product of those two 00:05:03.751 --> 00:05:08.801 primes. The next thing we do is we pick two exponents, e and d, such that e times 00:05:08.801 --> 00:05:13.894 d is 1 modulo phi(N). What this means is that e and d first of all are relatively 00:05:13.894 --> 00:05:19.051 prime to phi(N) and second of all they're actually modular inverses of one another, 00:05:19.051 --> 00:05:24.014 modulo phi(N). And then we output the public key as the pair N,e and the 00:05:24.014 --> 00:05:29.172 secret key is the secret key N,d. I should mention that the exponent e, 00:05:29.172 --> 00:05:34.586 that the number e is sometimes called the encryption exponent and the exponent d is 00:05:34.586 --> 00:05:39.135 sometimes called the decryption exponent. And you'll see why I keep referring to 00:05:39.135 --> 00:05:43.189 these as exponents in just a second. Now the way the RSA function itself is 00:05:43.189 --> 00:05:46.902 defined is really simple. For simplicity I'm gonna define it as the function 00:05:46.902 --> 00:05:51.801 from ZN star to ZN star. And the way the function is defined is simply given an 00:05:51.801 --> 00:05:57.001 input X, all we do is we simply take X and raise it to the power of e in ZN. So we 00:05:57.001 --> 00:06:02.137 just compute X to the e, modulo N. That's it. And then to decrypt, what we do is we 00:06:02.137 --> 00:06:07.451 simply, given an input Y, we simply raise Y to the power of d, modulo N. And that's 00:06:07.451 --> 00:06:12.483 it. So now you can see why as I refer to e and d as exponents. They're the things 00:06:12.483 --> 00:06:17.767 that X and Y are being raised to. So let's quickly verify that F inverse really does 00:06:17.767 --> 00:06:22.673 invert the function F. So let's see what happens when we compute Y to the d. So 00:06:22.673 --> 00:06:27.515 suppose Y itself happens to be the RSA function of some value X. In which case, 00:06:27.515 --> 00:06:33.045 what Y to the d is, is really RSA of X to the power of d. While X by itself is 00:06:33.045 --> 00:06:39.006 simply gonna be X to the e modulo N, And therefore, Y to the d is simply X to the e 00:06:39.006 --> 00:06:44.896 times d modulo N. Again, just using rules of exponentiation, the exponents multiply, 00:06:44.896 --> 00:06:50.857 so we get X to the e times d. But what do we know about e times d? e times d we said 00:06:50.857 --> 00:06:57.390 is one modulo phi(N). And what that means is there exists some integer such that e 00:06:57.390 --> 00:07:04.177 times d is equal to K times phi(N) plus one. This is what it means that e times d is 00:07:04.177 --> 00:07:09.820 one modulo phi(N). So, we can simply replace e times d by K times phi(N)+1. So, that's 00:07:09.820 --> 00:07:14.453 what I wrote here. So, we have X to the power of K times phi(N)+1. But now again 00:07:14.453 --> 00:07:19.868 just using rules of exponentiation, we can re-write this as X to the power of phi(N) to 00:07:19.868 --> 00:07:24.827 the power of K times X. This is really the same thing as K times phi(N)+1 as the 00:07:24.827 --> 00:07:29.917 exponent. I just kind of separated the exponent into it's different components. 00:07:29.917 --> 00:07:35.137 Now, X to the phi(N) by Euler's theorem, we know that X to the phi(N) is equal to one. So what 00:07:35.137 --> 00:07:41.394 is this whole product equal to? Well since X to the phi(N) is equal to one, one to 00:07:41.394 --> 00:07:45.961 the K is also equal to one, so this whole thing over here is simply equal to one. 00:07:45.961 --> 00:07:50.757 And what we're left with is X. So what we just proved is that if I take the output of 00:07:50.757 --> 00:07:55.210 the RSA function and raise it to the power of 'd', I get back X. Which means that 00:07:55.210 --> 00:07:59.663 raising to the power of 'd' basically inverts the RSA function, which is what we 00:07:59.663 --> 00:08:04.638 wanted to show. So that's it, that's the whole description of the function, we've 00:08:04.638 --> 00:08:08.972 described the key generation. The function itself, which is simply raising things to 00:08:08.972 --> 00:08:13.410 the power of e modulo N, and the inversion function which is simply raising things to 00:08:13.410 --> 00:08:17.483 the power of d, also modulo N. The next question is, why is this function secure? 00:08:17.483 --> 00:08:21.609 In other words, why is this function one way if all I have is just a public key, 00:08:21.609 --> 00:08:26.409 but I don't have the secret key? And so to argue that this function is one way we 00:08:26.409 --> 00:08:31.454 basically state the RSA assumption which basically says that the RSA function is a 00:08:31.454 --> 00:08:36.626 one way permutation. And formally the way we state that is that, basically for all 00:08:36.626 --> 00:08:41.416 efficient algorithms, A, it so happens that if I generate two primes p and q, 00:08:41.416 --> 00:08:46.397 random primes p and q. I multiply them to get to modulus N and then I choose a 00:08:46.397 --> 00:08:51.103 random 'y' in ZN star. And now I give the modulus, the exponent and this 'y' to 00:08:51.103 --> 00:08:55.893 algorithm A, the probability that I'll get the inverse of RSA at the point Y, mainly 00:08:55.893 --> 00:09:00.336 I'll get Y to the power of one over E. That's really what the inverse is. This 00:09:00.336 --> 00:09:04.606 probability is negligible. So this assumption is called the RSA assumption. 00:09:04.606 --> 00:09:09.338 It basically states that RSA is a one way permutation just given the public [key?]. And 00:09:09.338 --> 00:09:13.954 therefore, it is a trapdoor permutation because it has a trapdoor. And makes this 00:09:13.954 --> 00:09:19.501 easy to invert for anyone who knows the trap door. So now that we have a secure 00:09:19.501 --> 00:09:23.717 trap door permutation, we can simply plug that into our construction for public key 00:09:23.717 --> 00:09:27.826 encryption, and get our first real world public key encryption system. And so what 00:09:27.826 --> 00:09:32.362 we'll do is we'll simply plug the, the RSA trapdoor permutation into the iso standard 00:09:32.362 --> 00:09:36.151 construction that we saw in the previous segment. So, if you recall, that 00:09:36.151 --> 00:09:40.207 construction was based on a symmetric encryption system that had to provide 00:09:40.207 --> 00:09:44.438 authenticated encryption. And it was also based on a hash function. Then mapped 00:09:44.615 --> 00:09:48.866 while transferring it into the world of RSA, it maps elements in 00:09:48.866 --> 00:09:54.202 ZN, into secret keys for the symmetric key system. And now the 00:09:54.202 --> 00:09:58.947 way the encryption scheme works is really easy to describe. Basically algorithm G 00:09:58.947 --> 00:10:03.751 just runs the RSA key generation algorithm and produces a public key and a secret 00:10:03.751 --> 00:10:07.813 key. Just as before. So you notice the public key contains the encryption 00:10:07.813 --> 00:10:11.948 exponent and the, secret key contains the decryption exponent. And the way we 00:10:11.948 --> 00:10:16.298 encrypt is as follows. Well, we're going to choose a random X in ZN. We're going 00:10:16.298 --> 00:10:21.468 to apply the RSA function to this X, we're going to deduce a symmetric key from this 00:10:21.468 --> 00:10:26.453 X by hashing it, so we compute H of X to obtain the key K, and then we output this 00:10:26.453 --> 00:10:31.130 Y along with the encryption of the message under the symmetric key K. And in 00:10:31.130 --> 00:10:35.930 practice, the hash function H would be just implemented just using SHA-256, and 00:10:35.930 --> 00:10:40.977 you would use the output of SHA-256 to generate a symmetric key that could then 00:10:40.977 --> 00:10:45.687 be used for the symmetric encryption assistant. So that's how we would encrypt 00:10:45.687 --> 00:10:50.084 and then the way we would decrypt is pretty much as we saw in the previous 00:10:50.084 --> 00:10:54.951 segment, where the first thing we would do is we would use the secret key to invert 00:10:54.951 --> 00:10:59.758 the header of the ciphertext. So we would compute RSA invert of Y, that would give 00:10:59.758 --> 00:11:04.566 us the value X. Then we would apply the hash function to X so that this would give 00:11:04.566 --> 00:11:09.198 us the key K. And then we would run the decryption algorithm for the symmetric 00:11:09.198 --> 00:11:15.171 system on the ciphertext and that would produce the original message m. And then 00:11:15.171 --> 00:11:19.103 we stated a theorem in the previous segment to say that if the RSA trapdoor 00:11:19.103 --> 00:11:23.087 permutation is secure, Es and Ds, the symmetric encryption scheme [inaudible] 00:11:23.087 --> 00:11:27.175 provides authenticated encryption. And as we said, H is just random oracle. It's, 00:11:27.332 --> 00:11:31.421 you know, kind of a random function from ZN to the key space. Then, in fact, this 00:11:31.421 --> 00:11:35.720 system is chosen cipher text secure, and is a good public key system to use. 00:11:36.240 --> 00:11:41.729 So now that we have our first example of a good public key system to use, I wanna 00:11:41.729 --> 00:11:46.978 quickly warn you about how not to use RSA for encryption. And this again something 00:11:46.978 --> 00:11:51.101 that we said in the previous segment. And I'm going to repeat it here, except I'm 00:11:51.101 --> 00:11:55.534 going to make it specific to RSA. So I'd like to call this, textbook RSA. 00:11:55.534 --> 00:11:59.400 Which basically is the first thing that comes to mind when you think about 00:11:59.400 --> 00:12:03.678 encrypting using RSA, namely, the secret key and the public key will be as before. 00:12:03.678 --> 00:12:08.162 But now instead of running through, a hash function to generate a symmetric key, what 00:12:08.162 --> 00:12:12.337 we would do is we would directly use RSA to encrypt the given message M. And then 00:12:12.337 --> 00:12:16.202 we would directly use the decryption exponent to decrypt the cipher text and 00:12:16.202 --> 00:12:20.773 obtain the plain text M. I'm going to call this textbook RSA, because there are many 00:12:20.773 --> 00:12:25.350 textbooks that describe RSA encryption in this way. And this is completely wrong. 00:12:25.350 --> 00:12:29.495 This is not how RSA encryption works. It's an insecure system. In particular, 00:12:29.495 --> 00:12:33.936 it's deterministic encryption, and so it can't possibly be semantically secure, but 00:12:33.936 --> 00:12:38.542 in fact there are many attacks exist that I'm going to show you an attack in just a 00:12:38.542 --> 00:12:42.709 minute, but the message that I want to make clear here, is that RSA, all it is, 00:12:42.709 --> 00:12:47.151 is a trap door permutation. By itself it's not an encryption system. You have to 00:12:47.151 --> 00:12:51.427 embellish it with this ISO standard for example, to make it into an encryption 00:12:51.427 --> 00:12:55.826 system. By itself, all it is, is just a function. So let's see what goes wrong if 00:12:55.826 --> 00:13:00.225 you try to use textbook RSA, In other words, if you try to encrypt a message 00:13:00.225 --> 00:13:04.975 using RSA directly. And I'll give you an example attack from the world of the web. 00:13:04.975 --> 00:13:09.725 So imagine we have a web server. The web server has an RSA secret key. Here's it's 00:13:09.725 --> 00:13:14.738 denoted by N and D. And here we have a web browser who's trying to establish a secure 00:13:14.738 --> 00:13:19.124 session, a secure SSL session, with the web server. So the way SSL works is that the 00:13:19.124 --> 00:13:23.401 web browser starts off by sending this client hello message saying, hey, I want 00:13:23.401 --> 00:13:27.787 to set up a secure session with you. The web server responds with a server hello 00:13:27.787 --> 00:13:32.430 message that contains the server's public key And then the web browser will go ahead 00:13:32.430 --> 00:13:36.615 and generate a random what's called a premaster secret K, it will encrypt the 00:13:36.615 --> 00:13:40.692 premaster secret using K and send the result in ciphertext over to the web 00:13:40.692 --> 00:13:44.932 server. The web server will decrypt and then the web server will also get K, so 00:13:44.932 --> 00:13:49.336 now the two have a shared key that they can use to then secure a session between 00:13:49.336 --> 00:13:53.630 them. So I want to show you what goes wrong if we directly use the RSA function 00:13:53.630 --> 00:13:57.762 for encrypting K. In other words, if directly K is encrypted as K to the e 00:13:57.762 --> 00:14:02.828 modulo N. Just for the sake of argument let's suppose that K is a 64-bit key. 00:14:02.828 --> 00:14:08.097 We're going to treat K as an integer in the range as zero to 2 to the 64. 00:14:08.097 --> 00:14:13.100 More precisely two to the 64 minus one, and now what we're going to do is the 00:14:13.100 --> 00:14:18.302 following. First of all, suppose it so happens that K factors into a product of 00:14:18.302 --> 00:14:23.705 roughly equal sized numbers. So K we can write as K1 times K2, where K1 and K2 are 00:14:23.705 --> 00:14:29.745 integers. And both are say less than two to the 34. So, it turns out this happens 00:14:29.745 --> 00:14:34.508 with probability roughly twenty percent so one in five times K can actually be 00:14:34.508 --> 00:14:39.740 written in this way. But, now if we plug this K, K=K1 x K2 if we plug that into the 00:14:39.740 --> 00:14:45.241 equation that defines the cipher text you see that we can simply substitute K by K1 x k2 00:14:45.241 --> 00:14:50.875 and then we can move k1 to the other side. So then we end up with this equation here, 00:14:50.875 --> 00:14:55.897 namely C over K1 to the e is equal to K2 to the e. You notice if I multiply both 00:14:55.897 --> 00:15:00.659 sides by K1 to the e, I get that C is equal to K1 times K2 to the e, 00:15:00.659 --> 00:15:06.374 which is precisely this equation here. Okay, so all I did is I just replaced K by 00:15:06.374 --> 00:15:11.955 K1 times K2 and then divided by K1 to the e. So by now this should look familiar to 00:15:11.955 --> 00:15:16.146 you. So now we have two variables in this equation, of course. C is known to the 00:15:16.146 --> 00:15:20.092 attacker, E is known to the attacker, and N is known to the attacker. The two 00:15:20.092 --> 00:15:24.518 variables in this equation are K1 and K2, and we've separated them into a 00:15:24.518 --> 00:15:28.891 different side of the equation, and as a result we can do now a meet in the middle 00:15:28.891 --> 00:15:33.157 attack on this equation. So let's do the meet in the middle attack. What we would 00:15:33.157 --> 00:15:37.524 do is we would build a table of all possible values Of the left-hand side. So 00:15:37.524 --> 00:15:43.392 all possible values of C over K1 to the E, there are 2 to the 34 of them. And then, 00:15:43.584 --> 00:15:48.878 for all possible values on the right-hand side, [inaudible] for all possible values 00:15:48.878 --> 00:15:54.175 of K2 to the e, we're gonna check whether this value here lives in the table that we 00:15:54.175 --> 00:15:58.749 constructed in step one. And if it is then we found a collision, and basically we 00:15:58.749 --> 00:16:03.265 have a solution to this equation. So as soon as we find an element of the form K2 00:16:03.265 --> 00:16:07.962 to the E that lives in the table that we built in step one, we've solved this 00:16:07.962 --> 00:16:12.717 equation and we found K1 and K2. And of course once we found K1 and K2, 00:16:12.717 --> 00:16:16.950 we can easily recover K simply by multiplying them. So then we multiply K1 00:16:16.950 --> 00:16:21.428 and K2 and we get, the secret key K. Okay? So, we've broken, basically, 00:16:21.428 --> 00:16:25.604 this, this encryption system. And how long did it take? Well, by brute force, we 00:16:25.604 --> 00:16:29.890 could have broken it in time 2 to the 64, simply by trying all possible keys. But 00:16:29.890 --> 00:16:33.792 this attack, you notice, it took 2 to the 34 time for step number one. Well, it 00:16:33.792 --> 00:16:38.353 took a little bit more than 2 to the 34, 'cause we had to do these exponentiations. 00:16:38.518 --> 00:16:42.969 It took 2 to the 34 time for step two against slightly more than two to the 34 00:16:42.969 --> 00:16:47.530 because of the exponentiations. So let's say that the whole algorithm took time two 00:16:47.530 --> 00:16:52.277 to the 40. The point is that this is much, much less time due to the 64. So here you 00:16:52.277 --> 00:16:56.667 have an example. Where if you encrypt using RSA directly, in other words you 00:16:56.667 --> 00:17:01.296 directly compute, K to the E, mod N, instead of going through the ISO standard, 00:17:01.296 --> 00:17:05.983 for example, then you get an attack that runs much faster than exhaustive search. 00:17:05.983 --> 00:17:10.730 You get an attack that runs in time two to the 40, rather than time two to the 64. 00:17:10.730 --> 00:17:14.985 Okay, so this is a cute example of how things can break if you use the RSA 00:17:14.985 --> 00:17:19.299 trapdoor permutation directly to encrypt a message. So the message to 00:17:19.299 --> 00:17:23.670 remember here, is never, ever, ever use RSA directly to encrypt. You have to use to go 00:17:23.670 --> 00:17:27.868 through an encryption mechanism. For example, like the ISO standard. And in 00:17:27.868 --> 00:17:32.354 fact, in the next segment we are going to see other ways of using RSA to build 00:17:32.354 --> 00:17:33.620 public key encryption.