Skip to main content \(\newcommand{\longdivision}[2]{#1\big)\!\!\overline{\;#2}}
\newcommand{\mlongdivision}[2]{\longdivision{#1}{#2}}
\renewcommand{\emptyset}{\{\}}
\newcommand{\blanksp}{\underline{\hspace{.25in}}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\cspace}{-}
\newcommand{\Ta}{\mathtt{a}}
\newcommand{\Tb}{\mathtt{b}}
\newcommand{\Tc}{\mathtt{c}}
\newcommand{\Td}{\mathtt{d}}
\newcommand{\Te}{\mathtt{e}}
\newcommand{\Tf}{\mathtt{f}}
\newcommand{\Tg}{\mathtt{g}}
\newcommand{\Th}{\mathtt{h}}
\newcommand{\Ti}{\mathtt{i}}
\newcommand{\Tj}{\mathtt{j}}
\newcommand{\Tk}{\mathtt{k}}
\newcommand{\Tl}{\mathtt{l}}
\newcommand{\Tm}{\mathtt{m}}
\newcommand{\Tn}{\mathtt{n}}
\newcommand{\To}{\mathtt{o}}
\newcommand{\Tp}{\mathtt{p}}
\newcommand{\Tq}{\mathtt{q}}
\newcommand{\Tr}{\mathtt{r}}
\newcommand{\Ts}{\mathtt{s}}
\newcommand{\Tt}{\mathtt{t}}
\newcommand{\Tu}{\mathtt{u}}
\newcommand{\Tv}{\mathtt{v}}
\newcommand{\Tw}{\mathtt{w}}
\newcommand{\Tx}{\mathtt{x}}
\newcommand{\Ty}{\mathtt{y}}
\newcommand{\Tz}{\mathtt{z}}
\newcommand{\So}{\Tf}
\newcommand{\Sno}{\Tg}
\newcommand{\Si}{\Th}
\newcommand{\Sni}{\Tj}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\ZZ}{\Z}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RR}{\R}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\fmod}{\bmod}
\newcommand{\fdiv}{\,\mathrm{div}\,}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\nr}[1]{\##1}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\newcommand{\sol}[1]{{\color{blue}\textit{#1}}}
\newcommand{\gro}[1]{{\color{gray}#1}}
\newcommand{\todo}[1]{{\color{purple}TO DO: #1}}
\newcommand{\fixme}[1]{{\color{red}FIX ME: #1}}
\newcommand{\checkme}[1]{{\color{green}CHECK ME: #1}}
\newcommand{\degre}{^\circ}
\newcommand{\vect}[1]{\overrightarrow{#1}}
\newcommand{\nix}{}
\newcommand{\cox}[1]{\fcolorbox[HTML]{000000}{#1}{\phantom{M}}}
\newcommand{\tox}[1]{\texttt{\##1} \amp \cox{#1}}
\newcommand{\ttx}[1]{\texttt{\##1}}
\newcommand{\mox}[1]{\mathtt{\##1}}
\newcommand{\xx}{\mathtt{\#}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
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:
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:
Finally, he decodes this with the decoding function
\(C^{-1}\) from
Figure 8.1 and gets the decrypted plain text message:
\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.
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{.}\)
Checkpoint 8.30 . Encrypting with a substitution cipher.
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{.}\)
Checkpoint 8.32 . Decrypting with a substitution cipher.
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:
\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:
\(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\)
Then he decrypts this sequence of numbers with the function
\(D = E^{-1}\text{:}\)
\(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\)
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*}
