### Sage note 11.2.1. Reminder to evaluate definitions.

Don’t forget to evaluate the first cell of commands so we can use words as messages instead of just numbers.

We will spend most of our time talking about enciphering, or encrypting, messages. Such encryption 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 perform our mathematical encryption.

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.

Don’t forget to evaluate the first cell of commands so we can use words as messages instead of just numbers.

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)\text{.}\)

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\text{,}\) your key is \(a\text{,}\) and you are working modulo \((n)\text{,}\) 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\text{,}\) which is \(-a\text{.}\)

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

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

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)\text{.}
\end{equation*}

Here, let’s choose \(a=5\) and \(b=18\text{.}\) Since we have blocks of two letters each, the encoding mechanism could yield numbers up to \(26^2+26\text{,}\) so we’ll encrypt using \(n=709\text{,}\) the next prime after that.

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

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

To make modular encryption by a linear function workable, we need \(\gcd(a,n)=1\text{.}\) In that case there is a number \(a'\) such that

\begin{equation*}
a(a')\equiv 1\text{ (mod }n)\text{,}
\end{equation*}

so we can decode via

\begin{equation*}
m\longmapsto a'(m-b)\equiv x\text{ (mod }n)\text{.}
\end{equation*}

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

You should get ‘MathIsCool’ or whatever message you originally used. For convenience, you can use the cell below to do this in just one step, picking your own \(a\) and \(b\) along with your own (even length) message.

The proof of the pudding is in the eating. There’s no way I get the original message back unless this works! Can you modify the Sage cell above to break your message into groups of three letters instead?

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^{ 1 }

and here^{ 2 }

). Let’s look at our message again.

`en.wikipedia.org/wiki/Data_Encryption_Standard`

`en.wikipedia.org/wiki/Advanced_Encryption_Standard`

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)\text{,}\) I will change that block to \((28,8)\text{,}\) which modulo 26 becomes \((2,8)\text{.}\)

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^{ 3 }

the public key of a fairly well-known open-source software advocate, for example.

`www.catb.org/esr/gpg-public-key.asc`

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.