Other Substitution Ciphers

Section 8.4 Other Substitution Ciphers

The Caesar cipher is an example of a substitution cipher, where one character is replaced by another. Other substitution ciphers use more complicated rules or tables for the encoding of characters. We give an example for another substitution cipher given by an algebraic rule.

We may describe a Caesar cipher with an arbitrary \(n\in\Z_{27}\) as a key using the following functions:

\(C:\A\to\Z_{27} \)	as defined in Figure 8.1
\(E:\Z_{27}\to\Z_{27} \)	given by \(E(x)= (x-n) \fmod 27\)
\(E^{-1}:\Z_{27}\to\Z_{27} \)	given by \(E^{-1}(x)= (x+n) \fmod 27\)
\(C^{-1}:\Z_{27}\to\A \)	as defined in Figure 8.1

The encryption function for a Caesar cipher is \(J=C^{-1}\circ E\circ C\text{.}\) It first encodes each character into an element of \(\Z_{27}\) using the function \(C\text{.}\) Then, the function \(E\) does the shift for the encryption by subtracting \(n\) from each number and determining the result modulo \(n\text{,}\) where \(n\) is the key for the particular Caesar cipher. Finally, it converts each new number into a new character using the function \(C^{-1}\text{.}\)

The decryption function for a Caesar cipher is \(J^{-1}=C^{-1}\circ E^{-1}\circ C\text{.}\) It first encodes each character into an element of \(\Z_{27}\) using the function \(C\text{.}\) Then, the function \(E^{-1}\) does the shift for the decryption by adding \(n\) from each number and determining the result modulo \(n\text{,}\) where \(n\) is the key for the particular Caesar cipher. Finally, it converts each new number into a new character using the function \(C^{-1}\text{.}\)

Example 8.26. Caesar cipher shifting by \(11\) characters.

Alice and Bob agree to encrypt their communication with the Caesar cipher using the key \(n=11\text{.}\) Alice sends Bob the encrypted message:

\begin{equation*} \mathtt{ndjpqgupauqkycwpixupqbugysqcphusidg} \end{equation*}

To decrypt the message, Bob first encodes the cipher text with the encoding function \(C\) from Figure 8.1 and gets:

14, 4, 10, 16, 17, 7, 21, 16, 1, 21, 17, 11, 25, 3, 23, 16, 9, 24, 21, 16, 17, 2, 21, 7, 25, 19, 17, 3, 16, 8, 21, 19, 9, 4, 7

Next, he applies the function \(E^{-1}\) with \(n=11\) to each of the numbers by adding 11 and determining the result modulo 27 to obtain:

25, 15, 21, 0, 1, 18, 5, 0, 12, 5, 1, 22, 9, 14, 7, 0, 20, 8, 5, 0, 1, 13, 5, 18, 9, 3, 1, 14, 0, 19, 5, 3, 20, 15, 18

Finally, he decodes this with the decoding function \(C^{-1}\) from Figure 8.1 and gets the decrypted plain text message

from the signs along the border (that is, along the wall) between the American sector and the Soviet sector of Berlin, before the fall of the Berlin wall in 1989.

\begin{equation*} \mathtt{you{\cspace}are{\cspace}leaving{\cspace}the{\cspace}american{\cspace}sector} \end{equation*}

Instead of formally applying the functions \(C\text{,}\) \(E^{-1}\text{,}\) and \(C^{-1}\text{,}\) Bob could have also created a table as in Figure 8.17.(b) or counted 11 letters forward (wrapping around to \(\cspace\) after \(\mathtt{z}\)) from the letters in the cipher text or used the decoder disc in Example 8.23.

Checkpoint 8.27. Caesar cipher with composition of functions.

Alice and Bob meet and agree to use the code

\begin{equation*} C:\lbrace \mathtt{-},\mathtt{a},\mathtt{b},\mathtt{c},...,\mathtt{z}\rbrace \to \lbrace 0,1,2,3,...26\rbrace,\\ C(\mathtt{-})=0, C(\mathtt{a})=1,...,C(\mathtt{z})=26. \end{equation*}

