Cryptography is the study of methods of sending messages in disguised form. The message we want to send is called the plaintext and the disguised message is called the ciphertext. The process of converting a plaintext to a ciphertext is enciphering or encryption and the reverse process is deciphering or decryption. The plaintext and ciphertext are broken up into multiple message units (a single letter, a pair of letters, a triple of letters, …). An enciphering transformation is a function that takes any plaintext message unit and gives us a ciphertext message unit. Let $\mathcal{P}$ be the set of all possible plaintext massage units and $\mathcal{C}$ the set of all possible ciphertext message units. Then an enciphering transformation can be represented as a function $f: \mathcal{P}\longrightarrow\mathcal{C}$ (assumed to be a one-to-one correspondence) and the deciphering transformation is its inverse function $f^{-1}:\mathcal{C}\longrightarrow\mathcal{P}$. The functional composition
$$\mathcal{P}\stackrel{f}{\longrightarrow}\mathcal{C}\stackrel{f^{-1}}{\longrightarrow}\mathcal{P}$$
is a cryptosystem.
Making a Cryptosystem
First step is to label all possible plaintext message units and ciphertext message units by means of mathematical objects. For example, if our plaintext and ciphertext message units are single letters from A-Z and the blank, then we can label them as $0,1,2,\cdots,26$.
| A | B | C | D | E | F | G | H | I | J | K | L | M | N |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| O | P | Q | R | S | T | U | V | W | X | Y | Z | blank | |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
If we use digraphs, length-2 strings of letters, as message units, then we can label the digraph whose two letters correspond to $x,y\in\{0,1,2,\cdots,26\}$ by the integer $27x+y\in\{0,1,2,\cdots,728\}$. So, we view the individual letters as digits to the base 27 and the digraph as a 2-digit integer to that base. For instance, the digraph NO corresponds to $27\cdot 13+14=365$.
Example. Suppose we use the 26-letter alphabet A-Z with numerical equivalents 0-25. Let $P\in\{0,1,2,\cdots,25\}$ denotes a plaintext message unit. Define $f:\{0,1,2,\cdots,25\}\longrightarrow\{0,1,2,\cdots,25\}$ by
$$f(P)=\left\{\begin{array}{ccc}
P+3 & \mbox{if} & P<23\\
P-23 & \mbox{if} & P\geq 23
\end{array}\right.$$
Simply, $f(P)\equiv P+3\mod 26$. Let us encipher YES. Each letter corresponds to plaintext units 24, 4, 18, respectively. The enciphering (add 3 mod 26) of each plaintext unit is 1, 7, 21, respectively and their corresponding alphabet letters are BHV. Let us now decipher ZKB. Each letter corresponds to ciphertext units 25, 10, 1, respectively. By subtracting 3 mod 26, each unit is deciphered to 22, 7, 24, respectively. The corresponding letters are WHY.
The cryptosystem shown in the above example is one of the oldest cryptosystems. It was invented and used by Julius Caesar. The cryptosystem can be written, in general, as
\begin{equation}
\label{eq:shiftransf}
C=f(P)\equiv P+b\mod N
\end{equation}
\eqref{eq:shiftransf} is called the shift transformation.
Breaking the Code
We need to know two types of information to break a code:
- The first type of information we need to know is the nature (structure) of the cryptosystem. For example, we know the cryptosystem uses a shift transformation on single letters of the 26-letter alphabet A-Z with numerical equivalents 0-25.
- The second type of information we need to know is a specific choice of parameters connected with the cryptosystem. In the shit transformation, it is $b$. The parameter $b$ is called a key, or more specifically the enciphering key.
Example. The intercepted message is FQOCUDEM and we would like to decipher this. Suppose we know that it was enciphered using a shift transformation on single letters of the 26-letter alphabet A-Z with numerical equivalents 0-25. So we need to figure out the parameter $b$. Suppose that we have already intercepted a long string of ciphertext. The most frequently occurring letter in English text is E and the second most frequently occurring letter is T according to the finding by Samuel Morse (1791-1872), the inventor of Morse code. He obtained the result by counting the number of letters in sets of printers’ type. E is also most frequently occurring letter in the words listed in the main entries of the Concise Oxford English Dictionary (9th Edition, 1995) with the percentage of words the letter E appears in 11.16% but the second most frequently occurring letter in English vocabulary is A (8.5%) and T (7%) is 5th most frequently occurring letter. See here for more information. It is reasonable to assume that the most frequently occurring letter in the ciphertext is the encryption of E. Suppose that the letter U appears the most frequently in the ciphertext. This indicates the shift $b$ take E=4 to U=20, i.e. $20\equiv 4+b\mod 26$, so $b=16$. To decipher the message we just need to subtract 16 mod 26 from the numerical equivalents of FQOCUDEM.
\begin{align*} \mbox{FQOCUDEM}&= 5\ 16\ 14\ 2\ 20\ 3\ 4\ 12\\ &\mapsto 15\ 0\ 24\ 12\ 4\ 13\ 14\ 22\\ &=\mbox{PAYMENOW} \end{align*}
The type of analysis we have done in this example by considering the most frequently occurring letter is called the frequency analysis.
The cryptosystem by a shift transformation is so simple that it can easily be broken. We can make an improvement by using a more general type of transformation on $\mathbb{Z}/N\mathbb{Z}$, called an affine map:
\begin{equation}
\label{eq:affine}
C\equiv aP+b\mod N
\end{equation}
where $a$ and $b$ are fixed integers which form the enciphering key.
Example. Let us encipher PAYMENOW using the affine transformation \eqref{eq:affine} with $a=7$, $b=12$.
\begin{align*} 15\ 0\ 24\ 12\ 4\ 13\ 14\ 22&\mapsto 13\ 12\ 24\ 18\ 14\ 25\ 6\ 10\\ &=\mbox{NMYSOZGK} \end{align*}
Deciphering a message that was enciphered by means of the affine map \eqref{eq:affine} can be achieved by
\begin{equation}
\label{eq:affine2}
\begin{aligned}
P&\equiv a^{-1}C-a^{-1}b\mod N\\
P&\equiv a’C+b’\mod N
\end{aligned}
\end{equation}
where $a^{-1}$ is the multiplicative inverse of $a$. This works only if $(a,N)=1$, otherwise we cannot solve \eqref{eq:affine} for $P$ in terms of $C$. Thus, $a$ is required to be in
$$(\mathbb{Z}/N\mathbb{Z})^*=\{[a]\in\mathbb{Z}/N\mathbb{Z}: (a,N)=1\}$$ so that the map $C$ can be a one-to-one correspondence. $((\mathbb{Z}/N\mathbb{Z})^*,\cdot)$ is a multiplicative abelian group.
Example. Suppose that we know the most frequently occurring letter of ciphertext is K and the second most frequently occurring one is D. It is reasonable to assume that these are E and T, the two most frequently occurring letters in the English language.
\begin{align*} 10a’+b’&\equiv 4\mod 26\\ 3a’+b’&\equiv 19\mod 26 \end{align*}
Subtracting the second equation from the first, we obtain $7a’\equiv 11\mod 26$ and so $a’\equiv 7^{-1}\cdot 11\mod 26\equiv 15\cdot 11\mod 26\equiv 9\mod 26$. $b’$ is obtained from the first equation by $b’\equiv 4-10a’\mod 26\equiv 18\mod 26$. Hence, messages can be deciphered by means of the formula $P\equiv 9C+18\mod 26$.
$$\varphi(26)=\varphi(2\cdot 13)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{13}\right)=12$$
so we know $(\mathbb{Z}/26\mathbb{Z})^*$ has 12 elements. $(\mathbb{Z}/26\mathbb{Z})^*$ is given by
$$(\mathbb{Z}/26\mathbb{Z})^*={1,3,5,7,9,11,15,17,19,21,23,25}$$
Digraph Transformations
Suppose that our plaintext and ciphertext message units are two-letter blocks (digraphs). If the entire plaintext has an odd number of letters, then in order to obtain a whole number of digraphs, we add on an extra letter at the end. For instance, we can add on the blank if our alphabet contains it. If we are using the 26-letter alphabet, we can add on another letter that may not cause a trouble. Each digraph is assigned to a numerical equivalent as a 2-digit base-$N$ integer $xN+y$, where $x$ is the numerical equivalent of the first letter in the digraph and $y$ is the numerical equivalent of the second letter in the digraph. This gives a one-to-one correspondence between the set of all digraphs in the $N$-letter alphabet and $\mathbb{Z}/N^2\mathbb{Z}=\{0,1,2,\cdots,N^2-1\}$. Define the encryption of $P$ to be $C\equiv a P+b\mod N^2$, where $(a,N^2)=1$ i.e. $a\in(\mathbb{Z}/N^2\mathbb{Z})^*$.
Example. Suppose that we are using 26-letter alphabet and the digraph enciphering transformation $C\equiv 159P+580\mod 676$. The digraph NO has numerical equivalent $13*26+14=352$. The ciphertext is $C\equiv 159\cdot 352+580\mod 676\equiv 440\mod 676$. $440=16\cdot 26+24$, so its equivalent digraph is QY. The digraph ON has numerical equivalent $14\cdot 26+13=377$ and its ciphertext is $C\equiv 159\cdot 377+580\mod 676\equiv 359\mod 676$. Since $359=13\cdot 26+21$, its digraph equivalent is NV.
To break a digraph encryption system $C\equiv aP+b\mod N^2$ we need to know the ciphertext corresponding to two different plaintext message units. The message units are digraphs, so for frequency analysis count which two-letter blocks occur the most often in a long string of ciphertext. If we use the 26-letter alphabet, TH and HE are known to be the first and the second most frequently occurring digraphs.
Example. You know that your adversary is using a cryptosystem with 27-letter alphabet A-Z, the blank. Each diagraph corresponds to an integer in $\mathbb{Z}/729\mathbb{Z}=\{0,1,2,\cdots, 728=27^2-1\}$. As previously seen, if two letters in the digraph have numerical equivalent of $x$ and $y$, then the digraph has the numerical equivalent $27x+y$. Suppose that a study of a large sample of ciphertext shows that the most frequently occurring digraphs are ZA, IA and IW in that order. Suppose that the most frequently occurring digraphs in the English language (for text written in 27-letter alphabet) are Eblank, Sblank, blankT in that order. We also know that the cryptosystem uses an affine transformation $\mod 729$. find the deciphering key and read the message NDXBHO. Also find the enciphering key.
Solution.
\begin{align*} C&\equiv aP+b\mod 729\\ P&\equiv a’C+b’\mod 729 \end{align*}
where $a’=a^{-1}\in\mathbb{Z}/27\mathbb{Z}$ and $b’=-a^{-1}b\in\mathbb{Z}/27\mathbb{Z}$.
The numerical equivalents of ZA, IA and IW, respectively, are
\begin{align*} 25\cdot 27+0&=675\\ 8\cdot 27+0&=216\\ 8\cdot 27+22&=238 \end{align*}
The numerical equivalents of Eblank, Sblank, blankT, respectively, are
\begin{align*} 4\cdot 27+26&=134\\ 18\cdot 27+26&=512\\ 26\cdot 27+19&=721 \end{align*}
Now, we have the equations
\begin{align*} 675a’+b’&\equiv 134\mod 729\\ 216a’+b’&\equiv 512\mod 729\\ 238a’+b’&\equiv 721\mod 729 \end{align*}
One may think only two of theses equations would be needed to determine $a’$ and $b’$ but that is not necessarily the case. Subtracting the second equation from the first, we obtain $459a’\equiv 351\mod 729$. This equation however does not have a unique solution because $(459,729)=27$. (There are 27 solutions modulo 729, $a’=104+27t$, $-3\leq t\leq 23$.) If we subtract the third equation from the first, we obtain $437a’\equiv 142\mod 729$. $(437,729)=1$, i.e. there exists $437^{-1}\in\mathbb{Z}/729\mathbb{Z}$. Hence, the equation has a unique solution $a’\equiv 437^{-1}\cdot 142\mod 729$.
Finding $437^{-1}\in\mathbb{Z}/729\mathbb{Z}$:
\begin{align*} 729&=437+292\\ 437&=292+145\\ 292&=2\cdot 145+2\\ 145&=72\cdot 2+1 \end{align*}
and
\begin{align*} 1&=145-72\cdot 2\\ &=145-72(292-2\cdot 145)\\ &=145\cdot 145-97\cdot 292\\ &=145(437-292)-97\cdot 292\\ &=145\cdot 437-217\cdot 292\\ &=145\cdot 437-217(729-437)\\ &\equiv 362\cdot 437\mod 729 \end{align*}
Therefore, $362\equiv 437^{-1}\mod 27$. $a’$ and $b’$ are then given by
\begin{align*} a’&\equiv 362\cdot 142\mod 729\equiv 374\mod 729\\ b’&\equiv 134-675\cdot 374\mod 729\equiv 647\mod 729 \end{align*}
The numerical equivalents of ND, XB, and HO are 354, 622, 203, respectively. The deciphering of these digraphs is given by
\begin{align*} a’\cdot 354+b’&=374\cdot 354+647\equiv 365\mod 729\\ a’\cdot 622+b’&=374\cdot 622+647\equiv 724\mod 729\\ a’\cdot 203+b’&=374\cdot 203+647\equiv 24\mod 729 \end{align*}
\begin{align*} 365&=27\cdot 13+14\mapsto\mbox{NO}\\ 724&=27\cdot 26+22\mapsto\mbox{blankW}\\ 24&=27\cdot 0+24\mapsto\mbox{AY} \end{align*}
The deciphered message is NO WAY. The enciphering keys $a$ and $b$ are given by
\begin{align*} a&\equiv(a’)^{-1}\mod 729\equiv 374^{-1}\mod 729\equiv 614\mod 729\\ b&\equiv -ab’\mod 729\equiv -614\cdot 647\mod 729\equiv 47\mod 729 \end{align*}