0:00

In the previous segment we saw how to build public key encryption from trapdoor

Â functions, in this segment we're going to build a classic trapdoor function called

Â RSA. But first let's quickly review what a trapdoor function is. So recall that a

Â trapdoor function is made up of three algorithms. There is a key generation

Â algorithm, the function itself, and the inverse of the function. The key

Â generation algorithm outputs a public key and a secret key. And in this case, in

Â this lecture the public key is going to define a function that maps the set X onto

Â itself. Which is why I call these things trapdoor permutations, as opposed to

Â trapdoor functions, simply because the function maps X onto itself, whereas a

Â trapdoor function might map the set X to some arbitrary set Y. Now given the public

Â key, the function, as we say, basically defines this function from the set X to

Â the set X. And then given the secret key, we can invert this function. So this

Â function F evaluates the function in the forward direction, and this function F

Â inverse, which means the secret key SK, computes F in the reverse direction. Now

Â we say that the trapdoor permutation is secure if the function defined by the

Â public key is in fact a one-way function, which means that it's easy to evaluate,

Â but without the trapdoor, the secret trapdoor, it's difficult to invert. Before

Â we look at our first example of a trapdoor permutation, I want to do a quick review

Â of some necessary arithmetic facts that we're gonna need. And in particular,

Â let's look at some arithmetic facts modulo composites. So here we have our

Â modulus N, which happens to be a product of two primes, and you should be thinking

Â of P and Q as roughly equal size numbers, since particular P and Q are both roughly

Â on the size of square root of N. So both are roughly the same size. Recall that we

Â denoted by ZN the set of integers from zero to N minus one, and we said that we

Â can do addition and multiplication module N. We denoted by ZN star the set of

Â invertible elements in ZN. So these are all the elements, which have a modular

Â inverse. And we said that actually X is invertible if and only if it's relatively

Â prime to N. Moreover, I also told you that the number of invertible elements in ZN

Â star is denoted by this function phi(N). So phi(N) is the number of invertible elements in ZN

Â star, And I told you that when N is a product of two distinct primes, then in

Â fact phi(N) is equal to (P - 1) times (Q - 1) and if you extend that out, you

Â see that this is really equal to (N - P - Q + 1). Now remember that I said

Â that P and Q are on the order of square root of N which means that P + Q is

Â also on the order of square root of N. Which means that really phi(N) is on the

Â order of N minus two square root of N. So, in other words, it's very, very close to

Â N. Basically, subtracting the square root of N from a number, this is from, N is

Â going to be a huge number in our case, like 600 digits. And so subtracting from a

Â 600 digit number, the square root of that 600 digit number, namely a 300 digit

Â number, hardly affects the size of the number. Which means that phi(N) is really,

Â really, really close to N, and I want you to remember that, because we will actually

Â be using this now and again. And so the fact that phi(N) is really close to N, means

Â that if we choose a random element modulo N It's very, very, very likely to be in ZN

Â star. So it's very unlikely that by choosing a random element in ZN, we will

Â end up choosing an element that is not invertable. Okay. So just remember that,

Â that in fact almost all elements in ZN are actually invertible. And the last thing

Â that we'll need is Euler's theorem, which we covered last week, which basically says

Â that for any element X in ZN star, if I raise X to the power of phi(N), I get one, in

Â ZN. So in other words, I get 1 modulo N. I'll say it one more time because this

Â is gonna be critical to what's coming. Again X to the phi(N) is equal to 1 modulo

Â N. So now that we have the necessary background we can actually describe the

Â RSA trapdoor permutation. This is a classic, classic, classic construction in

Â cryptography that was first published in Scientific American back in 1977, this is

Â a very well known article in cryptography. And ever since then, this was 35 years

Â ago, the RSA trapdoor permutation has been used extensively in cryptographic applications.

Â For example, SSL and TLS use RSA both for certificates and for key exchange. There

Â are many secure email systems and secure file systems that use RSA to encrypt

