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 cryptography. The symmetry is that both people need to keep it secret. One early example of this supposedly goes back to C. Julius Caesar. To encrypt a message, first convert it to numbers, and then add three to each number (‘wrapping around’ as in modular arithmetic 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? Again, this is just modular arithmetic, modulo 26, so I added 3 mod \((26)\).

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 \begin{equation*}m\equiv x+a \text{ mod}(n)\end{equation*} 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. In the next Sage cell, the code requires a message with an even number of letters; can you make it more flexible?

Let's do something a little more interesting to encrypt our ‘secret’ about how cool math is. What else has inverses?

Well, sometimes multiplication mod \((n)\) does! We could make a cipher that gets \(m\) by performing \begin{equation*}m\equiv ax+b \text{ (mod }n)\; .\end{equation*} 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):

You should get ‘MathIsCool’ or whatever message you originally used.

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 very far, 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 corresponding list of vectors of length two by a matrix! \begin{equation*}\left(\begin{matrix}1& 1\\0& 1\end{matrix}\right)\end{equation*} To invert this cipher, we would need an inverse to this matrix modulo 26. (People don't do something quite so naive, as there aren't too many inverses modulo 26, but for our purposes this suffices.)

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.

Finally 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 idea may seem odd. But in practice today, people really do just post their encryption keys on the Internet! In the live book, this links the public key of a fairly well-known open-source software advocate, for example.

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 an implementation of an asymmetric system is called public-key cryptography, although of course it's only the encryption key that is actually public.

In this chapter, we will see examples of both symmetric and asymmetric systems, but the main point is to lead up to the mathematics of basic public key systems.