to map characters to integers and to use the function

\begin{equation*} E: \lbrace 0,1,2,3,...26\rbrace \to \lbrace 0,1,2,3,...26\rbrace,\\ E(x) = (x+12) \bmod 27 \end{equation*}

for encryption. The inverse of the function E is

\begin{equation*} E^{-1}: \lbrace 0,1,2,...,26\rbrace \to \lbrace 0,1,2,...,26\rbrace ,\\ E^{-1}(x) = (x-12) \bmod 27 \end{equation*}

They also agree to send their messages as sequences of integers.

Alice wants to send Bob the secret message:

\begin{equation*} \mathtt{pigs} \end{equation*}

She encodes the characters with the function and obtains:

\(C(\mathtt{p}) =\) , \(C(\mathtt{i}) =\) , \(C(\mathtt{g}) =\) , \(C(\mathtt{s}) =\) .

She encrypts these with the function \(E\) and gets

\(E(C(\mathtt{p})) =\) , \(E(C(\mathtt{i})) =\) , \(E(C(\mathtt{g})) =\) , \(E(C(\mathtt{s})) =\) .

Alice sends these integers to Bob.

Bob receives the message and evaluates the function \(E^{-1}\) at the integers send by Alice:

\(E^{-1}(E(C(\mathtt{p}))) =\) , \(E^{-1}(E(C(\mathtt{i}))) =\) , \(E^{-1}(E(C(\mathtt{g}))) =\) , \(E^{-1}(E(C(\mathtt{s}))) =\) .

An application of C\({}^{-1}\) yields:

\(C^{-1}(E^{-1}(E(C(\mathtt{p})))) =\) , \(C^{-1}(E^{-1}(E(C(\mathtt{i})))) =\) , \(C^{-1}(E^{-1}(E(C(\mathtt{g})))) =\) , \(C^{-1}(E^{-1}(E(C(\mathtt{s})))) =\) .

In the following we use these methods with slightly more complicated functions for the encryption and decryption. An introduction is given in the video in Figure 8.28. It is followed by a more detailed discussion.

Figure 8.28. Other Substitution Ciphers by Matt Farmer and Stephen Steward

We now encrypt a problem with a substitution cipher.

Problem 8.29. Encrypting a word with a substitution cipher.

Encrypt the word \(\mathtt{ball}\) with the encryption function \(E:\Z_{27}\to\Z_{27}\) given by \(E(x)=((4\cdot x)+5)\fmod 27\text{.}\) Give the cipher text as characters.

Solution.

With the encoding function \(C\) we get \(C(\mathtt{b})=2\text{,}\) \(C(\mathtt{a})=1\text{,}\) \(C(\mathtt{l})=12\)

Applying the encryption function \(E\) we obtain:

\begin{align*} E(2)\amp =((4\cdot 2)+5)\fmod 27 = 13\\ E(1)\amp =((4\cdot 1)+5)\fmod 27 = 9\\ E(12)\amp =((4\cdot 12)+5)\fmod 27 = 26 \end{align*}

Now we convert these values back to characters with the decoding function \(C^{-1}\text{:}\)

\begin{align*} C^{-1}(13)\amp=\mathtt{m}\\ C^{-1}(9)\amp=\mathtt{i}\\ C^{-1}(26)\amp=\mathtt{z} \end{align*}

So the encrypted word is \(\mathtt{mizz}\text{.}\)

Go through the process used in the problem yourself in Checkpoint 8.30.

Checkpoint 8.30. Encrypting with a substitution cipher.

Alice wants to send this message to Bob:

\begin{equation*} \mathtt{element} \end{equation*}

First she applies the encoding function

and obtains this sequence of integers:

Then Alice encrypts the message using the encryption function