Â emails and encrypt files in the file system. And there are many, many, many

Â other applications of this system. So this is a very, very classic, crypto

Â construction, and I'll show you how it works. I should say that RSA is named for

Â its inventors, Ron Rivest, Adi Shamir and Len Adleman, who were all at MIT at the

Â time they made this important discovery. So now we're ready to describe the RSA

Â trapdoor permutation. To do that, I have to describe the key generation algorithm,

Â the function Æ’ and the function Æ’âˆ’1. So let's see. So the way the key

Â generation algorithm works is as follows: What we do is we generate two primes, P

Â and Q, each would be, say on the order of 1000 bits, so, you know, roughly 300

Â digits, and then the RSA modulus is simply going to be the product of those two

Â primes. The next thing we do is we pick two exponents, e and d, such that e times

Â d is 1 modulo phi(N). What this means is that e and d first of all are relatively

Â prime to phi(N) and second of all they're actually modular inverses of one another,

Â modulo phi(N). And then we output the public key as the pair N,e and the

Â secret key is the secret key N,d. I should mention that the exponent e,

Â that the number e is sometimes called the encryption exponent and the exponent d is

Â sometimes called the decryption exponent. And you'll see why I keep referring to

Â these as exponents in just a second. Now the way the RSA function itself is

Â defined is really simple. For simplicity I'm gonna define it as the function

Â from ZN star to ZN star. And the way the function is defined is simply given an

Â input X, all we do is we simply take X and raise it to the power of e in ZN. So we

Â just compute X to the e, modulo N. That's it. And then to decrypt, what we do is we

Â simply, given an input Y, we simply raise Y to the power of d, modulo N. And that's

Â it. So now you can see why as I refer to e and d as exponents. They're the things

Â that X and Y are being raised to. So let's quickly verify that F inverse really does

Â invert the function F. So let's see what happens when we compute Y to the d. So

Â suppose Y itself happens to be the RSA function of some value X. In which case,

Â what Y to the d is, is really RSA of X to the power of d. While X by itself is

Â simply gonna be X to the e modulo N, And therefore, Y to the d is simply X to the e

Â times d modulo N. Again, just using rules of exponentiation, the exponents multiply,

Â so we get X to the e times d. But what do we know about e times d? e times d we said

Â is one modulo phi(N). And what that means is there exists some integer such that e

Â times d is equal to K times phi(N) plus one. This is what it means that e times d is

Â one modulo phi(N). So, we can simply replace e times d by K times phi(N)+1. So, that's

Â what I wrote here. So, we have X to the power of K times phi(N)+1. But now again

Â just using rules of exponentiation, we can re-write this as X to the power of phi(N) to

Â the power of K times X. This is really the same thing as K times phi(N)+1 as the

Â exponent. I just kind of separated the exponent into it's different components.

Â Now, X to the phi(N) by Euler's theorem, we know that X to the phi(N) is equal to one. So what

Â is this whole product equal to? Well since X to the phi(N) is equal to one, one to

Â the K is also equal to one, so this whole thing over here is simply equal to one.

Â And what we're left with is X. So what we just proved is that if I take the output of

Â the RSA function and raise it to the power of 'd', I get back X. Which means that

Â raising to the power of 'd' basically inverts the RSA function, which is what we

Â wanted to show. So that's it, that's the whole description of the function, we've

Â described the key generation. The function itself, which is simply raising things to

Â the power of e modulo N, and the inversion function which is simply raising things to

Â the power of d, also modulo N. The next question is, why is this function secure?

Â In other words, why is this function one way if all I have is just a public key,

Â but I don't have the secret key? And so to argue that this function is one way we

Â basically state the RSA assumption which basically says that the RSA function is a

Â one way permutation. And formally the way we state that is that, basically for all

Â efficient algorithms, A, it so happens that if I generate two primes p and q,

Â random primes p and q. I multiply them to get to modulus N and then I choose a

Â random 'y' in ZN star. And now I give the modulus, the exponent and this 'y' to

