Why Factoring Keeps Secrets: RSA Encryption

Here is a fact about arithmetic that almost nothing else in mathematics shares. Some calculations are easy to run forwards and brutally hard to run backwards. Very nearly all of the security on the internet is built on that one lopsided fact. Before we build anything, let me show you where we are going. By the end of this lecture you will have made these two things, and they are only numbers. This one you publish. You put it in a certificate, you hand it to strangers, you print it on a poster. And this one you never show anybody, ever. Anyone who learns it can read everything that was ever sent to you. So the whole lecture is really one question: how do you hand out the first number without giving away the second? So here is where the first of those numbers comes from. Two primes, sixty one and fifty three. Multiply them together and out comes the number you just saw. You can do that by hand in twenty seconds, and your processor does it in a single instruction. Now let me hand you the answer and take the question away. Here is that same number, and I am not telling you what I multiplied. Which two primes were they? You know for certain that they exist, and there is no formula anywhere that will hand them to you. The only honest method is to go looking. Try two: does it divide? No. Try three. No. Try five. No. And on up the small numbers, asking every one of them the same question. And you do not have to search forever. If a number has two factors, one of them is no bigger than its square root, and for this one that is a shade under fifty seven. So the search is bounded. Fifty odd questions, worst case. So let us run it. Two, three, five, seven, and onward, and there it stops, at fifty three. That divides our number exactly, and the partner is sixty one. We found it, but notice how we found it: by exhaustion, not by insight. Fifty odd questions is nothing at all. But watch what happens to that search when this number gets bigger, because that gap is the entire trick. Here is the comparison that matters. Down the left, how many digits the number has. In the middle, what it costs to multiply the two primes together. And on the right, what it costs to go looking for them. Four digits, which is our case: multiplying is instant, and the search is about sixty steps. Twenty digits: multiplying is still instant, and the search is ten billion steps, which is a couple of seconds on a laptop. Six hundred and seventeen digits, which is the size your bank actually uses. Multiplying two three hundred digit primes is still instant, a millisecond. The search is ten to the three hundred and eight steps. There are only about ten to the eighty atoms in the observable universe. You could give every atom in it its own computer, run them all since the big bang, and you would not be anywhere near finished. That gap is the whole of RSA. Everything else we do today is machinery for turning one lopsided piece of arithmetic into a lock. But before we can build the lock we need a second kind of arithmetic: the kind that wraps around.

You already know this arithmetic. It is the percent operator in whatever language you happen to write in. But let me set it up properly, on a clock face, because it is the ground that everything else today stands on. Twelve positions, and after eleven you do not get twelve, you get zero all over again. The numbers wrap. So start at zero, at the top, and count seventeen steps forward. One, two, three, on round past eleven, back through zero, and keep going. Where do you finish? At five. And that is what congruence modulo twelve means. Two whole numbers are congruent when they leave the same remainder. Seventeen and five leave the same one here, so as far as this clock is concerned they are the same number. We write it with a three bar equals sign. Now here is the property that makes all of this practical. You may take the remainder whenever you like. Nineteen times seven. I do not need the product at all, because nineteen is already seven on this clock. So it is seven times seven, forty nine, which is one. Reduce early and reduce often, and the numbers never grow. That single habit is what lets a computer raise a six hundred digit number to a six hundred digit power without ever holding anything bigger than six hundred digits. Now let us raise something to a power on one of these clocks. Take three, and keep multiplying it by itself, on a clock with seven positions. Three to the one is three. Three squared is nine, which is two. Three cubed is twenty seven, which is six. Then eighty one, which is four. Then two hundred and forty three, which is five. Then seven hundred and twenty nine, which is one, and after that the whole thing repeats forever. Now look down that last column. Three, two, six, four, five, one. That is a scramble. There is no pattern you can eyeball, and here is the point: if I tell you the answer is five, and ask which power of three produced it, you are back to guessing. That problem has a name, the discrete logarithm, and nobody has a fast method for it either. So there are our two one way streets. Multiplying primes is easy and factoring is hard. Raising to a power on a clock is cheap and coming back is not.

