An example of encryption

Let's say I want to send my credit card number to a bank over the internet.

If the bank sent everyone the equivalent of a lockbox and a key, any miscreant who also dealt with the bank would have a copy of the bank's key and could get into my lockbox just as easily as his own, or the bank would need a seriously large keyring.

If the bank sent everyone the equivalent of a lockbox and a padlock, once locked, no one but the bank, who has the key to the padlock, can get inside, not even you.

This is the sort of idea RSA, and a lot of modern encryption, works.

Instead of using my actual credit card number, or even a made-up one, let's just deal with some random text: "Sincere juicy cabbage letters." But RSA, heck, even computers, don't understand words or even letters—it needs numbers. We can convert it to a list of ASCII, or UTF-8, numbers: 83, 105, 110, 99, 101, 114, 101, 32, 106, 117, 105, 99, 121, 32, 99, 97, 98, 98, 97, 103, 101, 32, 108, 101, 116, 116, 101, 114, 115, 46.

The bank sends you the padlock, 5, and the lockbox, 259. Anyone can have access to either of these, they're not secrets. If you bank online, your bank's actual numbers are probably stored somewhere on your computer.

Step 1: take each letter in the list and raise it to the power of 5: 3939040643, 12762815625, 16105100000, 9509900499, 10510100501, 19254145824, 10510100501, 33554432, 13382255776, 21924480357, 12762815625, 9509900499, 25937424601, 33554432, 9509900499, 8587340257, 9039207968, 9039207968, 8587340257, 11592740743, 10510100501, 33554432, 14693280768, 10510100501, 21003416576, 21003416576, 10510100501, 19254145824, 20113571875, 205962976

At this point, since the "5" isn't a secret, anyone who has it could take the 5th root of these numbers and figure out the original message. Which is where step two comes in.

Step 2: divide each of those numbers by 259, and keep just the remainder: 34, 105, 73, 141, 159, 95, 159, 205, 57, 80, 105, 141, 137, 205, 141, 230, 224, 224, 230, 199, 159, 205, 201, 159, 128, 128, 159, 95, 173, 219.

If you thought this was the actual message, and tried to convert it back into text, you'd get a garbled mess: "iIŸ_ŸÍ9Pi‰ÍæààæǟÍɟ€€Ÿ_­Û

Only the bank has the key to unlock it. There's no mathematical formula, given the numbers 5 and 259, to get the message back.

The bank has the key, which in this case is 29. The same process happens here: raise all the numbers to the power of 29, divide the result by 259, and keep the remainder (29's a much bigger number—34^29=258754906862289125141960829975095105409777664—so I won't bore you with the results of the middle step here): 83, 105, 110, 99, 101, 114, 101, 32, 106, 117, 105, 99, 121, 32, 99, 97, 98, 98, 97, 103, 101, 32, 108, 101, 116, 116, 101, 114, 115, 46. Huh, those numbers look eerily familiar!

I kind of lied before: knowing 5 and 259 actually can give you 29, the key, but the issue is that the numbers banks, Facebook, Google, and other companies use are much, much bigger than 259, so much so that doing the steps required to get the answer, or key, is non-trivial.

In order to get the key from the original numbers, you need to know the prime factors of 259, which are 7 and 37. Your padlock, 5, has no factors in common with the least common multiple of one less than these numbers (6 and 36, which of course is 36, don't worry about why these numbers, but if it has common factors, your lock is broken). Then you find another number that, when multiplied by 5 and divided by 36, gives you a remainder of 1. There is a mathematical formula/algorithm to find out what that number is, but because you don't know the factors 7 and 37, you don't know the 36. Because you don't know the 36, you can't break in to the lockbox.

An example number (768 bits, 232 digits): 1230186684​5301177551​3049495838​4962720772​8535695953​3479219732​2452151726​4005072636​5751874520​2199786469​3899564749​4277406384​5925192557​3263034537​3154826850​7917026122​1429134616​7042921431​1602221240​4792747377​9408066535​1419597459​856902143413

We know the factors of this are 3347807169​8956898786​0441698482​1269081770​4794983713​7685689124​3138898288​3793878002​2876147116​5253174308​7737814467999489 and 3674604366​6799590428​2446337996​2795263227​9158164343​0876426760​3228381573​9666511279​2333734171​4339681027​0092798736308917, so using it as a lock isn't a good idea, but it took 13 people two years to figure out what those factors were. And that is a small number! The typical numbers used today are 1024 bits, or 308-309 digits long, or for banks, twice that.