[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.09,Default,,0000,0000,0000,,In the previous segment we saw how to\Nbuild public key encryption from trapdoor
Dialogue: 0,0:00:04.09,0:00:08.39,Default,,0000,0000,0000,,functions, in this segment we're going to\Nbuild a classic trapdoor function called
Dialogue: 0,0:00:08.39,0:00:13.30,Default,,0000,0000,0000,,RSA. But first let's quickly review what a\Ntrapdoor function is. So recall that a
Dialogue: 0,0:00:13.30,0:00:17.28,Default,,0000,0000,0000,,trapdoor function is made up of three\Nalgorithms. There is a key generation
Dialogue: 0,0:00:17.28,0:00:21.06,Default,,0000,0000,0000,,algorithm, the function itself, and the\Ninverse of the function. The key
Dialogue: 0,0:00:21.06,0:00:25.31,Default,,0000,0000,0000,,generation algorithm outputs a public key\Nand a secret key. And in this case, in
Dialogue: 0,0:00:25.31,0:00:29.79,Default,,0000,0000,0000,,this lecture the public key is going to\Ndefine a function that maps the set X onto
Dialogue: 0,0:00:29.79,0:00:33.88,Default,,0000,0000,0000,,itself. Which is why I call these things\Ntrapdoor permutations, as opposed to
Dialogue: 0,0:00:33.88,0:00:37.98,Default,,0000,0000,0000,,trapdoor functions, simply because the\Nfunction maps X onto itself, whereas a
Dialogue: 0,0:00:37.98,0:00:43.36,Default,,0000,0000,0000,,trapdoor function might map the set X to\Nsome arbitrary set Y. Now given the public
Dialogue: 0,0:00:43.36,0:00:47.82,Default,,0000,0000,0000,,key, the function, as we say, basically\Ndefines this function from the set X to
Dialogue: 0,0:00:47.82,0:00:52.91,Default,,0000,0000,0000,,the set X. And then given the secret key,\Nwe can invert this function. So this
Dialogue: 0,0:00:52.91,0:00:57.40,Default,,0000,0000,0000,,function F evaluates the function in the\Nforward direction, and this function F
Dialogue: 0,0:00:57.40,0:01:02.06,Default,,0000,0000,0000,,inverse, which means the secret key SK,\Ncomputes F in the reverse direction. Now
Dialogue: 0,0:01:02.06,0:01:06.49,Default,,0000,0000,0000,,we say that the trapdoor permutation is\Nsecure if the function defined by the
Dialogue: 0,0:01:06.49,0:01:11.03,Default,,0000,0000,0000,,public key is in fact a one-way function,\Nwhich means that it's easy to evaluate,
Dialogue: 0,0:01:11.03,0:01:15.40,Default,,0000,0000,0000,,but without the trapdoor, the secret\Ntrapdoor, it's difficult to invert. Before
Dialogue: 0,0:01:15.40,0:01:20.08,Default,,0000,0000,0000,,we look at our first example of a trapdoor\Npermutation, I want to do a quick review
Dialogue: 0,0:01:20.08,0:01:24.47,Default,,0000,0000,0000,,of some necessary arithmetic facts that\Nwe're gonna need. And in particular,
Dialogue: 0,0:01:24.47,0:01:28.63,Default,,0000,0000,0000,,let's look at some arithmetic facts\Nmodulo composites. So here we have our
Dialogue: 0,0:01:28.63,0:01:33.19,Default,,0000,0000,0000,,modulus N, which happens to be a product\Nof two primes, and you should be thinking
Dialogue: 0,0:01:33.19,0:01:37.86,Default,,0000,0000,0000,,of P and Q as roughly equal size numbers,\Nsince particular P and Q are both roughly
Dialogue: 0,0:01:37.86,0:01:42.41,Default,,0000,0000,0000,,on the size of square root of N. So both\Nare roughly the same size. Recall that we
Dialogue: 0,0:01:42.41,0:01:46.83,Default,,0000,0000,0000,,denoted by ZN the set of integers from\Nzero to N minus one, and we said that we
Dialogue: 0,0:01:46.83,0:01:51.32,Default,,0000,0000,0000,,can do addition and multiplication module N. We denoted by ZN star the set of
Dialogue: 0,0:01:51.32,0:01:55.80,Default,,0000,0000,0000,,invertible elements in ZN. So these are\Nall the elements, which have a modular
Dialogue: 0,0:01:55.80,0:02:00.92,Default,,0000,0000,0000,,inverse. And we said that actually X is\Ninvertible if and only if it's relatively
Dialogue: 0,0:02:00.92,0:02:05.93,Default,,0000,0000,0000,,prime to N. Moreover, I also told you that\Nthe number of invertible elements in ZN
Dialogue: 0,0:02:05.93,0:02:11.15,Default,,0000,0000,0000,,star is denoted by this function phi(N). So phi(N)\Nis the number of invertible elements in ZN
Dialogue: 0,0:02:11.15,0:02:15.81,Default,,0000,0000,0000,,star, And I told you that when N is a\Nproduct of two distinct primes, then in
Dialogue: 0,0:02:15.81,0:02:20.79,Default,,0000,0000,0000,,fact phi(N) is equal to (P - 1) times (Q - 1) and if you extend that out, you
Dialogue: 0,0:02:20.79,0:02:26.01,Default,,0000,0000,0000,,see that this is really equal to (N - P - Q + 1). Now remember that I said
Dialogue: 0,0:02:26.01,0:02:30.86,Default,,0000,0000,0000,,that P and Q are on the order of square\Nroot of N which means that P + Q is
Dialogue: 0,0:02:30.86,0:02:35.68,Default,,0000,0000,0000,,also on the order of square root of N.\NWhich means that really phi(N) is on the
Dialogue: 0,0:02:35.68,0:02:41.05,Default,,0000,0000,0000,,order of N minus two square root of N. So,\Nin other words, it's very, very close to
Dialogue: 0,0:02:41.05,0:02:45.16,Default,,0000,0000,0000,,N. Basically, subtracting the square root\Nof N from a number, this is from, N is
Dialogue: 0,0:02:45.16,0:02:49.42,Default,,0000,0000,0000,,going to be a huge number in our case,\Nlike 600 digits. And so subtracting from a
Dialogue: 0,0:02:49.42,0:02:53.53,Default,,0000,0000,0000,,600 digit number, the square root of that\N600 digit number, namely a 300 digit
Dialogue: 0,0:02:53.53,0:02:57.53,Default,,0000,0000,0000,,number, hardly affects the size of the\Nnumber. Which means that phi(N) is really,
Dialogue: 0,0:02:57.53,0:03:01.91,Default,,0000,0000,0000,,really, really close to N, and I want you\Nto remember that, because we will actually
Dialogue: 0,0:03:01.91,0:03:06.12,Default,,0000,0000,0000,,be using this now and again. And so the\Nfact that phi(N) is really close to N, means
Dialogue: 0,0:03:06.12,0:03:11.09,Default,,0000,0000,0000,,that if we choose a random element modulo\NN It's very, very, very likely to be in ZN
Dialogue: 0,0:03:11.09,0:03:15.63,Default,,0000,0000,0000,,star. So it's very unlikely that by\Nchoosing a random element in ZN, we will
Dialogue: 0,0:03:15.63,0:03:20.08,Default,,0000,0000,0000,,end up choosing an element that is not\Ninvertable. Okay. So just remember that,
Dialogue: 0,0:03:20.08,0:03:25.48,Default,,0000,0000,0000,,that in fact almost all elements in ZN are\Nactually invertible. And the last thing
Dialogue: 0,0:03:25.48,0:03:30.94,Default,,0000,0000,0000,,that we'll need is Euler's theorem, which\Nwe covered last week, which basically says
Dialogue: 0,0:03:30.94,0:03:36.33,Default,,0000,0000,0000,,that for any element X in ZN star, if I\Nraise X to the power of phi(N), I get one, in
Dialogue: 0,0:03:36.33,0:03:42.53,Default,,0000,0000,0000,,ZN. So in other words, I get 1 modulo N. I'll say it one more time because this
Dialogue: 0,0:03:42.53,0:03:47.47,Default,,0000,0000,0000,,is gonna be critical to what's coming.\NAgain X to the phi(N) is equal to 1 modulo
Dialogue: 0,0:03:47.47,0:03:51.100,Default,,0000,0000,0000,,N. So now that we have the necessary\Nbackground we can actually describe the
Dialogue: 0,0:03:51.100,0:03:55.93,Default,,0000,0000,0000,,RSA trapdoor permutation. This is a classic,\Nclassic, classic construction in
Dialogue: 0,0:03:55.93,0:04:00.81,Default,,0000,0000,0000,,cryptography that was first published in\NScientific American back in 1977, this is
Dialogue: 0,0:04:00.81,0:04:05.58,Default,,0000,0000,0000,,a very well known article in cryptography.\NAnd ever since then, this was 35 years
Dialogue: 0,0:04:05.58,0:04:10.34,Default,,0000,0000,0000,,ago, the RSA trapdoor permutation has been used\Nextensively in cryptographic applications.
Dialogue: 0,0:04:10.34,0:04:15.11,Default,,0000,0000,0000,,For example, SSL and TLS use RSA both for\Ncertificates and for key exchange. There
Dialogue: 0,0:04:15.11,0:04:19.45,Default,,0000,0000,0000,,are many secure email systems and secure\Nfile systems that use RSA to encrypt
Dialogue: 0,0:04:19.45,0:04:23.52,Default,,0000,0000,0000,,emails and encrypt files in the file\Nsystem. And there are many, many, many
Dialogue: 0,0:04:23.52,0:04:27.69,Default,,0000,0000,0000,,other applications of this system. So this\Nis a very, very classic, crypto
Dialogue: 0,0:04:27.69,0:04:32.54,Default,,0000,0000,0000,,construction, and I'll show you how it\Nworks. I should say that RSA is named for
Dialogue: 0,0:04:32.54,0:04:37.15,Default,,0000,0000,0000,,its inventors, Ron Rivest, Adi Shamir and\NLen Adleman, who were all at MIT at the
Dialogue: 0,0:04:37.15,0:04:41.76,Default,,0000,0000,0000,,time they made this important discovery.\NSo now we're ready to describe the RSA
Dialogue: 0,0:04:41.76,0:04:46.42,Default,,0000,0000,0000,,trapdoor permutation. To do that, I have\Nto describe the key generation algorithm,
Dialogue: 0,0:04:46.42,0:04:50.16,Default,,0000,0000,0000,,the function ƒ and the function ƒ−1.\NSo let's see. So the way the key
Dialogue: 0,0:04:50.16,0:04:54.83,Default,,0000,0000,0000,,generation algorithm works is as follows:\NWhat we do is we generate two primes, P
Dialogue: 0,0:04:54.83,0:04:59.14,Default,,0000,0000,0000,,and Q, each would be, say on the order of\N1000 bits, so, you know, roughly 300
Dialogue: 0,0:04:59.14,0:05:03.75,Default,,0000,0000,0000,,digits, and then the RSA modulus is simply\Ngoing to be the product of those two
Dialogue: 0,0:05:03.75,0:05:08.80,Default,,0000,0000,0000,,primes. The next thing we do is we pick\Ntwo exponents, e and d, such that e times
Dialogue: 0,0:05:08.80,0:05:13.89,Default,,0000,0000,0000,,d is 1 modulo phi(N). What this means is\Nthat e and d first of all are relatively
Dialogue: 0,0:05:13.89,0:05:19.05,Default,,0000,0000,0000,,prime to phi(N) and second of all they're\Nactually modular inverses of one another,
Dialogue: 0,0:05:19.05,0:05:24.01,Default,,0000,0000,0000,,modulo phi(N). And then we output the public\Nkey as the pair N,e and the
Dialogue: 0,0:05:24.01,0:05:29.17,Default,,0000,0000,0000,,secret key is the secret key N,d. I should mention that the exponent e,
Dialogue: 0,0:05:29.17,0:05:34.59,Default,,0000,0000,0000,,that the number e is sometimes called the\Nencryption exponent and the exponent d is
Dialogue: 0,0:05:34.59,0:05:39.14,Default,,0000,0000,0000,,sometimes called the decryption exponent.\NAnd you'll see why I keep referring to
Dialogue: 0,0:05:39.14,0:05:43.19,Default,,0000,0000,0000,,these as exponents in just a second. Now\Nthe way the RSA function itself is
Dialogue: 0,0:05:43.19,0:05:46.90,Default,,0000,0000,0000,,defined is really simple. For simplicity\NI'm gonna define it as the function
Dialogue: 0,0:05:46.90,0:05:51.80,Default,,0000,0000,0000,,from ZN star to ZN star. And the way\Nthe function is defined is simply given an
Dialogue: 0,0:05:51.80,0:05:57.00,Default,,0000,0000,0000,,input X, all we do is we simply take X and\Nraise it to the power of e in ZN. So we
Dialogue: 0,0:05:57.00,0:06:02.14,Default,,0000,0000,0000,,just compute X to the e, modulo N. That's\Nit. And then to decrypt, what we do is we
Dialogue: 0,0:06:02.14,0:06:07.45,Default,,0000,0000,0000,,simply, given an input Y, we simply raise\NY to the power of d, modulo N. And that's
Dialogue: 0,0:06:07.45,0:06:12.48,Default,,0000,0000,0000,,it. So now you can see why as I refer to e\Nand d as exponents. They're the things
Dialogue: 0,0:06:12.48,0:06:17.77,Default,,0000,0000,0000,,that X and Y are being raised to. So let's\Nquickly verify that F inverse really does
Dialogue: 0,0:06:17.77,0:06:22.67,Default,,0000,0000,0000,,invert the function F. So let's see what\Nhappens when we compute Y to the d. So
Dialogue: 0,0:06:22.67,0:06:27.52,Default,,0000,0000,0000,,suppose Y itself happens to be the RSA\Nfunction of some value X. In which case,
Dialogue: 0,0:06:27.52,0:06:33.04,Default,,0000,0000,0000,,what Y to the d is, is really RSA of X to\Nthe power of d. While X by itself is
Dialogue: 0,0:06:33.04,0:06:39.01,Default,,0000,0000,0000,,simply gonna be X to the e modulo N, And\Ntherefore, Y to the d is simply X to the e
Dialogue: 0,0:06:39.01,0:06:44.90,Default,,0000,0000,0000,,times d modulo N. Again, just using rules\Nof exponentiation, the exponents multiply,
Dialogue: 0,0:06:44.90,0:06:50.86,Default,,0000,0000,0000,,so we get X to the e times d. But what do\Nwe know about e times d? e times d we said
Dialogue: 0,0:06:50.86,0:06:57.39,Default,,0000,0000,0000,,is one modulo phi(N). And what that means is\Nthere exists some integer such that e
Dialogue: 0,0:06:57.39,0:07:04.18,Default,,0000,0000,0000,,times d is equal to K times phi(N) plus one.\NThis is what it means that e times d is
Dialogue: 0,0:07:04.18,0:07:09.82,Default,,0000,0000,0000,,one modulo phi(N). So, we can simply replace e\Ntimes d by K times phi(N)+1. So, that's
Dialogue: 0,0:07:09.82,0:07:14.45,Default,,0000,0000,0000,,what I wrote here. So, we have X to the\Npower of K times phi(N)+1. But now again
Dialogue: 0,0:07:14.45,0:07:19.87,Default,,0000,0000,0000,,just using rules of exponentiation, we can\Nre-write this as X to the power of phi(N) to
Dialogue: 0,0:07:19.87,0:07:24.83,Default,,0000,0000,0000,,the power of K times X. This is really the\Nsame thing as K times phi(N)+1 as the
Dialogue: 0,0:07:24.83,0:07:29.92,Default,,0000,0000,0000,,exponent. I just kind of separated the\Nexponent into it's different components.
Dialogue: 0,0:07:29.92,0:07:35.14,Default,,0000,0000,0000,,Now, X to the phi(N) by Euler's theorem, we know\Nthat X to the phi(N) is equal to one. So what
Dialogue: 0,0:07:35.14,0:07:41.39,Default,,0000,0000,0000,,is this whole product equal to? Well since\NX to the phi(N) is equal to one, one to
Dialogue: 0,0:07:41.39,0:07:45.96,Default,,0000,0000,0000,,the K is also equal to one, so this whole\Nthing over here is simply equal to one.
Dialogue: 0,0:07:45.96,0:07:50.76,Default,,0000,0000,0000,,And what we're left with is X. So what we\Njust proved is that if I take the output of
Dialogue: 0,0:07:50.76,0:07:55.21,Default,,0000,0000,0000,,the RSA function and raise it to the power\Nof 'd', I get back X. Which means that
Dialogue: 0,0:07:55.21,0:07:59.66,Default,,0000,0000,0000,,raising to the power of 'd' basically\Ninverts the RSA function, which is what we
Dialogue: 0,0:07:59.66,0:08:04.64,Default,,0000,0000,0000,,wanted to show. So that's it, that's the\Nwhole description of the function, we've
Dialogue: 0,0:08:04.64,0:08:08.97,Default,,0000,0000,0000,,described the key generation. The function\Nitself, which is simply raising things to
Dialogue: 0,0:08:08.97,0:08:13.41,Default,,0000,0000,0000,,the power of e modulo N, and the inversion\Nfunction which is simply raising things to
Dialogue: 0,0:08:13.41,0:08:17.48,Default,,0000,0000,0000,,the power of d, also modulo N. The next\Nquestion is, why is this function secure?
Dialogue: 0,0:08:17.48,0:08:21.61,Default,,0000,0000,0000,,In other words, why is this function one\Nway if all I have is just a public key,
Dialogue: 0,0:08:21.61,0:08:26.41,Default,,0000,0000,0000,,but I don't have the secret key? And so to\Nargue that this function is one way we
Dialogue: 0,0:08:26.41,0:08:31.45,Default,,0000,0000,0000,,basically state the RSA assumption which\Nbasically says that the RSA function is a
Dialogue: 0,0:08:31.45,0:08:36.63,Default,,0000,0000,0000,,one way permutation. And formally the way\Nwe state that is that, basically for all
Dialogue: 0,0:08:36.63,0:08:41.42,Default,,0000,0000,0000,,efficient algorithms, A, it so happens\Nthat if I generate two primes p and q,
Dialogue: 0,0:08:41.42,0:08:46.40,Default,,0000,0000,0000,,random primes p and q. I multiply them to\Nget to modulus N and then I choose a
Dialogue: 0,0:08:46.40,0:08:51.10,Default,,0000,0000,0000,,random 'y' in ZN star. And now I give\Nthe modulus, the exponent and this 'y' to
Dialogue: 0,0:08:51.10,0:08:55.89,Default,,0000,0000,0000,,algorithm A, the probability that I'll get\Nthe inverse of RSA at the point Y, mainly
Dialogue: 0,0:08:55.89,0:09:00.34,Default,,0000,0000,0000,,I'll get Y to the power of one over E.\NThat's really what the inverse is. This
Dialogue: 0,0:09:00.34,0:09:04.61,Default,,0000,0000,0000,,probability is negligible. So this\Nassumption is called the RSA assumption.
Dialogue: 0,0:09:04.61,0:09:09.34,Default,,0000,0000,0000,,It basically states that RSA is a one way\Npermutation just given the public [key?]. And
Dialogue: 0,0:09:09.34,0:09:13.95,Default,,0000,0000,0000,,therefore, it is a trapdoor permutation\Nbecause it has a trapdoor. And makes this
Dialogue: 0,0:09:13.95,0:09:19.50,Default,,0000,0000,0000,,easy to invert for anyone who knows the\Ntrap door. So now that we have a secure
Dialogue: 0,0:09:19.50,0:09:23.72,Default,,0000,0000,0000,,trap door permutation, we can simply plug\Nthat into our construction for public key
Dialogue: 0,0:09:23.72,0:09:27.83,Default,,0000,0000,0000,,encryption, and get our first real world\Npublic key encryption system. And so what
Dialogue: 0,0:09:27.83,0:09:32.36,Default,,0000,0000,0000,,we'll do is we'll simply plug the, the RSA\Ntrapdoor permutation into the iso standard
Dialogue: 0,0:09:32.36,0:09:36.15,Default,,0000,0000,0000,,construction that we saw in the previous\Nsegment. So, if you recall, that
Dialogue: 0,0:09:36.15,0:09:40.21,Default,,0000,0000,0000,,construction was based on a symmetric\Nencryption system that had to provide
Dialogue: 0,0:09:40.21,0:09:44.44,Default,,0000,0000,0000,,authenticated encryption. And it was also\Nbased on a hash function. Then mapped
Dialogue: 0,0:09:44.62,0:09:48.87,Default,,0000,0000,0000,,while transferring it into the world of\NRSA, it maps elements in
Dialogue: 0,0:09:48.87,0:09:54.20,Default,,0000,0000,0000,,ZN, into secret keys for the\Nsymmetric key system. And now the
Dialogue: 0,0:09:54.20,0:09:58.95,Default,,0000,0000,0000,,way the encryption scheme works is really\Neasy to describe. Basically algorithm G
Dialogue: 0,0:09:58.95,0:10:03.75,Default,,0000,0000,0000,,just runs the RSA key generation algorithm\Nand produces a public key and a secret
Dialogue: 0,0:10:03.75,0:10:07.81,Default,,0000,0000,0000,,key. Just as before. So you notice the\Npublic key contains the encryption
Dialogue: 0,0:10:07.81,0:10:11.95,Default,,0000,0000,0000,,exponent and the, secret key contains the\Ndecryption exponent. And the way we
Dialogue: 0,0:10:11.95,0:10:16.30,Default,,0000,0000,0000,,encrypt is as follows. Well, we're going\Nto choose a random X in ZN. We're going
Dialogue: 0,0:10:16.30,0:10:21.47,Default,,0000,0000,0000,,to apply the RSA function to this X, we're\Ngoing to deduce a symmetric key from this
Dialogue: 0,0:10:21.47,0:10:26.45,Default,,0000,0000,0000,,X by hashing it, so we compute H of X to\Nobtain the key K, and then we output this
Dialogue: 0,0:10:26.45,0:10:31.13,Default,,0000,0000,0000,,Y along with the encryption of the message\Nunder the symmetric key K. And in
Dialogue: 0,0:10:31.13,0:10:35.93,Default,,0000,0000,0000,,practice, the hash function H would be\Njust implemented just using SHA-256, and
Dialogue: 0,0:10:35.93,0:10:40.98,Default,,0000,0000,0000,,you would use the output of SHA-256 to\Ngenerate a symmetric key that could then
Dialogue: 0,0:10:40.98,0:10:45.69,Default,,0000,0000,0000,,be used for the symmetric encryption\Nassistant. So that's how we would encrypt
Dialogue: 0,0:10:45.69,0:10:50.08,Default,,0000,0000,0000,,and then the way we would decrypt is\Npretty much as we saw in the previous
Dialogue: 0,0:10:50.08,0:10:54.95,Default,,0000,0000,0000,,segment, where the first thing we would do\Nis we would use the secret key to invert
Dialogue: 0,0:10:54.95,0:10:59.76,Default,,0000,0000,0000,,the header of the ciphertext. So we would\Ncompute RSA invert of Y, that would give
Dialogue: 0,0:10:59.76,0:11:04.57,Default,,0000,0000,0000,,us the value X. Then we would apply the\Nhash function to X so that this would give
Dialogue: 0,0:11:04.57,0:11:09.20,Default,,0000,0000,0000,,us the key K. And then we would run the\Ndecryption algorithm for the symmetric
Dialogue: 0,0:11:09.20,0:11:15.17,Default,,0000,0000,0000,,system on the ciphertext and that would\Nproduce the original message m. And then
Dialogue: 0,0:11:15.17,0:11:19.10,Default,,0000,0000,0000,,we stated a theorem in the previous\Nsegment to say that if the RSA trapdoor
Dialogue: 0,0:11:19.10,0:11:23.09,Default,,0000,0000,0000,,permutation is secure, Es and Ds, the\Nsymmetric encryption scheme [inaudible]
Dialogue: 0,0:11:23.09,0:11:27.18,Default,,0000,0000,0000,,provides authenticated encryption. And as\Nwe said, H is just random oracle. It's,
Dialogue: 0,0:11:27.33,0:11:31.42,Default,,0000,0000,0000,,you know, kind of a random function from\NZN to the key space. Then, in fact, this
Dialogue: 0,0:11:31.42,0:11:35.72,Default,,0000,0000,0000,,system is chosen cipher text secure, and\Nis a good public key system to use.
Dialogue: 0,0:11:36.24,0:11:41.73,Default,,0000,0000,0000,,So now that we have our first example of a\Ngood public key system to use, I wanna
Dialogue: 0,0:11:41.73,0:11:46.98,Default,,0000,0000,0000,,quickly warn you about how not to use RSA\Nfor encryption. And this again something
Dialogue: 0,0:11:46.98,0:11:51.10,Default,,0000,0000,0000,,that we said in the previous segment. And\NI'm going to repeat it here, except I'm
Dialogue: 0,0:11:51.10,0:11:55.53,Default,,0000,0000,0000,,going to make it specific to RSA. So\NI'd like to call this, textbook RSA.
Dialogue: 0,0:11:55.53,0:11:59.40,Default,,0000,0000,0000,,Which basically is the first thing that\Ncomes to mind when you think about
Dialogue: 0,0:11:59.40,0:12:03.68,Default,,0000,0000,0000,,encrypting using RSA, namely, the secret\Nkey and the public key will be as before.
Dialogue: 0,0:12:03.68,0:12:08.16,Default,,0000,0000,0000,,But now instead of running through, a hash\Nfunction to generate a symmetric key, what
Dialogue: 0,0:12:08.16,0:12:12.34,Default,,0000,0000,0000,,we would do is we would directly use RSA\Nto encrypt the given message M. And then
Dialogue: 0,0:12:12.34,0:12:16.20,Default,,0000,0000,0000,,we would directly use the decryption\Nexponent to decrypt the cipher text and
Dialogue: 0,0:12:16.20,0:12:20.77,Default,,0000,0000,0000,,obtain the plain text M. I'm going to call\Nthis textbook RSA, because there are many
Dialogue: 0,0:12:20.77,0:12:25.35,Default,,0000,0000,0000,,textbooks that describe RSA encryption in\Nthis way. And this is completely wrong.
Dialogue: 0,0:12:25.35,0:12:29.50,Default,,0000,0000,0000,,This is not how RSA encryption works.\NIt's an insecure system. In particular,
Dialogue: 0,0:12:29.50,0:12:33.94,Default,,0000,0000,0000,,it's deterministic encryption, and so it\Ncan't possibly be semantically secure, but
Dialogue: 0,0:12:33.94,0:12:38.54,Default,,0000,0000,0000,,in fact there are many attacks exist that\NI'm going to show you an attack in just a
Dialogue: 0,0:12:38.54,0:12:42.71,Default,,0000,0000,0000,,minute, but the message that I want to\Nmake clear here, is that RSA, all it is,
Dialogue: 0,0:12:42.71,0:12:47.15,Default,,0000,0000,0000,,is a trap door permutation. By itself\Nit's not an encryption system. You have to
Dialogue: 0,0:12:47.15,0:12:51.43,Default,,0000,0000,0000,,embellish it with this ISO standard for\Nexample, to make it into an encryption
Dialogue: 0,0:12:51.43,0:12:55.83,Default,,0000,0000,0000,,system. By itself, all it is, is just a\Nfunction. So let's see what goes wrong if
Dialogue: 0,0:12:55.83,0:13:00.22,Default,,0000,0000,0000,,you try to use textbook RSA, In other\Nwords, if you try to encrypt a message
Dialogue: 0,0:13:00.22,0:13:04.98,Default,,0000,0000,0000,,using RSA directly. And I'll give you an\Nexample attack from the world of the web.
Dialogue: 0,0:13:04.98,0:13:09.72,Default,,0000,0000,0000,,So imagine we have a web server. The web\Nserver has an RSA secret key. Here's it's
Dialogue: 0,0:13:09.72,0:13:14.74,Default,,0000,0000,0000,,denoted by N and D. And here we have a web\Nbrowser who's trying to establish a secure
Dialogue: 0,0:13:14.74,0:13:19.12,Default,,0000,0000,0000,,session, a secure SSL session, with the web\Nserver. So the way SSL works is that the
Dialogue: 0,0:13:19.12,0:13:23.40,Default,,0000,0000,0000,,web browser starts off by sending this\Nclient hello message saying, hey, I want
Dialogue: 0,0:13:23.40,0:13:27.79,Default,,0000,0000,0000,,to set up a secure session with you. The\Nweb server responds with a server hello
Dialogue: 0,0:13:27.79,0:13:32.43,Default,,0000,0000,0000,,message that contains the server's public\Nkey And then the web browser will go ahead
Dialogue: 0,0:13:32.43,0:13:36.62,Default,,0000,0000,0000,,and generate a random what's called a\Npremaster secret K, it will encrypt the
Dialogue: 0,0:13:36.62,0:13:40.69,Default,,0000,0000,0000,,premaster secret using K and send the\Nresult in ciphertext over to the web
Dialogue: 0,0:13:40.69,0:13:44.93,Default,,0000,0000,0000,,server. The web server will decrypt and\Nthen the web server will also get K, so
Dialogue: 0,0:13:44.93,0:13:49.34,Default,,0000,0000,0000,,now the two have a shared key that they\Ncan use to then secure a session between
Dialogue: 0,0:13:49.34,0:13:53.63,Default,,0000,0000,0000,,them. So I want to show you what goes\Nwrong if we directly use the RSA function
Dialogue: 0,0:13:53.63,0:13:57.76,Default,,0000,0000,0000,,for encrypting K. In other words, if\Ndirectly K is encrypted as K to the e
Dialogue: 0,0:13:57.76,0:14:02.83,Default,,0000,0000,0000,,modulo N. Just for the sake of argument\Nlet's suppose that K is a 64-bit key.
Dialogue: 0,0:14:02.83,0:14:08.10,Default,,0000,0000,0000,,We're going to treat K as an integer in\Nthe range as zero to 2 to the 64.
Dialogue: 0,0:14:08.10,0:14:13.10,Default,,0000,0000,0000,,More precisely two to the 64 minus one,\Nand now what we're going to do is the
Dialogue: 0,0:14:13.10,0:14:18.30,Default,,0000,0000,0000,,following. First of all, suppose it so\Nhappens that K factors into a product of
Dialogue: 0,0:14:18.30,0:14:23.70,Default,,0000,0000,0000,,roughly equal sized numbers. So K we can\Nwrite as K1 times K2, where K1 and K2 are
Dialogue: 0,0:14:23.70,0:14:29.74,Default,,0000,0000,0000,,integers. And both are say less than two\Nto the 34. So, it turns out this happens
Dialogue: 0,0:14:29.74,0:14:34.51,Default,,0000,0000,0000,,with probability roughly twenty percent so\None in five times K can actually be
Dialogue: 0,0:14:34.51,0:14:39.74,Default,,0000,0000,0000,,written in this way. But, now if we plug\Nthis K, K=K1 x K2 if we plug that into the
Dialogue: 0,0:14:39.74,0:14:45.24,Default,,0000,0000,0000,,equation that defines the cipher text you\Nsee that we can simply substitute K by K1 x k2
Dialogue: 0,0:14:45.24,0:14:50.88,Default,,0000,0000,0000,,and then we can move k1 to the other side.\NSo then we end up with this equation here,
Dialogue: 0,0:14:50.88,0:14:55.90,Default,,0000,0000,0000,,namely C over K1 to the e is equal to K2 to the e. You notice if I multiply both
Dialogue: 0,0:14:55.90,0:15:00.66,Default,,0000,0000,0000,,sides by K1 to the e, I get that C is\Nequal to K1 times K2 to the e,
Dialogue: 0,0:15:00.66,0:15:06.37,Default,,0000,0000,0000,,which is precisely this equation here.\NOkay, so all I did is I just replaced K by
Dialogue: 0,0:15:06.37,0:15:11.96,Default,,0000,0000,0000,,K1 times K2 and then divided by K1 to the\Ne. So by now this should look familiar to
Dialogue: 0,0:15:11.96,0:15:16.15,Default,,0000,0000,0000,,you. So now we have two variables in this\Nequation, of course. C is known to the
Dialogue: 0,0:15:16.15,0:15:20.09,Default,,0000,0000,0000,,attacker, E is known to the attacker, and\NN is known to the attacker. The two
Dialogue: 0,0:15:20.09,0:15:24.52,Default,,0000,0000,0000,,variables in this equation are K1 and\NK2, and we've separated them into a
Dialogue: 0,0:15:24.52,0:15:28.89,Default,,0000,0000,0000,,different side of the equation, and as a\Nresult we can do now a meet in the middle
Dialogue: 0,0:15:28.89,0:15:33.16,Default,,0000,0000,0000,,attack on this equation. So let's do the\Nmeet in the middle attack. What we would
Dialogue: 0,0:15:33.16,0:15:37.52,Default,,0000,0000,0000,,do is we would build a table of all\Npossible values Of the left-hand side. So
Dialogue: 0,0:15:37.52,0:15:43.39,Default,,0000,0000,0000,,all possible values of C over K1 to the E,\Nthere are 2 to the 34 of them. And then,
Dialogue: 0,0:15:43.58,0:15:48.88,Default,,0000,0000,0000,,for all possible values on the right-hand\Nside, [inaudible] for all possible values
Dialogue: 0,0:15:48.88,0:15:54.18,Default,,0000,0000,0000,,of K2 to the e, we're gonna check whether\Nthis value here lives in the table that we
Dialogue: 0,0:15:54.18,0:15:58.75,Default,,0000,0000,0000,,constructed in step one. And if it is then\Nwe found a collision, and basically we
Dialogue: 0,0:15:58.75,0:16:03.26,Default,,0000,0000,0000,,have a solution to this equation. So as\Nsoon as we find an element of the form K2
Dialogue: 0,0:16:03.26,0:16:07.96,Default,,0000,0000,0000,,to the E that lives in the table that\Nwe built in step one, we've solved this
Dialogue: 0,0:16:07.96,0:16:12.72,Default,,0000,0000,0000,,equation and we found K1 and K2. And\Nof course once we found K1 and K2,
Dialogue: 0,0:16:12.72,0:16:16.95,Default,,0000,0000,0000,,we can easily recover K simply by\Nmultiplying them. So then we multiply K1
Dialogue: 0,0:16:16.95,0:16:21.43,Default,,0000,0000,0000,,and K2 and we get, the secret key\NK. Okay? So, we've broken, basically,
Dialogue: 0,0:16:21.43,0:16:25.60,Default,,0000,0000,0000,,this, this encryption system. And how long\Ndid it take? Well, by brute force, we
Dialogue: 0,0:16:25.60,0:16:29.89,Default,,0000,0000,0000,,could have broken it in time 2 to the 64,\Nsimply by trying all possible keys. But
Dialogue: 0,0:16:29.89,0:16:33.79,Default,,0000,0000,0000,,this attack, you notice, it took 2 to\Nthe 34 time for step number one. Well, it
Dialogue: 0,0:16:33.79,0:16:38.35,Default,,0000,0000,0000,,took a little bit more than 2 to the 34,\N'cause we had to do these exponentiations.
Dialogue: 0,0:16:38.52,0:16:42.97,Default,,0000,0000,0000,,It took 2 to the 34 time for step two\Nagainst slightly more than two to the 34
Dialogue: 0,0:16:42.97,0:16:47.53,Default,,0000,0000,0000,,because of the exponentiations. So let's\Nsay that the whole algorithm took time two
Dialogue: 0,0:16:47.53,0:16:52.28,Default,,0000,0000,0000,,to the 40. The point is that this is much,\Nmuch less time due to the 64. So here you
Dialogue: 0,0:16:52.28,0:16:56.67,Default,,0000,0000,0000,,have an example. Where if you encrypt\Nusing RSA directly, in other words you
Dialogue: 0,0:16:56.67,0:17:01.30,Default,,0000,0000,0000,,directly compute, K to the E, mod N,\Ninstead of going through the ISO standard,
Dialogue: 0,0:17:01.30,0:17:05.98,Default,,0000,0000,0000,,for example, then you get an attack that\Nruns much faster than exhaustive search.
Dialogue: 0,0:17:05.98,0:17:10.73,Default,,0000,0000,0000,,You get an attack that runs in time two to\Nthe 40, rather than time two to the 64.
Dialogue: 0,0:17:10.73,0:17:14.98,Default,,0000,0000,0000,,Okay, so this is a cute example of how\Nthings can break if you use the RSA
Dialogue: 0,0:17:14.98,0:17:19.30,Default,,0000,0000,0000,,trapdoor permutation directly to\Nencrypt a message. So the message to
Dialogue: 0,0:17:19.30,0:17:23.67,Default,,0000,0000,0000,,remember here, is never, ever, ever use\NRSA directly to encrypt. You have to use to go
Dialogue: 0,0:17:23.67,0:17:27.87,Default,,0000,0000,0000,,through an encryption mechanism. For\Nexample, like the ISO standard. And in
Dialogue: 0,0:17:27.87,0:17:32.35,Default,,0000,0000,0000,,fact, in the next segment we are going to\Nsee other ways of using RSA to build
Dialogue: 0,0:17:32.35,0:17:33.62,Default,,0000,0000,0000,,public key encryption.