section-private-key-crypt.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section7.1Private Key Cryptography

¶

In or 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. We could have used a larger alphabet or a different shift.

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

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 , 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)^{\rm t}\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.