WEBVTT 00:00:00.058 --> 00:00:04.308 Here is a fact about arithmetic that almost nothing else in mathematics shares. 00:00:04.412 --> 00:00:08.731 Some calculations are easy to run forwards and brutally hard to run backwards. 00:00:08.928 --> 00:00:10.495 Very nearly all of the security 00:00:10.495 --> 00:00:13.712 on the internet is built on that one lopsided fact. 00:00:15.109 --> 00:00:18.393 Before we build anything, let me show you where we are going. 00:00:18.476 --> 00:00:21.261 By the end of this lecture you will have made these two things, 00:00:21.344 --> 00:00:22.747 and they are only numbers. 00:00:22.830 --> 00:00:24.117 This one you publish. 00:00:24.200 --> 00:00:28.821 You put it in a certificate, you hand it to strangers, you print it on a poster. 00:00:29.733 --> 00:00:32.402 And this one you never show anybody, ever. 00:00:32.485 --> 00:00:36.340 Anyone who learns it can read everything that was ever sent to you. 00:00:37.141 --> 00:00:39.835 So the whole lecture is really one question: 00:00:40.032 --> 00:00:43.423 how do you hand out the first number without giving away the second? 00:00:44.726 --> 00:00:47.571 So here is where the first of those numbers comes from. 00:00:48.023 --> 00:00:51.391 Two primes, sixty one and fifty three. 00:00:51.704 --> 00:00:55.104 Multiply them together and out comes the number you just saw. 00:00:55.187 --> 00:00:57.309 You can do that by hand in twenty seconds, 00:00:57.392 --> 00:01:00.296 and your processor does it in a single instruction. 00:01:00.999 --> 00:01:04.007 Now let me hand you the answer and take the question away. 00:01:04.111 --> 00:01:08.024 Here is that same number, and I am not telling you what I multiplied. 00:01:08.221 --> 00:01:10.207 Which two primes were they? 00:01:10.659 --> 00:01:12.643 You know for certain that they exist, 00:01:12.726 --> 00:01:15.896 and there is no formula anywhere that will hand them to you. 00:01:16.948 --> 00:01:19.559 The only honest method is to go looking. 00:01:19.642 --> 00:01:22.034 Try two: does it divide? 00:01:22.347 --> 00:01:23.216 No. 00:01:23.299 --> 00:01:24.495 Try three. 00:01:24.692 --> 00:01:25.633 No. 00:01:25.830 --> 00:01:27.154 Try five. 00:01:27.351 --> 00:01:28.362 No. 00:01:28.558 --> 00:01:33.342 And on up the small numbers, asking every one of them the same question. 00:01:34.394 --> 00:01:36.705 And you do not have to search forever. 00:01:37.018 --> 00:01:41.173 If a number has two factors, one of them is no bigger than its square root, 00:01:41.256 --> 00:01:44.273 and for this one that is a shade under fifty seven. 00:01:44.356 --> 00:01:46.086 So the search is bounded. 00:01:46.282 --> 00:01:48.872 Fifty odd questions, worst case. 00:01:49.785 --> 00:01:51.130 So let us run it. 00:01:51.213 --> 00:01:57.216 Two, three, five, seven, and onward, and there it stops, at fifty three. 00:01:57.529 --> 00:02:01.233 That divides our number exactly, and the partner is sixty one. 00:02:01.430 --> 00:02:06.295 We found it, but notice how we found it: by exhaustion, not by insight. 00:02:07.092 --> 00:02:11.295 Fifty odd questions is nothing at all. But watch what happens to that search 00:02:11.295 --> 00:02:15.138 when this number gets bigger, because that gap is the entire trick. 00:02:16.442 --> 00:02:18.625 Here is the comparison that matters. 00:02:18.822 --> 00:02:21.876 Down the left, how many digits the number has. 00:02:22.189 --> 00:02:26.021 In the middle, what it costs to multiply the two primes together. 00:02:26.124 --> 00:02:29.387 And on the right, what it costs to go looking for them. 00:02:30.439 --> 00:02:32.725 Four digits, which is our case: 00:02:32.808 --> 00:02:36.594 multiplying is instant, and the search is about sixty steps. 00:02:36.907 --> 00:02:38.312 Twenty digits: 00:02:38.625 --> 00:02:40.458 multiplying is still instant, 00:02:40.541 --> 00:02:45.127 and the search is ten billion steps, which is a couple of seconds on a laptop. 00:02:46.342 --> 00:02:51.034 Six hundred and seventeen digits, which is the size your bank actually uses. 00:02:51.834 --> 00:02:56.386 Multiplying two three hundred digit primes is still instant, a millisecond. 00:02:56.838 --> 00:02:59.938 The search is ten to the three hundred and eight steps. 00:03:00.735 --> 00:03:04.704 There are only about ten to the eighty atoms in the observable universe. 00:03:04.787 --> 00:03:09.173 You could give every atom in it its own computer, run them all since the big bang, 00:03:09.256 --> 00:03:11.556 and you would not be anywhere near finished. 00:03:12.353 --> 00:03:14.977 That gap is the whole of RSA. 00:03:15.174 --> 00:03:15.987 Everything else we 00:03:15.987 --> 00:03:20.643 do today is machinery for turning one lopsided piece of arithmetic into a lock. 00:03:20.747 --> 00:03:24.123 But before we can build the lock we need a second kind of arithmetic: 00:03:24.206 --> 00:03:26.158 the kind that wraps around. 00:03:27.220 --> 00:03:29.229 You already know this arithmetic. 00:03:29.542 --> 00:03:33.301 It is the percent operator in whatever language you happen to write in. 00:03:33.385 --> 00:03:34.856 But let me set it up properly, 00:03:34.940 --> 00:03:39.550 on a clock face, because it is the ground that everything else today stands on. 00:03:40.602 --> 00:03:44.372 Twelve positions, and after eleven you do not get twelve, 00:03:44.456 --> 00:03:46.524 you get zero all over again. 00:03:46.720 --> 00:03:48.184 The numbers wrap. 00:03:48.458 --> 00:03:53.207 So start at zero, at the top, and count seventeen steps forward. 00:03:53.404 --> 00:03:59.546 One, two, three, on round past eleven, back through zero, and keep going. 00:03:59.859 --> 00:04:01.323 Where do you finish? 00:04:01.519 --> 00:04:02.762 At five. 00:04:03.373 --> 00:04:06.578 And that is what congruence modulo twelve means. 00:04:06.891 --> 00:04:10.305 Two whole numbers are congruent when they leave the same remainder. 00:04:10.502 --> 00:04:13.169 Seventeen and five leave the same one here, 00:04:13.253 --> 00:04:17.027 so as far as this clock is concerned they are the same number. 00:04:17.340 --> 00:04:19.953 We write it with a three bar equals sign. 00:04:20.866 --> 00:04:24.222 Now here is the property that makes all of this practical. 00:04:24.326 --> 00:04:26.683 You may take the remainder whenever you like. 00:04:26.880 --> 00:04:28.410 Nineteen times seven. 00:04:28.494 --> 00:04:33.440 I do not need the product at all, because nineteen is already seven on this clock. 00:04:33.636 --> 00:04:37.097 So it is seven times seven, forty nine, which is one. 00:04:37.801 --> 00:04:41.888 Reduce early and reduce often, and the numbers never grow. 00:04:42.085 --> 00:04:46.474 That single habit is what lets a computer raise a six hundred digit number to a six 00:04:46.474 --> 00:04:50.654 hundred digit power without ever holding anything bigger than six hundred digits. 00:04:52.051 --> 00:04:55.264 Now let us raise something to a power on one of these clocks. 00:04:55.348 --> 00:05:00.666 Take three, and keep multiplying it by itself, on a clock with seven positions. 00:05:01.462 --> 00:05:03.402 Three to the one is three. 00:05:03.599 --> 00:05:06.305 Three squared is nine, which is two. 00:05:06.501 --> 00:05:09.520 Three cubed is twenty seven, which is six. 00:05:10.317 --> 00:05:12.907 Then eighty one, which is four. 00:05:13.103 --> 00:05:16.610 Then two hundred and forty three, which is five. 00:05:16.923 --> 00:05:18.882 Then seven hundred and twenty nine, 00:05:18.966 --> 00:05:23.100 which is one, and after that the whole thing repeats forever. 00:05:23.897 --> 00:05:25.589 Now look down that last column. 00:05:25.673 --> 00:05:28.526 Three, two, six, 00:05:28.610 --> 00:05:31.003 four, five, one. 00:05:31.455 --> 00:05:33.336 That is a scramble. 00:05:33.533 --> 00:05:36.514 There is no pattern you can eyeball, and here is the point: 00:05:36.598 --> 00:05:40.984 if I tell you the answer is five, and ask which power of three produced it, 00:05:41.068 --> 00:05:42.590 you are back to guessing. 00:05:43.642 --> 00:05:45.183 That problem has a name, 00:05:45.267 --> 00:05:49.563 the discrete logarithm, and nobody has a fast method for it either. 00:05:49.760 --> 00:05:52.489 So there are our two one way streets. 00:05:52.685 --> 00:05:56.564 Multiplying primes is easy and factoring is hard. 00:05:56.760 --> 00:06:00.523 Raising to a power on a clock is cheap and coming back is not. 00:06:01.646 --> 00:06:02.610 Right. 00:06:02.714 --> 00:06:04.709 Let us build an actual key. 00:06:04.792 --> 00:06:07.995 There is exactly one piece of number theory you need first, 00:06:08.078 --> 00:06:10.110 and it is a counting question. 00:06:10.307 --> 00:06:14.079 So let me do the counting on a number small enough to see all of at once: 00:06:14.162 --> 00:06:16.752 fifteen, which is three times five. 00:06:17.455 --> 00:06:19.720 Here is every whole number below it. 00:06:19.917 --> 00:06:23.177 Now cross out the ones that share a factor with fifteen. 00:06:23.260 --> 00:06:27.870 The multiples of three: three, six, nine, twelve. 00:06:28.411 --> 00:06:31.524 And the multiples of five: five, and ten. 00:06:31.720 --> 00:06:32.998 What is left? 00:06:33.195 --> 00:06:38.548 One, two, four, seven, eight, eleven, thirteen and fourteen. 00:06:38.860 --> 00:06:40.591 Eight numbers survive. 00:06:41.388 --> 00:06:43.362 Eight is two times four. 00:06:43.559 --> 00:06:48.981 And two is three minus one, four is five minus one. That is not a coincidence. 00:06:49.178 --> 00:06:50.676 For any product of two primes, 00:06:50.676 --> 00:06:54.612 the count comes out as p minus one, times q minus one. 00:06:55.409 --> 00:06:57.848 This count has a name and a symbol. 00:06:57.951 --> 00:07:01.723 It is Euler's totient function, written phi of n. 00:07:01.806 --> 00:07:06.567 Hold on to it, because it is the only genuinely new symbol in this lecture. 00:07:07.963 --> 00:07:09.404 Now the real thing. 00:07:09.507 --> 00:07:11.284 I pick two primes: 00:07:11.481 --> 00:07:13.513 sixty one and fifty three. 00:07:13.710 --> 00:07:17.400 Real RSA picks primes with about three hundred digits each, 00:07:17.483 --> 00:07:21.594 by generating random odd numbers and testing them, which is fast. 00:07:21.790 --> 00:07:23.846 The arithmetic is identical. 00:07:24.043 --> 00:07:26.528 I just want numbers you can check by hand. 00:07:27.324 --> 00:07:28.614 Multiply them. 00:07:29.066 --> 00:07:31.723 That is n, and it is the modulus: 00:07:31.806 --> 00:07:35.673 the size of the clock that everything from here on happens on. 00:07:35.869 --> 00:07:38.262 You have seen it twice already today. 00:07:38.872 --> 00:07:41.599 Now compute phi of n from the two primes. 00:07:41.682 --> 00:07:44.933 Sixty times fifty two, which is this number here. 00:07:45.246 --> 00:07:48.730 And notice that you could only do that because you know p and q. 00:07:48.926 --> 00:07:53.885 From n on its own, computing phi is exactly as hard as factoring. 00:07:54.797 --> 00:07:57.445 Last, pick a public exponent, e. 00:07:57.642 --> 00:08:01.962 The one requirement is that it shares no factor with phi of n. 00:08:02.576 --> 00:08:07.534 Seventeen will do nicely: it is prime, and it does not divide the totient. 00:08:08.331 --> 00:08:12.265 In production, e is almost always one particular number, 00:08:12.348 --> 00:08:14.555 two to the sixteen plus one. 00:08:14.751 --> 00:08:16.679 Nothing deep is going on there. 00:08:16.876 --> 00:08:20.279 That exponent is simply quick to raise things to. 00:08:20.820 --> 00:08:26.452 And that is the public key: the pair n and e. You publish it. 00:08:26.555 --> 00:08:31.920 You put it in your certificate, you hand it to strangers, you print it on a poster. 00:08:32.116 --> 00:08:35.310 It is exactly the pair I showed you in the first minute. 00:08:36.706 --> 00:08:41.569 The private key is one more number, d, and it is fixed by a single condition: 00:08:41.652 --> 00:08:47.133 e times d has to be congruent to one, modulo phi of n. 00:08:47.825 --> 00:08:49.216 Unpack that. 00:08:49.299 --> 00:08:54.826 It says seventeen d is one more than some whole multiple of phi of n. 00:08:55.011 --> 00:08:57.125 So go and look for the multiple. 00:08:57.434 --> 00:09:02.030 Take k equals one. That gives three thousand one hundred and twenty one, 00:09:02.113 --> 00:09:04.493 and seventeen does not divide it. 00:09:04.690 --> 00:09:06.232 Bump k to two: 00:09:06.315 --> 00:09:09.671 six thousand two hundred and forty one, and again no. 00:09:09.775 --> 00:09:12.411 Bump it once more, and still no. 00:09:13.208 --> 00:09:16.900 Keep going, and at k equals fifteen you get this one. 00:09:17.213 --> 00:09:22.392 And that is seventeen times two thousand seven hundred and fifty three, exactly. 00:09:22.589 --> 00:09:24.099 So there is d. 00:09:24.477 --> 00:09:26.438 You would never do it that way in code. 00:09:26.521 --> 00:09:30.431 The extended Euclidean algorithm produces d in a few dozen steps, 00:09:30.514 --> 00:09:32.849 for numbers of any size at all. 00:09:33.045 --> 00:09:35.229 But that is what d is: 00:09:35.425 --> 00:09:40.511 the number that undoes seventeen, on a clock of size phi of n. 00:09:41.308 --> 00:09:42.899 So there is the pair. 00:09:43.003 --> 00:09:46.614 The public key is n and e, and anybody may have it. 00:09:46.811 --> 00:09:51.673 The private key is d, and every step that produced it leaned on this number here, 00:09:51.756 --> 00:09:53.986 which came from the two primes. 00:09:54.090 --> 00:09:56.088 They are the whole secret. 00:09:57.151 --> 00:10:01.866 All right. Your public key is out in the world, and I want to send you a message. 00:10:02.062 --> 00:10:03.956 The message is the letter A. 00:10:04.059 --> 00:10:08.504 My computer stores A as the number sixty five, so my message, as a number, 00:10:08.587 --> 00:10:10.086 is sixty five. 00:10:10.998 --> 00:10:13.609 Encryption is one line of arithmetic. 00:10:13.692 --> 00:10:19.136 The ciphertext c is the message raised to the public exponent e, modulo n. 00:10:19.219 --> 00:10:21.414 That is the entire operation. 00:10:21.839 --> 00:10:24.263 There is exactly one rule about the message: 00:10:24.346 --> 00:10:27.131 as a number it has to be smaller than n. 00:10:27.214 --> 00:10:31.578 Sixty five is comfortably smaller than our modulus, so we are fine. 00:10:31.661 --> 00:10:34.970 A real message gets chopped into blocks that each fit. 00:10:35.674 --> 00:10:40.990 So here is our case: sixty five, to the seventeenth, on a clock of that size. 00:10:41.073 --> 00:10:44.150 Now that power is a thirty one digit number. 00:10:44.254 --> 00:10:45.901 We are never going to write it down, 00:10:45.984 --> 00:10:51.163 and we do not have to, because of the habit from earlier: reduce at every step. 00:10:51.867 --> 00:10:52.866 Watch. 00:10:52.970 --> 00:10:54.689 Square sixty five: 00:10:54.792 --> 00:10:56.753 four thousand two hundred and twenty five, 00:10:56.836 --> 00:11:00.145 which on our clock is nine hundred and ninety two. 00:11:00.342 --> 00:11:05.078 Square that, reduce it again, and you get one thousand two hundred and thirty two, 00:11:05.078 --> 00:11:07.227 which is sixty five to the fourth. 00:11:08.140 --> 00:11:10.344 Square again and you have the eighth power: 00:11:10.427 --> 00:11:12.935 one thousand five hundred and forty seven. 00:11:13.550 --> 00:11:17.800 Once more and you have the sixteenth: seven hundred and eighty nine. 00:11:17.904 --> 00:11:22.096 Four squarings so far, and we have climbed all the way to sixteen. 00:11:22.799 --> 00:11:25.378 And seventeen is sixteen plus one. 00:11:25.574 --> 00:11:28.721 So one final multiplication by sixty five. 00:11:28.918 --> 00:11:32.145 Seven hundred and eighty nine times sixty five is fifty 00:11:32.145 --> 00:11:36.268 one thousand two hundred and eighty five, and on our clock that lands here. 00:11:36.972 --> 00:11:39.292 Four squarings and one multiplication. 00:11:39.375 --> 00:11:41.674 Not seventeen multiplications. 00:11:41.778 --> 00:11:46.644 And for a real two thousand bit exponent it is about three thousand steps. 00:11:46.747 --> 00:11:50.417 That is why your browser does this without you ever noticing. 00:11:51.930 --> 00:11:55.086 Let me lay out the whole range, from zero up to n. 00:11:55.169 --> 00:11:57.921 Here is the message, down at sixty five. 00:11:58.025 --> 00:12:01.137 And here is the ciphertext, way over there. 00:12:01.934 --> 00:12:03.572 Now look at the neighbours. 00:12:03.884 --> 00:12:06.973 Sixty four encrypts to fifteen seventy seven. 00:12:07.425 --> 00:12:10.538 Sixty six encrypts to five hundred and twenty four. 00:12:10.734 --> 00:12:15.623 Three consecutive messages, three ciphertexts flung all over the range. 00:12:15.819 --> 00:12:19.257 There is nothing to read off and nothing to interpolate between. 00:12:19.867 --> 00:12:21.737 That scatter is the point. 00:12:21.934 --> 00:12:23.571 Encryption here is not a shuffle 00:12:23.571 --> 00:12:27.031 or a substitution you could work backwards from by staring at it. 00:12:27.228 --> 00:12:28.898 It is one modular power, 00:12:28.981 --> 00:12:32.755 and it throws the message somewhere unpredictable inside the range. 00:12:34.152 --> 00:12:35.801 Now your side of it. 00:12:36.253 --> 00:12:40.316 The ciphertext is twenty-seven ninety, the private exponent is twenty-seven 00:12:40.316 --> 00:12:43.951 fifty-three, and the number we want back is sixty-five. 00:12:44.148 --> 00:12:46.250 Those are the numbers in front of us. 00:12:46.954 --> 00:12:48.739 Now write the relationship. 00:12:48.822 --> 00:12:52.420 The message m is c to the d, modulo n. 00:12:52.503 --> 00:12:56.739 For our ciphertext and private exponent, that is twenty-seven ninety 00:12:56.822 --> 00:13:00.956 to the twenty-seven fifty-three, modulo thirty-two thirty-three. 00:13:01.152 --> 00:13:06.261 In principle that is astronomically large, and again we never build it. 00:13:06.965 --> 00:13:08.124 Same trick. 00:13:08.207 --> 00:13:12.710 Two thousand seven hundred and fifty three is a sum of five powers of two: 00:13:12.793 --> 00:13:15.705 two thousand and forty eight, plus five hundred and twelve, 00:13:15.788 --> 00:13:19.725 plus one hundred and twenty eight, plus sixty four, plus one. 00:13:20.522 --> 00:13:23.515 So it is eleven squarings and four multiplications, 00:13:23.598 --> 00:13:25.433 and that is the whole cost. 00:13:25.630 --> 00:13:27.927 Do it, and out comes sixty five. 00:13:28.010 --> 00:13:32.295 The letter A. Exactly the message I sent, not close to it: 00:13:32.608 --> 00:13:35.267 exactly it, every single time. 00:13:36.180 --> 00:13:37.992 And there is the loop. 00:13:38.096 --> 00:13:41.928 Raise to e to lock it, raise to d to unlock it. 00:13:42.380 --> 00:13:43.645 The only thing separating you 00:13:43.645 --> 00:13:47.350 from everybody else watching the wire is that you know d. 00:13:48.146 --> 00:13:51.688 Which leaves the two questions we have been circling all lecture. 00:13:52.001 --> 00:13:54.416 Why does the message come back at all? 00:13:54.613 --> 00:13:56.912 And why can nobody else bring it back? 00:13:57.945 --> 00:14:00.164 So why did the message come back? 00:14:00.267 --> 00:14:05.028 Raise the ciphertext to d, and out drops exactly the number I started with. 00:14:05.132 --> 00:14:06.315 Not close to it. 00:14:06.398 --> 00:14:10.706 That is not luck, and it is not a property of the numbers I happened to pick. 00:14:11.018 --> 00:14:12.633 It is one theorem. 00:14:13.337 --> 00:14:14.823 Euler's theorem. 00:14:15.020 --> 00:14:20.823 If m shares no factor with n, then m raised to phi of n is one, modulo n. 00:14:20.906 --> 00:14:23.392 Not nearly one. Exactly one. 00:14:23.588 --> 00:14:26.373 Raise almost anything to that one particular power, 00:14:26.456 --> 00:14:29.777 on that one particular clock, and you land on one. 00:14:30.481 --> 00:14:32.592 Now watch what decryption actually is. 00:14:32.675 --> 00:14:39.166 c to the d is m to the e, all raised to the d, which is simply m to the e times d. 00:14:39.963 --> 00:14:41.714 So what is e times d? 00:14:41.797 --> 00:14:46.303 Seventeen times two thousand seven hundred and fifty three, which is this number. 00:14:46.406 --> 00:14:50.214 But we chose d precisely so that this product would be one more than a multiple 00:14:50.214 --> 00:14:55.614 of phi of n. And there it is: fifteen lots of the totient, plus one. 00:14:56.666 --> 00:15:01.715 So m to the e d is m to the fifteen times the totient, times one more m. 00:15:01.798 --> 00:15:07.034 Which I can regroup: m to the totient, all raised to the fifteenth, times m. 00:15:07.575 --> 00:15:10.616 And that bracket is Euler's theorem staring back at us. 00:15:10.699 --> 00:15:15.795 It is one. One to the fifteenth is one. So the whole expression collapses to m, 00:15:15.795 --> 00:15:21.076 every time, for every message under the sun. Decryption is not a lucky inverse. 00:15:21.159 --> 00:15:22.518 It is a theorem. 00:15:23.659 --> 00:15:24.589 Right. 00:15:24.786 --> 00:15:29.614 Now the other half. Why can nobody else do that? Put yourself on the outside: 00:15:29.697 --> 00:15:34.524 you have n, you have e, and you have the ciphertext going past on the wire. 00:15:34.607 --> 00:15:35.883 That is everything. 00:15:35.966 --> 00:15:37.511 What do you actually need? 00:15:37.855 --> 00:15:42.810 You need d. That is the only exponent that undoes seventeen on this particular clock, 00:15:42.893 --> 00:15:45.518 and without it the ciphertext is just a number. 00:15:46.222 --> 00:15:48.612 To compute d you need phi of n, 00:15:48.695 --> 00:15:55.695 because d was defined by that congruence: e d is one, modulo phi of n. No phi, no d. 00:15:56.215 --> 00:15:58.641 To compute phi of n you need p and q, 00:15:58.641 --> 00:16:04.400 because phi of n is p minus one times q minus one. There is no other route to it. 00:16:04.597 --> 00:16:06.687 Knowing n is not enough. 00:16:07.112 --> 00:16:10.141 And to get p and q out of n, you have to factor n. 00:16:10.224 --> 00:16:13.415 That is the last link, and every link in the chain is forced. 00:16:13.498 --> 00:16:15.658 There is no way in from the side. 00:16:16.454 --> 00:16:18.684 So how hard is factoring, really? 00:16:18.881 --> 00:16:22.783 Here is trial division again, plotted against the number of digits. 00:16:22.979 --> 00:16:25.291 Four digits, about a hundred steps. 00:16:25.487 --> 00:16:27.682 Eight digits, ten thousand. 00:16:27.879 --> 00:16:32.686 Twelve digits, a million, and the curve has already left the top of the board. 00:16:33.390 --> 00:16:37.326 Now imagine putting six hundred and seventeen digits on that axis. 00:16:37.523 --> 00:16:39.950 This curve was off the board at twelve. 00:16:40.054 --> 00:16:43.709 Out there, trial division needs the number we met in the first minute, 00:16:43.792 --> 00:16:46.147 the one bigger than the atoms in the universe. 00:16:46.230 --> 00:16:49.119 The best method anybody knows does enormously better, 00:16:49.202 --> 00:16:51.432 and it is still nowhere near enough. 00:16:52.229 --> 00:16:54.563 And notice the flip side of all this. 00:16:54.760 --> 00:16:56.688 My key is a toy. 00:16:56.792 --> 00:16:59.472 Its modulus has a factor under sixty, 00:16:59.555 --> 00:17:04.952 and you could break it on paper over a cup of coffee. That is not a flaw in RSA. 00:17:05.035 --> 00:17:08.426 It is the entire reason the real numbers have to be enormous. 00:17:09.939 --> 00:17:12.271 So that is RSA, complete. 00:17:12.354 --> 00:17:15.234 Encrypt by raising the message to e. 00:17:15.430 --> 00:17:18.566 Decrypt by raising the ciphertext to d. 00:17:18.669 --> 00:17:21.199 Both modulo n, and both cheap. 00:17:21.282 --> 00:17:23.300 The public key hands out n, 00:17:23.383 --> 00:17:27.239 and n is the product of two primes that it will not give up. 00:17:28.035 --> 00:17:30.565 One honest footnote before you go and implement this, 00:17:30.648 --> 00:17:33.144 because you should not implement this. 00:17:33.248 --> 00:17:36.256 What I have shown you is textbook RSA. 00:17:36.453 --> 00:17:41.211 Every real library pads the message with structured randomness before encrypting, 00:17:41.294 --> 00:17:44.035 because raw RSA has an obvious hole: 00:17:44.139 --> 00:17:47.437 the same message always produces the same ciphertext. 00:17:48.140 --> 00:17:51.160 The mathematics is exactly what you have just watched. 00:17:51.356 --> 00:17:54.387 The padding is what makes it safe to hand to strangers. 00:17:54.584 --> 00:17:55.954 And the wall the whole thing leans 00:17:55.954 --> 00:17:59.031 on has not changed since the first minute of this lecture. 00:17:59.135 --> 00:18:00.784 Multiplying is easy. 00:18:00.981 --> 00:18:02.804 Going the other way is not.