\begin{equation*} E: \lbrace 0,1,2,3,\dots,26\rbrace \to \lbrace 0,1,2,3,\dots,26\rbrace,\\ E(x) = (2\cdot x + 3) \bmod 27. \end{equation*}

She gets the sequence of integers:

For transmission she converts the integers back into characters using the inverse of the function C:

We now decrypt a problem with a substitution cipher.

Problem 8.31. Decrypting a word with a substitution cipher.

Decrypt the cipher text

\begin{equation*} \mathtt{bilt} \end{equation*}

with the decryption function \(D:\Z_{27}\to\Z_{27}\) given by \(D(x)=(7\cdot x)\fmod 27\text{.}\) Give the cipher text as characters.

Solution.

With the encoding function \(C\) we get:

\begin{align*} C(\mathtt{b})\amp=2\\ C(\mathtt{i})\amp=9\\ C(\mathtt{l})\amp=12\\ C(\mathtt{t})\amp=20 \end{align*}

Applying the decryption function \(D\) we obtain:

\begin{align*} D(2)\amp=(7\cdot 2)\fmod 27 = 14\\ D(9)\amp=(7\cdot 9)\fmod 27 = 9\\ D(12)\amp=(7\cdot 12)\fmod 27 = 3\\ D(12)\amp=(7\cdot 12)\fmod 27 = 3\\ D(20)\amp=(7\cdot 20)\fmod 27 = 5 \end{align*}

Now we convert these values back to characters with the decoding function \(C^{-1}\text{:}\)

\begin{align*} C^{-1}(14)\amp=\mathtt{n}\\ C^{-1}(9)\amp=\mathtt{i}\\ C^{-1}(3)\amp=\mathtt{c}\\ C^{-1}(5)\amp=\mathtt{e} \end{align*}

So the decrypted word is \(\mathtt{nice}\text{.}\)

Go through the process used in the problem yourself in Checkpoint 8.32.

Checkpoint 8.32. Decrypting with a substitution cipher.

Bob receives an encrypted message from Alice:

\begin{equation*} \mathtt{m}\mathtt{-}\mathtt{m}\mathtt{b}\mathtt{m}\mathtt{d}\mathtt{p} \end{equation*}

First he applies the encoding function

and obtains this sequence of integers:

Bob decrypts the message using the decryption function

\begin{equation*} D: \lbrace 0,1,2,3,...26\rbrace \to \lbrace 0,1,2,3,...26\rbrace\\ D(x) = (14 \cdot (x-3)) \bmod 27. \end{equation*}

He gets the sequence of integers:

Applying the inverse of the encoding function \(C\) Bob obtains the plain text:

Not all functions from \(\Z_{27}\) to \(\Z_{27}\) are invertible. In the following we verify that two such functions are indeed inverses.

Example 8.33. Inverse of an encryption function.

Alice and Bob want to use the function

\begin{equation*} E:\Z_{27}\to\Z_{27},\;E(c)=(7\cdot c)\fmod 27 \end{equation*}

for the encryption. However, they need to also determine if \(E\) has an inverse function so that the encrypted messages can be decrypted. They notice that

\begin{equation*} (7\cdot 4)\fmod 27=28\fmod 27=1\text{,} \end{equation*}

which leads them to hypothesize that the function

\begin{equation*} D:\Z_{27}\to\Z_{27},\;D(b)=(4\cdot b)\fmod 27 \end{equation*}

should be the inverse of the function \(E\text{.}\) To verify their hypothesis, they compute:

\begin{align*} D\left(E(c)\right) \amp =D\left((7\cdot c)\fmod 27\right)\\ \amp =\left(4 \cdot (7\cdot c)\fmod 27\right) \fmod 27\\ \amp=(4\cdot 7\cdot c)\fmod 27\\ \amp =(28\cdot c)\fmod 27\\ \amp =\left((28\fmod 27)\cdot c\right)\fmod 27\\ \amp =(1\cdot c)\fmod 27\\ \amp =c \fmod 27\\ \amp =c \end{align*}

