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.

Why I Know So Much

This is the first in a series of posts adapted from old Facebook notes, in the hopes that reworking old material will get me back into the groove of writing and perhaps I will start putting out more new material. The original was published on November 8th, 2010.


Back when meeting new people was actually a thing that happened from time to time (i.e., when I was still in school), I would frequently experience people asking me "how do you know that?" or "how do you know so much?" or some variation on that theme. Usually I would give a short answer like "I read a lot", but I've decided to go into the issue a little deeper. Why do other people perceive me as knowing an unusually large quantity of stuff?

Part of it is that I know stuff about lots of widely differing fields. People often have often had misconceptions of what my degrees were in based on whatever topic I may have expounded on in their presence first, and when they encounter me then discoursing intelligently on something wildly different (like when someone who knows I'm good at physics first hears me get excited about linguistics), they are surprised. Why should they be surprised? I think it's because most people only have expertise in a very few fields, and it doesn't elicit surprise when someone reveals how much they know about Their Field. There's something surprising and impressive about having depth in more than one area. Especially since we are all so used to the fallacy of people who are experts in one area proclaiming bullcrap about other domains.

So, answering the question "how do I know so much?" at a deeper level means answering the question "how did I become knowledgeable about so many different things?" Or, "why am I not stuck on a small range of topics?" I won't tackle that directly, because I don't think I can really come up with a better answer than just "I'm interested in it all." It's a fundamental feature of my brain and my personality. And then because I'm interested in it, I go looking for it. And once you go looking for knowledge, especially when you go looking for knowledge in apparently wildly divergent directions, you get compound interest. The more you know, the easier it is to understand even more things, and the more your rate of learning will increase. Richard Hamming once said

Given two people of approximately the same ability and one person who works ten percent more than the other, the latter will more than twice outproduce the former. The more you know, the more you learn; the more you learn, the more you can do; the more you can do, the more the opportunity - it is very much like compound interest. I don't want to give you a rate, but it is a very high rate.

So if I spend even a few more minutes every day acquiring new knowledge than some other person of equivalent ability, over a year, or a few years, or 30 years, I'll end up far, far ahead. And I try not to let time go by when my brain is idle. If I can read something, I'll read it. If I can talk to someone who knows more than I do, I'll try to get them to answer my questions. If I can't read anything, and I can't talk to anybody, I'll philosophize, and try to solve problems I already know about, or try to come up with new problems that are easier to solve. Note that bit about "someone who knows more than I do": if you maintain a good, accurate understanding not only of what you have learned, but also what you know that you don't know yet, that can greatly increase your efficiency at learning new things. Now, all that philosophizing time helps make new connections, and the more stuff you have to connect, the more connections you can make. You still get compound interest if you're just studying one subject, but the exponent gets even bigger when you find that you can start making correlations between highly divergent domains. So, not only is it true that the more you know, the faster you'll know more, but also, the more different kinds of things you know, the faster you'll learn even more different kinds of things. And pretty soon, you realize that most of what you know cannot be easily put into nice neat boxes like "Math" and "English" and "Biology". Did you know that natural language processing and protein folding simulation have a lot of overlap in the types of algorithms used to run them? I know that because I happened to have lunch with a guy working on natural language processing, and a guy working on protein folding in bioinformatics. And then I went and got a degree in computational linguistics so I'd know what those algorithms were!

So, start taking a few minutes every day to think about things you don't know much about yet. Wikipedia is a great help for getting started with that. Keep it up, and pretty soon, you'll know a lot of stuff, too.