Section11.2Encryption

We will spend most of our time talking about enciphering, or encrypting, messages. This is the difficult part, after all, the details of which we want to keep secret. What is cool about modern ciphers is that we actually expect that any eavesdropper will know how we do the encryption; they just don't know the key, which is the specific numbers we use to do it. Reversing this process (hopefully only done by the person you want to receive your message!) is called decryption. Sometimes you need a different set of numbers to decrypt, in which case we distinguish between the encryption key and the decryption key.

Remark11.2.1

Sage note:
Don't forget to evaluate this so we can use words as messages instead of just numbers.

Subsection11.2.1Simple ciphers

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.

Subsection11.2.2Decryption and Inverses

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.

Subsection11.2.3Getting more sophisticated

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!

Subsection11.2.4Linear Algebra and Encryption

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.

Subsection11.2.5Asymmetric Key Cryptography

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.