After going through this, you might think "wow, that seems so obvious, why did it take 6000 years of civilization before somebody figured this out?" Well, lots of things seem obvious in retrospect, but it's actually really hard; and, after you've got the idea, it's still hard to come up with the actual functions that implement the idea.
So, 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 you're probably all familiar with are alphabetic rotation ciphers (like rot-13). The key is the number of letters you're going to rotate by, and the encryption function is modular addition.
Except in the special case of rot-13 using the 26-letter Roman alphabet, the decryption function is different- it's modular subtraction instead of addition, the inverse of the encryption function.
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 key to security is keeping the key secret.
So, note the features here:
- Asymmetric public en/decryption functions
- private key
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). It's a bootstrapping problem.
Modular addition & subtraction are really easy to reverse, so you can assume that if somebody knows either one of them, it's really easy to figure out the other, and it's not much use trying to keep secret. But what if we used a function that's really difficult to invert? Say if instead of f(m,k) = m+k, we used something like f(m,k) = (m+k)/(m-k); that's still not extremely difficult to invert, but it's harder, so hopefully you can see how there are functions for which calculating the inverse is totally impractically difficult.
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. 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 functions.
Since finding new mathematical functions with the right properties is rather difficult, this system is not very practical, but it works as a proof-of-concept: I can set up secure communications without ever having to share a secret, taking advantage of asymmetry in encryption and decryption.
- Asymmetric public/private en/decryption functions
- public key
This sort of one-way cryptography has another use- authentication & signing. If I send you a message encrypted with my private function, and you are able to decrypt it with my public function, then you know that it must have come from me, because no one else can do that kind of encryption.
Now, notice that there are lots of mathematical operators and functions which have the nice property that some numbers have inverses in relation to those operators. Like, the inverse of 2 over addition is -2, the inverse of 2 over multiplication is 1/2, etc. So, rather than coming up with pairs of functions, we can pick functions that have inverses in their domains and come up with pairs of inverse keys.
Going back to the simple rotation cipher example, we could re-analyze it as using one encryption function (modular addition) and two asymmetric keys (say, 2 and -2). Like when we were coming up with inverse functions, these inverses are really easy to calculate, and thus not very useful for encryption, but we can come up with operators for which finding the inverse of an arbitrary number is very difficult.
- Asymmetric public/private keys
- public en/decryption function
If you consider the encryption & decryption functions to be the the combination of base function + keys, then this is conceptually identical to having asymmetric functions, but it gives you a much simpler mathematical framework for generating those functions.
So far I've assumed that the encryption functions and keys are commutative; e.g., f.g = g.f, and f=g^-1 implies g = f^-1. In real-world cryptosystems like RSA, this is generally the case, and it's useful because it means that which piece you keep private and which piece is public doesn't matter, they're interchangeable, and you can use a single set of keys for both encryption and signing. However, in general this does not have to be true; we could pick a base function such that x = y^-1 does not imply that y = x^-1, or such that f.g =/= g.f. Such systems may even be slightly more difficult to crack, but commutative functions are just really convenient.