AATA Private Key Cryptography

Section 7.1 Private 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.

🔗

Example 7.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.

🔗

Example 7.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.

🔗

Example 7.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*}

🔗

Example 7.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.

🔗

Prev Top Next