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

Next we apply the inverse transformation to get

\begin{equation*} 0, 11, 6, 4, 1, 17, 0\text{,} \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\text{.} \end{equation*}

The corresponding decrypting function is

\begin{equation*} f^{-1}(p) = p + 12 \bmod 26\text{.} \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\text{.} \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\text{.} \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\text{.} \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}\text{.} \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}\text{,} \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}\text{.} \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}\text{,} \end{equation*}

then

\begin{equation*} A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}\text{.} \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.