Â algorithm A, the probability that I'll get the inverse of RSA at the point Y, mainly

Â I'll get Y to the power of one over E. That's really what the inverse is. This

Â probability is negligible. So this assumption is called the RSA assumption.

Â It basically states that RSA is a one way permutation just given the public [key?]. And

Â therefore, it is a trapdoor permutation because it has a trapdoor. And makes this

Â easy to invert for anyone who knows the trap door. So now that we have a secure

Â trap door permutation, we can simply plug that into our construction for public key

Â encryption, and get our first real world public key encryption system. And so what

Â we'll do is we'll simply plug the, the RSA trapdoor permutation into the iso standard

Â construction that we saw in the previous segment. So, if you recall, that

Â construction was based on a symmetric encryption system that had to provide

Â authenticated encryption. And it was also based on a hash function. Then mapped

Â while transferring it into the world of RSA, it maps elements in

Â ZN, into secret keys for the symmetric key system. And now the

Â way the encryption scheme works is really easy to describe. Basically algorithm G

Â just runs the RSA key generation algorithm and produces a public key and a secret

Â key. Just as before. So you notice the public key contains the encryption

Â exponent and the, secret key contains the decryption exponent. And the way we

Â encrypt is as follows. Well, we're going to choose a random X in ZN. We're going

Â to apply the RSA function to this X, we're going to deduce a symmetric key from this

Â X by hashing it, so we compute H of X to obtain the key K, and then we output this

Â Y along with the encryption of the message under the symmetric key K. And in

Â practice, the hash function H would be just implemented just using SHA-256, and

Â you would use the output of SHA-256 to generate a symmetric key that could then

Â be used for the symmetric encryption assistant. So that's how we would encrypt

Â and then the way we would decrypt is pretty much as we saw in the previous

Â segment, where the first thing we would do is we would use the secret key to invert

Â the header of the ciphertext. So we would compute RSA invert of Y, that would give

Â us the value X. Then we would apply the hash function to X so that this would give

Â us the key K. And then we would run the decryption algorithm for the symmetric

Â system on the ciphertext and that would produce the original message m. And then

Â we stated a theorem in the previous segment to say that if the RSA trapdoor

Â permutation is secure, Es and Ds, the symmetric encryption scheme [inaudible]

Â provides authenticated encryption. And as we said, H is just random oracle. It's,

Â you know, kind of a random function from ZN to the key space. Then, in fact, this

Â system is chosen cipher text secure, and is a good public key system to use.

Â 11:36

So now that we have our first example of a good public key system to use, I wanna

Â quickly warn you about how not to use RSA for encryption. And this again something

Â that we said in the previous segment. And I'm going to repeat it here, except I'm

Â going to make it specific to RSA. So I'd like to call this, textbook RSA.

Â Which basically is the first thing that comes to mind when you think about

Â encrypting using RSA, namely, the secret key and the public key will be as before.

Â But now instead of running through, a hash function to generate a symmetric key, what

Â we would do is we would directly use RSA to encrypt the given message M. And then

Â we would directly use the decryption exponent to decrypt the cipher text and

Â obtain the plain text M. I'm going to call this textbook RSA, because there are many

Â textbooks that describe RSA encryption in this way. And this is completely wrong.

Â This is not how RSA encryption works. It's an insecure system. In particular,

Â it's deterministic encryption, and so it can't possibly be semantically secure, but

Â in fact there are many attacks exist that I'm going to show you an attack in just a

Â minute, but the message that I want to make clear here, is that RSA, all it is,

Â is a trap door permutation. By itself it's not an encryption system. You have to

Â embellish it with this ISO standard for example, to make it into an encryption

Â system. By itself, all it is, is just a function. So let's see what goes wrong if

Â you try to use textbook RSA, In other words, if you try to encrypt a message

Â using RSA directly. And I'll give you an example attack from the world of the web.

Â So imagine we have a web server. The web server has an RSA secret key. Here's it's

