$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section7.1Private Key Cryptography

In single or private key cryptosystems the same key is used for both encrypting and decrypting messages. To encrypt a plaintext message, we apply to the message some function which is kept secret, say $f\text{.}$ This function will yield an encrypted message. Given the encrypted form of the message, we can recover the original message by applying the inverse transformation $f^{-1}\text{.}$ The transformation $f$ must be relatively easy to compute, as must $f^{-1}\text{;}$ however, $f$ must be extremely difficult to guess from available examples of coded messages.

###### Example7.1

One of the first and most famous private key cryptosystems was the shift code used by Julius Caesar. We first digitize the alphabet by letting $\text{A} = 00, \text{B} = 01, \ldots, \text{Z} = 25\text{.}$ The encoding function will be

\begin{equation*} f(p) = p + 3 \bmod 26; \end{equation*}

that is, $A \mapsto D, B \mapsto E, \ldots, Z \mapsto C\text{.}$ The decoding function is then

\begin{equation*} f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26. \end{equation*}

Suppose we receive the encoded message DOJHEUD. To decode this message, we first digitize it:

\begin{equation*} 3, 14, 9, 7, 4, 20, 3. \end{equation*}

Next we apply the inverse transformation to get

\begin{equation*} 0, 11, 6, 4, 1, 17, 0, \end{equation*}

or ALGEBRA. Notice here that there is nothing special about either of the numbers $3$ or $26\text{.}$ We could have used a larger alphabet or a different shift.

Cryptanalysis is concerned with deciphering a received or intercepted message. Methods from probability and statistics are great aids in deciphering an intercepted message; for example, the frequency analysis of the characters appearing in the intercepted message often makes its decryption possible.

###### Example7.2

Suppose we receive a message that we know was encrypted by using a shift transformation on single letters of the $26$-letter alphabet. To find out exactly what the shift transformation was, we must compute $b$ in the equation $f(p) = p + b \bmod 26\text{.}$ We can do this using frequency analysis. The letter $\text{E} = 04$ is the most commonly occurring letter in the English language. Suppose that $\text{S} = 18$ is the most commonly occurring letter in the ciphertext. Then we have good reason to suspect that $18 = 4 + b \bmod 26\text{,}$ or $b= 14\text{.}$ Therefore, the most likely encrypting function is

\begin{equation*} f(p) = p + 14 \bmod 26. \end{equation*}

The corresponding decrypting function is

\begin{equation*} f^{-1}(p) = p + 12 \bmod 26. \end{equation*}

It is now easy to determine whether or not our guess is correct.

Simple shift codes are examples of monoalphabetic cryptosystems. In these ciphers a character in the enciphered message represents exactly one character in the original message. Such cryptosystems are not very sophisticated and are quite easy to break. In fact, in a simple shift as described in Example 7.1, there are only $26$ possible keys. It would be quite easy to try them all rather than to use frequency analysis.

Let us investigate a slightly more sophisticated cryptosystem. Suppose that the encoding function is given by

\begin{equation*} f(p) = ap + b \bmod 26. \end{equation*}

We first need to find out when a decoding function $f^{-1}$ exists. Such a decoding function exists when we can solve the equation

\begin{equation*} c = ap + b \bmod 26 \end{equation*}

for $p\text{.}$ By Proposition 3.4, this is possible exactly when $a$ has an inverse or, equivalently, when $\gcd( a, 26) =1\text{.}$ In this case

\begin{equation*} f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26. \end{equation*}

Such a cryptosystem is called an affine cryptosystem.

###### Example7.3

Let us consider the affine cryptosystem $f(p) = ap + b \bmod 26\text{.}$ For this cryptosystem to work we must choose an $a \in {\mathbb Z}_{26}$ that is invertible. This is only possible if $\gcd(a, 26) = 1\text{.}$ Recognizing this fact, we will let $a = 5$ since $\gcd(5, 26) = 1\text{.}$ It is easy to see that $a^{-1} = 21\text{.}$ Therefore, we can take our encryption function to be $f(p) = 5p + 3 \bmod 26\text{.}$ Thus, ALGEBRA is encoded as $3, 6, 7, 23, 8, 10, 3\text{,}$ or DGHXIKD. The decryption function will be

\begin{equation*} f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26. \end{equation*}

A cryptosystem would be more secure if a ciphertext letter could represent more than one plaintext letter. To give an example of this type of cryptosystem, called a polyalphabetic cryptosystem, we will generalize affine codes by using matrices. The idea works roughly the same as before; however, instead of encrypting one letter at a time we will encrypt pairs of letters. We can store a pair of letters $p_1$ and $p_2$ in a vector

\begin{equation*} {\mathbf p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}. \end{equation*}

Let $A$ be a $2 \times 2$ invertible matrix with entries in ${\mathbb Z}_{26}\text{.}$ We can define an encoding function by

\begin{equation*} f({\mathbf p}) = A {\mathbf p} + {\mathbf b}, \end{equation*}

where ${\mathbf b}$ is a fixed column vector and matrix operations are performed in ${\mathbb Z}_{26}\text{.}$ The decoding function must be

\begin{equation*} f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}. \end{equation*}
###### Example7.4

Suppose that we wish to encode the word HELP. The corresponding digit string is $7, 4, 11, 15\text{.}$ If

\begin{equation*} A = \begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}, \end{equation*}

then

\begin{equation*} A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}. \end{equation*}

If ${\mathbf b} = ( 2, 2)^\transpose\text{,}$ then our message is encrypted as RRGR. The encrypted letter R represents more than one plaintext letter.

Frequency analysis can still be performed on a polyalphabetic cryptosystem, because we have a good understanding of how pairs of letters appear in the English language. The pair th appears quite often; the pair qz never appears. To avoid decryption by a third party, we must use a larger matrix than the one we used in Example 7.4.