Asymmetric Cryptography For Those Who Only Know Arithmetic

This is the second in a series of posts adapted from old Facebook Notes. The original was published on February 8th, 2011.

Let's start with basic substitution cryptography, and take baby steps all the way to asymmetric public key cryptography.

The simplest sort of cipher that nearly everyone is probably familiar with are alphabetic rotation ciphers (like rot-13). The key is how many letters you're going to rotate by; i.e., for rot-13, you rotate by 13 letters, so to encrypt an 'a', you count 13 spaces along the alphabet from 'a' to get 'n', to encrypt a 'w' you count 2 spaces down to the end of the alphabet and then the remaining 11 spaces down from 'a' to get 'j', and so forth. Mathematically, this operation is known as "modular addition", or "clock addition" (because numbers wrap around like the hours on a clock face). Except in the special case of rot-13 using the 26-letter roman alphabet, where adding 13 twice gets you back to where you started, the decryption function is different from the encryption function--you use modular subtraction instead of addition, counting backwards instead of forwards to reverse the encryption.

Now, rotation ciphers are so simple that they're only really useful at all if your potential attackers don't know that you're using it, but for most ciphers of this general category you assume that the functions are well known and the basis for security is keeping the key secret. If anyone finds out your key, you're screwed. And keeping the key private is a big problem with this sort of encryption (which was pretty much the only kind of encryption around for most of history), because you have to share the key with the person you want to talk to, and the key has to be sent "in the clear" (because you haven't shared it yet, so you can't encrypt it).

Not the features of this kind of cryptography: the encryption and decryption procedures are public (everyone knows how to count letters in the alphabet), they are asymmetric (encryption involves adding, while decryption involves subtracting), and the key is private and symmetric (encryption and decryption use the same key).