Â denoted by N and D. And here we have a web browser who's trying to establish a secure

Â session, a secure SSL session, with the web server. So the way SSL works is that the

Â web browser starts off by sending this client hello message saying, hey, I want

Â to set up a secure session with you. The web server responds with a server hello

Â message that contains the server's public key And then the web browser will go ahead

Â and generate a random what's called a premaster secret K, it will encrypt the

Â premaster secret using K and send the result in ciphertext over to the web

Â server. The web server will decrypt and then the web server will also get K, so

Â now the two have a shared key that they can use to then secure a session between

Â them. So I want to show you what goes wrong if we directly use the RSA function

Â for encrypting K. In other words, if directly K is encrypted as K to the e

Â modulo N. Just for the sake of argument let's suppose that K is a 64-bit key.

Â We're going to treat K as an integer in the range as zero to 2 to the 64.

Â More precisely two to the 64 minus one, and now what we're going to do is the

Â following. First of all, suppose it so happens that K factors into a product of

Â roughly equal sized numbers. So K we can write as K1 times K2, where K1 and K2 are

Â integers. And both are say less than two to the 34. So, it turns out this happens

Â with probability roughly twenty percent so one in five times K can actually be

Â written in this way. But, now if we plug this K, K=K1 x K2 if we plug that into the

Â equation that defines the cipher text you see that we can simply substitute K by K1 x k2

Â and then we can move k1 to the other side. So then we end up with this equation here,

Â namely C over K1 to the e is equal to K2 to the e. You notice if I multiply both

Â sides by K1 to the e, I get that C is equal to K1 times K2 to the e,

Â which is precisely this equation here. Okay, so all I did is I just replaced K by

Â K1 times K2 and then divided by K1 to the e. So by now this should look familiar to

Â you. So now we have two variables in this equation, of course. C is known to the

Â attacker, E is known to the attacker, and N is known to the attacker. The two

Â variables in this equation are K1 and K2, and we've separated them into a

Â different side of the equation, and as a result we can do now a meet in the middle

Â attack on this equation. So let's do the meet in the middle attack. What we would

Â do is we would build a table of all possible values Of the left-hand side. So

Â all possible values of C over K1 to the E, there are 2 to the 34 of them. And then,

Â for all possible values on the right-hand side, [inaudible] for all possible values

Â of K2 to the e, we're gonna check whether this value here lives in the table that we

Â constructed in step one. And if it is then we found a collision, and basically we

Â have a solution to this equation. So as soon as we find an element of the form K2

Â to the E that lives in the table that we built in step one, we've solved this

Â equation and we found K1 and K2. And of course once we found K1 and K2,

Â we can easily recover K simply by multiplying them. So then we multiply K1

Â and K2 and we get, the secret key K. Okay? So, we've broken, basically,

Â this, this encryption system. And how long did it take? Well, by brute force, we

Â could have broken it in time 2 to the 64, simply by trying all possible keys. But

Â this attack, you notice, it took 2 to the 34 time for step number one. Well, it

Â took a little bit more than 2 to the 34, 'cause we had to do these exponentiations.

Â It took 2 to the 34 time for step two against slightly more than two to the 34

Â because of the exponentiations. So let's say that the whole algorithm took time two

Â to the 40. The point is that this is much, much less time due to the 64. So here you

Â have an example. Where if you encrypt using RSA directly, in other words you

Â directly compute, K to the E, mod N, instead of going through the ISO standard,

Â for example, then you get an attack that runs much faster than exhaustive search.

Â You get an attack that runs in time two to the 40, rather than time two to the 64.

Â Okay, so this is a cute example of how things can break if you use the RSA

Â trapdoor permutation directly to encrypt a message. So the message to

Â remember here, is never, ever, ever use RSA directly to encrypt. You have to use to go

Â through an encryption mechanism. For example, like the ISO standard. And in

Â fact, in the next segment we are going to see other ways of using RSA to build

Â public key encryption.

Â