Right. Let us build an actual key. There is exactly one piece of number theory you need first, and it is a counting question. So let me do the counting on a number small enough to see all of at once: fifteen, which is three times five. Here is every whole number below it. Now cross out the ones that share a factor with fifteen. The multiples of three: three, six, nine, twelve. And the multiples of five: five, and ten. What is left? One, two, four, seven, eight, eleven, thirteen and fourteen. Eight numbers survive. Eight is two times four. And two is three minus one, four is five minus one. That is not a coincidence. For any product of two primes, the count comes out as p minus one, times q minus one. This count has a name and a symbol. It is Euler's totient function, written phi of n. Hold on to it, because it is the only genuinely new symbol in this lecture. Now the real thing. I pick two primes: sixty one and fifty three. Real RSA picks primes with about three hundred digits each, by generating random odd numbers and testing them, which is fast. The arithmetic is identical. I just want numbers you can check by hand. Multiply them. That is n, and it is the modulus: the size of the clock that everything from here on happens on. You have seen it twice already today. Now compute phi of n from the two primes. Sixty times fifty two, which is this number here. And notice that you could only do that because you know p and q. From n on its own, computing phi is exactly as hard as factoring. Last, pick a public exponent, e. The one requirement is that it shares no factor with phi of n. Seventeen will do nicely: it is prime, and it does not divide the totient. In production, e is almost always one particular number, two to the sixteen plus one. Nothing deep is going on there. That exponent is simply quick to raise things to. And that is the public key: the pair n and e. You publish it. You put it in your certificate, you hand it to strangers, you print it on a poster. It is exactly the pair I showed you in the first minute. The private key is one more number, d, and it is fixed by a single condition: e times d has to be congruent to one, modulo phi of n. Unpack that. It says seventeen d is one more than some whole multiple of phi of n. So go and look for the multiple. Take k equals one. That gives three thousand one hundred and twenty one, and seventeen does not divide it. Bump k to two: six thousand two hundred and forty one, and again no. Bump it once more, and still no. Keep going, and at k equals fifteen you get this one. And that is seventeen times two thousand seven hundred and fifty three, exactly. So there is d. You would never do it that way in code. The extended Euclidean algorithm produces d in a few dozen steps, for numbers of any size at all. But that is what d is: the number that undoes seventeen, on a clock of size phi of n. So there is the pair. The public key is n and e, and anybody may have it. The private key is d, and every step that produced it leaned on this number here, which came from the two primes. They are the whole secret.

All right. Your public key is out in the world, and I want to send you a message. The message is the letter A. My computer stores A as the number sixty five, so my message, as a number, is sixty five. Encryption is one line of arithmetic. The ciphertext c is the message raised to the public exponent e, modulo n. That is the entire operation. There is exactly one rule about the message: as a number it has to be smaller than n. Sixty five is comfortably smaller than our modulus, so we are fine. A real message gets chopped into blocks that each fit. So here is our case: sixty five, to the seventeenth, on a clock of that size. Now that power is a thirty one digit number. We are never going to write it down, and we do not have to, because of the habit from earlier: reduce at every step. Watch. Square sixty five: four thousand two hundred and twenty five, which on our clock is nine hundred and ninety two. Square that, reduce it again, and you get one thousand two hundred and thirty two, which is sixty five to the fourth. Square again and you have the eighth power: one thousand five hundred and forty seven. Once more and you have the sixteenth: seven hundred and eighty nine. Four squarings so far, and we have climbed all the way to sixteen. And seventeen is sixteen plus one. So one final multiplication by sixty five. Seven hundred and eighty nine times sixty five is fifty one thousand two hundred and eighty five, and on our clock that lands here. Four squarings and one multiplication. Not seventeen multiplications. And for a real two thousand bit exponent it is about three thousand steps. That is why your browser does this without you ever noticing. Let me lay out the whole range, from zero up to n. Here is the message, down at sixty five. And here is the ciphertext, way over there. Now look at the neighbours. Sixty four encrypts to fifteen seventy seven. Sixty six encrypts to five hundred and twenty four. Three consecutive messages, three ciphertexts flung all over the range. There is nothing to read off and nothing to interpolate between. That scatter is the point. Encryption here is not a shuffle or a substitution you could work backwards from by staring at it. It is one modular power, and it throws the message somewhere unpredictable inside the range. Now your side of it. The ciphertext is twenty-seven ninety, the private exponent is twenty-seven fifty-three, and the number we want back is sixty-five. Those are the numbers in front of us. Now write the relationship. The message m is c to the d, modulo n. For our ciphertext and private exponent, that is twenty-seven ninety to the twenty-seven fifty-three, modulo thirty-two thirty-three. In principle that is astronomically large, and again we never build it. Same trick. Two thousand seven hundred and fifty three is a sum of five powers of two: two thousand and forty eight, plus five hundred and twelve, plus one hundred and twenty eight, plus sixty four, plus one. So it is eleven squarings and four multiplications, and that is the whole cost. Do it, and out comes sixty five. The letter A. Exactly the message I sent, not close to it: exactly it, every single time. And there is the loop. Raise to e to lock it, raise to d to unlock it. The only thing separating you from everybody else watching the wire is that you know d. Which leaves the two questions we have been circling all lecture. Why does the message come back at all? And why can nobody else bring it back?