Now, instead of keeping my key private, I could not worry about the key and just keep the decryption function private. In fact, I might just do away with a key entirely; an example of this is the use of invisible ink (although that's really a better example of steganography than encryption). The message can only be decrypted if you know the secret decryption function (chemical process) for the relevant type of ink. And if I'm content with one-way communication, I don't have to share the secret. I can make the key and the encryption function completely public, and just keep the really-hard-to-find decryption function to myself, and then anybody who wants to can send me a secure message that only I can decrypt. If I want to go two-way, then my partner will have to come up with his own set of public encryption and private decryption procedures. Using a rotation cipher isn't very practical here, because figuring out how to reverse modular addition with modular subtraction is really easy, so your secret function wouldn't stay secret for very long. You can imagine functions that are harder to figure out, but since finding new mathematical functions with the right properties is rather difficult, this system is not very practical. It does not make sense for everyone who wants to send private messages to have to do serious research in pure mathematics!

But what if we made the key asymmetric instead of (or in addition to) the encryption and decryption procedures? With a rotation cipher, one way to do that would be to say that if, e.g., my encryption key is 5, then my decryption key is 21, and we're always going to use modular addition, symmetrically, to encrypt and decrypt. You add 5 to each letter to get the ciphered text, and then you add 21 to each ciphered letter (completing a 26-space trip around the alphabet) to get back to where you started. Now, you can do one of two things:

1. You can publish your encryption key, and keep the decryption key secret. That means other people can encrypt messages that only you can read.
2. You can publish your decryption key, and the encryption key secret. That means you can write messages (digital signatures) that other people can prove came from you, because decrypting it with your published decryption key works, and no one else is capable of doing that kind of encryption.

Now, that eliminates the key sharing problem! You have to keep something secret, but it really can be secret--you never have to share your private key with anyone. But, by using your public key, your friend can write messages that only you can read, and by using your friend's public key, you can write messages that only they can read. And it's easy to come up with new keys--much easier than inventing whole new mathematical functions!

Of course, a system based on simple modular arithmetic still isn't all that secure, because finding an additive inverse is *really easy*; in normal arithmetic, you just stick a negative sign in front (i.e., the additive inverse of 5 is -5), and in modular arithmetic you just subtract from the size of the alphabet (so the inverse of 5 in an alphabetic rotation cipher is 26-5 = 21). As soon as you publish the fact that your decryption key is 21, anyone can do some simple subtraction and figure out that your private encryption key is 5, or vice-versa. But, there are lots of mathematical operators and functions which have the nice property that some numbers have inverses in relation to those operators--not just addition. For example, the inverse of 2 over multiplication is 1/2, etc. Now, finding multiplicative inverses isn't all that difficult either, but it's a little harder than just sticking a minus sign out front, so let's run through an example using multiplication as the encryption function:

Say my public key is 2. Multiplying letters doesn't make immediate sense like counting them does, so we need to convert our letters into numbers first; fortunately, computers already represent letters as numbers anyway. So, suppose you want to secretly send me the letter 'c', which we'll assign the number 3. So, you use the encryption function (*) and the key (2) to calculate the ciphertext (3*2=6), which you send to me.
My private key is the inverse of 2-- 1/2.
I get the ciphertext 6 from you, and use the encryption function (*) with my private key (1/2) to recover the plaintext (6*1/2 = 3), which I can then interpret as the letter 'c'. Ta da! We have just accomplished encrypted communication without ever sharing a secret key.

By now, the basic proof-of-concept, that there is a way to communicate privately without ever having to arrange to share a secret with someone ahead of time, should be clear--as long as all of your adversaries are toddlers who haven't learned arithmetic. The multiplication-based system is still easy to crack, because everybody learns how to do division and multiply fractions in elementary school. But what if we did modular multiplication? Say I want to encrypt the letter 'n', which is the 14th letter of the alphabet; multiplying by my encryption key gets us 28--but there is no 28th letter of the alphabet! Instead, we wrap around and get the (28-26)=2nd letter of the alphabet--so 'n' encrypts as 'b'. What's the inverse of that? In this case, it turns out to be 20: 20*2=40, 40-26=14, 14='n'. That was a little harder to figure out, so we're getting somewhere... but it wasn't *that* hard to figure out (if it were, we wouldn't be able to figure out our own decryption keys ourselves, which would be kind of useless!), and it turns out that you aren't actually guaranteed to be able to find an inverse all the time--it's only guaranteed to work if the length of your alphabet is a prime number (which 26 is not!), so you have to pick your keys carefully, which makes it easier for an attacker to just try all of the possibilities until they guess the right one.

Real cryptosystems, therefore, get a little more complicated in a few ways. For one thing, although not all encryption functions depend on the alphabet being a prime number, most do require it to be special in some way; additionally, we want keys to be big numbers, in a large range (not just 1 to 26), so that they are harder to guess. Thus, we use more complicated ways of turning strings of letters into numbers before doing arithmetic on them. And for another thing, we have to be fairly clever about finding special mathematical functions (more complicated than just modular multiplication) which have a special property that makes it easy to generate a pair of numbers that are inverses of each other, but really hard to figure out the inverse given just one number. These are called "trapdoor functions"--it's easy to open the trapdoor from one side, but really hard to climb back out from the other side! But if you can find such a function (like, say, modular exponentiation over a range defined by multiplying two large prime numbers), so that you can't figure out what my private key is despite having the function and the public key, and then bam, you've got RSA public-key encryption & digital signing! If you know the prime numbers used to generate an RSA key, finding the inverse is trivial, so we can make keypairs for ourselves easily--but inverting a key without knowing how it was made requires factoring a large number, which is much, much more difficult than just doing division or multiplying fractions! And that is what keeps your messages over the internet safe.

NOTE: In these toy examples, and in actual RSA, the private key is the inverse of the public key, and the public key is also the inverse of the private key. This makes them interchangeable, and let's you do signing & encryption at the same time (that's generally considered a bad idea, but it can be done). However, while this seems intuitive and natural, it is not necessarily the case. There do exist functions for which a=inverse(b) does not imply that b=inverse(a), in which case the keys are not interchangeable.

Also note that, if you can factor large numbers easily, RSA becomes really easy to crack, just like our toy examples using addition and multiplication (that's what all the fuss about quantum computers is about). But while RSA was the first public-key encryption system invented, it's far from the only one nowadays, and there are plenty of more complicated encryption systems that rely on functions not-quite-as-accessible to an audience who only know arithmetic in which finding the inverses of public keys is much, much harder still.