# 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

$f(p) = p + 3 \bmod 26; \nonumber$

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

Solution

The decoding function is then

$f^{-1}(p) = p - 3 \bmod 26 = p + 23 \bmod 26\text{.} \nonumber$

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

$3, 14, 9, 7, 4, 20, 3\text{.} \nonumber$

Next we apply the inverse transformation to get

$0, 11, 6, 4, 1, 17, 0\text{,} \nonumber$

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{.}$$

Solution

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

$f(p) = p + 14 \bmod 26\text{.} \nonumber$

The corresponding decrypting function is

$f^{-1}(p) = p + 12 \bmod 26\text{.} \nonumber$

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

$f(p) = ap + b \bmod 26\text{.} \nonumber$

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

$c = ap + b \bmod 26 \nonumber$

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

$f^{-1}(p) = a^{-1} p - a^{-1} b \bmod 26\text{.} \nonumber$

Such a cryptosystem is called an affine cryptosystem.

## Example $$7.3$$

Let us consider the affine cryptosystem $$f(p) = ap + b \bmod 26\text{.}$$

Solution

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

$f^{-1}(p) = 21 p - 21 \cdot 3 \bmod 26 = 21 p + 15 \bmod 26\text{.} \nonumber$

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

${\mathbf p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}\text{.} \nonumber$

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

$f({\mathbf p}) = A {\mathbf p} + {\mathbf b}\text{,} \nonumber$

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

$f^{-1}({\mathbf p}) = A^{-1} {\mathbf p} - A^{-1} {\mathbf b}\text{.} \nonumber$

## Example $$7.4$$

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

$A = \begin{pmatrix} 3 & 5 \\ 1 & 2 \end{pmatrix}\text{,} \nonumber$

Solution

then

$A^{-1} = \begin{pmatrix} 2 & 21 \\ 25 & 3 \end{pmatrix}\text{.} \nonumber$

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

This page titled 7.1: Private Key Cryptography is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Thomas W. Judson (Abstract Algebra: Theory and Applications) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.