In the past, one would usually assume that both the sender and the receiver keep their keys secret (seems reasonable!), which is called symmetric key encryption. The symmetry is that both people need to keep it secret. One supposed early example of this goes back to C. Julius Caesar. To encrypt a message, first convert it to numbers, and then add three to each number (wrapping around if needed), and convert back to letters.

It's pretty clear that 1=A here, for instance. Now let's add three to each. The second letter should get to 4=D, for instance.

What did I do here? Well, this is really just modular arithmetic, modulo 26, so that is what I did.

How will I decrypt it, if I get this mysterious message? Here is the main point about mathematical ciphers; they need to come from operations that have inverses! So in number theoretic ciphers, they'll need to come from (somehow) invertible operations.

In this case, the operation is modular addition, which certainly has inverses. If your encoded numerical message is \(x\), your key is \(a\), and you are working modulo \((n)\), then your encrypted message \(m\) is \[m\equiv x+a \text{ mod}(n)\] To get \(x\) back, you just use the additive inverse to \(a\) modulo \(n\), which is \(-a\).

Since \(-3\) is the inverse of \(3\), this one is easy to decipher.

We could list the key here as a pair \((a,n)\), with \(a=3\) and \(n=26\).

As noted above, one can do something similar with bigger numbers, in blocks of two.

Let's do something a little more interesting to encrypt this. What else has inverses?

Well, sometimes multiplication mod \((n)\) does! We could make a cipher that gets \(m\) by performing \[m\equiv ax+b \text{ mod}(n)\; .\] Here, let's choose \(a=5\) and \(b=18\); we'll use \(n=677\), the next prime after \(26^2\), since we have blocks of two letters each.

Now the key is listed as a triple, \((a,b,n)=(5,18,677)\). How do we invert this?

To get from \(ax+b\) back to \(x\), ordinarily we would subtract \(b\) and then divide by \(a\). Now we are working over \(\mathbb{Z}_{n}\), so is that possible? We'll need our first “extra” condition.

To decode this particular example, then, we need to first subtract 18, then multiply by an inverse to 5 mod (677) (which turns out to be 271):

The proof of the pudding is in the eating - there's no way I get the original message back unless this works!

There is another way of using blocks of size two or more, which we won't pursue, but which is a big piece of how standard encryption works (see here and here). Let's look at our message again.

Now, in blocks of two, I will change my numbers by turning the first one into the sum of the numbers modulo 26 and leaving the second one alone. So for the second block \((20,8)\), I will change that block to \((28,8)\), which modulo 26 becomes \((2,8)\).

This turns out to be the same thing as multiplying the list of vectors of length two by the matrix \[\left(\begin{matrix}1& 1\\0& 1\end{matrix}\right)\; !\] To invert this cipher, we would need an inverse to this matrix modulo 26. (Which is why people don't do something quite so naive, as there aren't too many inverses modulo 26.)

In any case, this is another connection to the rest of mathematics! And it is a huge reason why linear algebra over finite algebraic structures is VERY important in security.

Now, there is another type of encryption, which is rather different. There exists the possibility that everybody knows the key to encrypt, while only the legitimate person knows how to decrypt. This is called asymmetric key cryptography.

This may seem odd. But in practice today, people really do just post their encryption keys on the Internet! Here is one of a fairly well-known open-source software advocate, for example.

Then, in theory, anyone who wants to send Person XYZ a secure message could use this key, but only Person XYZ can decrypt it - convenient! Such a system is called public-key cryptography, although of course it's only the encryption key that is actually public.