So why did the message come back? Raise the ciphertext to d, and out drops exactly the number I started with. Not close to it. That is not luck, and it is not a property of the numbers I happened to pick. It is one theorem. Euler's theorem. If m shares no factor with n, then m raised to phi of n is one, modulo n. Not nearly one. Exactly one. Raise almost anything to that one particular power, on that one particular clock, and you land on one. Now watch what decryption actually is. c to the d is m to the e, all raised to the d, which is simply m to the e times d. So what is e times d? Seventeen times two thousand seven hundred and fifty three, which is this number. But we chose d precisely so that this product would be one more than a multiple of phi of n. And there it is: fifteen lots of the totient, plus one. So m to the e d is m to the fifteen times the totient, times one more m. Which I can regroup: m to the totient, all raised to the fifteenth, times m. And that bracket is Euler's theorem staring back at us. It is one. One to the fifteenth is one. So the whole expression collapses to m, every time, for every message under the sun. Decryption is not a lucky inverse. It is a theorem. Right. Now the other half. Why can nobody else do that? Put yourself on the outside: you have n, you have e, and you have the ciphertext going past on the wire. That is everything. What do you actually need? You need d. That is the only exponent that undoes seventeen on this particular clock, and without it the ciphertext is just a number. To compute d you need phi of n, because d was defined by that congruence: e d is one, modulo phi of n. No phi, no d. To compute phi of n you need p and q, because phi of n is p minus one times q minus one. There is no other route to it. Knowing n is not enough. And to get p and q out of n, you have to factor n. That is the last link, and every link in the chain is forced. There is no way in from the side. So how hard is factoring, really? Here is trial division again, plotted against the number of digits. Four digits, about a hundred steps. Eight digits, ten thousand. Twelve digits, a million, and the curve has already left the top of the board. Now imagine putting six hundred and seventeen digits on that axis. This curve was off the board at twelve. Out there, trial division needs the number we met in the first minute, the one bigger than the atoms in the universe. The best method anybody knows does enormously better, and it is still nowhere near enough. And notice the flip side of all this. My key is a toy. Its modulus has a factor under sixty, and you could break it on paper over a cup of coffee. That is not a flaw in RSA. It is the entire reason the real numbers have to be enormous. So that is RSA, complete. Encrypt by raising the message to e. Decrypt by raising the ciphertext to d. Both modulo n, and both cheap. The public key hands out n, and n is the product of two primes that it will not give up. One honest footnote before you go and implement this, because you should not implement this. What I have shown you is textbook RSA. Every real library pads the message with structured randomness before encrypting, because raw RSA has an obvious hole: the same message always produces the same ciphertext. The mathematics is exactly what you have just watched. The padding is what makes it safe to hand to strangers. And the wall the whole thing leans on has not changed since the first minute of this lecture. Multiplying is easy. Going the other way is not.