They conclude that \(D\) is the inverse of \(E\text{,}\) So \(E\) is a useful encryption function and the corresponding decryption function is \(D\text{.}\)

We now use the encryption function and decryption function from the previous example to encrypt and decrypt a message.

Example 8.34.

Alice and Bob decide to use the encryption function

\begin{equation*} E:\Z_{27}\to\Z_{27},\;E(c)=(7\cdot c)\fmod 27 \end{equation*}

and the decryption function

\begin{equation*} D:\Z_{27}\to\Z_{27},\;D(b)=(4\cdot b)\fmod 27 \end{equation*}

for their secure communication. They decide to transmit the messages as sequences of numbers.

Alice wants to send Bob the message:

⁴

from the Hitchhikers Guide to the Galaxy by Douglas Adams, 1978 (radio play), 1979 (novel)

\begin{equation*} \mathtt{here{\cspace}i{\cspace}am{\cspace}brain{\cspace}the{\cspace}size{\cspace}of{\cspace}a{\cspace}planet} \end{equation*}

She begins by encoding the message using the function \(C\) from Figure 8.1:

\(8\text{,}\) \(5\text{,}\) \(18\text{,}\) \(5\text{,}\) \(0\text{,}\) \(9\text{,}\) \(0\text{,}\) \(1\text{,}\) \(13\text{,}\) \(0\text{,}\) \(2\text{,}\) \(18\text{,}\) \(1\text{,}\) \(9\text{,}\) \(14\text{,}\) \(0\text{,}\) \(20\text{,}\) \(8\text{,}\) \(5\text{,}\) \(0\text{,}\) \(19\text{,}\) \(9\text{,}\) \(26\text{,}\) \(5\text{,}\) \(0\text{,}\) \(15\text{,}\) \(6\text{,}\) \(0\text{,}\) \(1\text{,}\) \(0\text{,}\) \(16\text{,}\) \(12\text{,}\) \(1\text{,}\) \(14\text{,}\) \(5\text{,}\) \(20\)

Then she encrypts this sequence of numbers with the function \(E\text{:}\)

\(2\text{,}\) \(8\text{,}\) \(18\text{,}\) \(8\text{,}\) \(0\text{,}\) \(9\text{,}\) \(0\text{,}\) \(7\text{,}\) \(10\text{,}\) \(0\text{,}\) \(14\text{,}\) \(18\text{,}\) \(7\text{,}\) \(9\text{,}\) \(17\text{,}\) \(0\text{,}\) \(5\text{,}\) \(2\text{,}\) \(8\text{,}\) \(0\text{,}\) \(25\text{,}\) \(9\text{,}\) \(20\text{,}\) \(8\text{,}\) \(0\text{,}\) \(24\text{,}\) \(15\text{,}\) \(0\text{,}\) \(7\text{,}\) \(0\text{,}\) \(4\text{,}\) \(3\text{,}\) \(7\text{,}\) \(17\text{,}\) \(8\text{,}\) \(5\)

For transmission, she applies the function \(C^{-1}\) from Figure 8.1 to obtain the cipher text:

\begin{equation*} \mathtt{bhrh{\cspace}i{\cspace}gj{\cspace}nrgiq{\cspace}ebh{\cspace}yith{\cspace}xo{\cspace}g{\cspace}dcgqhe} \end{equation*}

Finally, Alice sends this encrypted message to Bob. After receiving the message, Bob needs to decrypt the message. So, he begins by applying the function \(C\) to change the cipher text to numbers:

Then he decrypts this sequence of numbers with the function \(D = E^{-1}\text{:}\)

Finally, he applies \(C^{-1}\) to change the numbers back to plain text:

\begin{equation*} \mathtt{here{\cspace}i{\cspace}am{\cspace}brain{\cspace}the{\cspace}size{\cspace}of{\cspace}a{\cspace}planet} \end{equation*}

Prev Top Next