As we discussed here, the enciphering and deciphering transformations involve secret keys called encryption and decryption keys. These keys are shared only by the transmitter and the receiver, so they are called private keys. An Achilles heel of cryptographic communication systems that use private keys is that secret communications can take place only after a key is transmitted in secret over a totally secure communication channel. This is referred to as the CATCH 22 of cryptography. First there are two most famous people when it comes to cryptography and communications, way even more famous than the great mathematician Claude E. Shannon formerly at Bell Lab, who is dubbed the father of modern communication theory. They are Alice and Bob. Literally any books and papers on cryptography, communications, or even quantum computing would mention their names.

CATCH 22: Before the transmitter and the receiver Alice and Bob can communicate in secret, they must first communicate in secret.

There is more to this CATCH 22.

CATCH 22a: Even if Alice and Bob succeed in tansmitting their key over a secure communication channel, there is no mechanism that guarantees with full certainty that no one is able to eavesdrop.

To remedy this issue with private key sharing, public key cryptosystems were invented. In a public key cryptosystem, Alice makes the encryption key available to the public, so anyone can encrypt messages using the key but only Alice can decrypt the messages, and Bob can do the same. So, there is no need to secretly communicate to share keys prior to communicating in secret. Using such trapdoor function (also called one-way function ) is crucial for public key cryptosystems. The most famous public key cryptosytem is RSA (named after its inventors Ronald Rivest, Adi Shamir and Leonard Adleman) which was (officially) introduced in 1978 (unofficially, it was already invented years before they did by researchers secretly working in the Communications-Electronics Security Group at GCHQ, the British counterpart of NSA). RSA is based on the difficulty of factoring. Here is a basic idea of the textbook RSA cryptosystem.

Suppose that Alice wants to receive secret messages. She selects two large primes $p$ and $q$ and then forms the product $n=pq$. Alice also chooses an integer $E<n$ coprime to $\phi(n)=(p-1)(q-1)$. The integers $n$ and $E$ are made public and constitute the encryption key, so everybody can encrypt messages. We assume that our message is a sequence of positive integers $T<n$. Bob encypts each integer $T$ as $C\equiv T^E\mod n$, and send the ciphertext to Alice. Alice can decrypt the ciphertext as follows: Let $m=\phi(n)=(p-1)(q-1)$. Since $(E,m)=1$, there exists $D\in\mathbb{Z}/m\mathbb{Z}$ such that $DE\equiv 1\mod m$ or equivalently $DE=1$ in $\mathbb{Z}/m\mathbb{Z}$. Thus, $DE=\phi(n)k+1$ for some $k\in\mathbb{Z}$. The prime numbers $p$ and $q$ are supposedly huge, so $T$ being one of them is improbable and we can safely assume that $(T,n)=1$. Then by the Euler-Fermat theorem, we have $T^{\phi(n)}\equiv 1\mod n$. Finally, we see that the paintext $T$ is recovered by computing $C^D$ modulo $n$. \begin{align*} C^D&\equiv (T^E)^D\mod n\\ &\equiv T^{ED}\mod n\\ &\equiv T^{\phi(n)k+1}\mod n\\ &\equiv T\mod n \end{align*}
Now, assume that Celia is is eavesdropping. She knows the public key $(n,E)$. She also knows the ciphertext $C$. However, in order to decrypt $C$ she needs the decryption key $D$, the inverse of $E$ in $\mathbb{Z}/m\mathbb{Z}$ where $m=\phi(n)=(p-1)(q-1)$, and she needs to know the prime factors $p$ and $q$ of $n$ in order to compute $D$.

Example. Let $n=1073$, $p=29$, and $q=37$. The public key is $(n,E)=(1073,25)$. The plaintext $T$ is “MISS PIGGY” and the numerical equivalents are
$$13\ 9\ 19\ 19\ 27\ 16\ 9\ 7\ 7\ 25$$
Enciphering $T$: $C\equiv T^{25}\mod n=1073$
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
T & 13 & 9 & 19 & 19 & 27 & 16 & 9 & 7 & 7 & 25\\
\hline
C & 671 & 312 & 901 & 901 & 656 & 1011 & 312 & 922 & 922 & 546\\
\hline
\end{array}$$
Deciphering: Compute $D$, the inverse of 25 modulo $\phi(n)=(p-1)(q-1)=1008$. Since $1=25\cdot 121+1008(-3)$, $D=121$ is the decipering key and the paintext $T$ is retrieved by
$$C^{121}\equiv T\mod n=1073$$
For example, $671^{121}\equiv 13\mod 1073$.

Remark. In practical sense, there is a problem with the above example. If we encrypt the message letter for letter, the cryptosystem can be easily broken by frequency analysis. This problem can be remedied if we encrypt the message in blocks of about 100 letters. The chance that any two message blocks of 100 letters coincide is practically none.

Remark. Of course in practice we wouldn’t be using such small key sizes shown in the above example. Here is an example of practically usable keys: \begin{align*}E&=198778434778923476493186960677288219412181391439289859633481192496758260063\\n&=2555942223974189195272679217974555794863882765417656848825203904501780583533\\D&=1774134686349434385697798709945131299127046225553502224286279549365461014283\end{align*} Messages can be encypted more securely if one uses key sizes of about 200 digits in addition to using many-letter message blocks suggested in the above remark.

Remark. As mentioned earlier, the presumed security of RSA is based on the belief that factoring is a difficult problem to crack on a computer. So, how difficulty can it be? Umesh Vazirani, a computer scientist at UC Berkely, summed it up using the example of factoring a 2,000-digit number back in 1994: “It’s not just a case that all the computers in the world today would be unable to factor that number. Even if you imagine that every particle in the universe was a computer and was computing at full speed for the entire life of the universe, that would be insufficient to factor that number.”

Remark. RSA protocol begins with picking prime numbers to make the key. We know there are infinitely many prime numbers although we don’t know if that is still the case for a particular type of prime numbers. For example, it is an open problem in number theory if there are infinitely many Mersenne prime numbers, i.e. primes numbers of the form $2^n-1$. (The conjecture is there are infinitely many Mersenne prime numbers.) The largest prime number known to date is a Mersenne prime $2^{82589933}-1$. Especially from computational perspective, it would be interesting to see how prime numbers are distributed, and prime number theorem gives us a pretty good picture about how many prime numbers are there within a certain bound. Let $\pi(x)$ denotes the number of prime numbers less than or equal to $x$. $\pi(x)$ is called prime-counting function. Then Prime Number Theorem sates that $$\lim_{x\to\infty}\frac{\pi(x)}{\left[\frac{x}{\log(x)}\right]}=1$$ which can be restated as $$\pi(x)\sim\frac{x}{\log(x)}$$ for large $x$. This can be interpreted that for large $x$, the probability that a random integer not greater than $x$ is prime is very closed to $\frac{1}{\log(x)}$. This theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Pousin in 1896. For example, if one wants to know how many prime numbers there are between $\frac{x}{2}$ and $x$ for a given lager number $x$, we can get an estimate from prime number theorem: \begin{align*}\pi(x)-\pi\left(\frac{x}{2}\right)&\sim\frac{x}{\log(x)}-\frac{x}{2\log\left(\frac{x}{2}\right)}\\&\sim\frac{x}{\log(x)}-\frac{x}{2\log(x)}\ (\mbox{because $x$ is large})\\&=\frac{x}{2\log(x)}\end{align*} Figure 1 shows the comparison between the asymptotic distribution of prime number between $\frac{x}{2}$ and $x$ (in blue), and its approximation (in red).

For $x=100000$, using the approximation $\frac{x}{2\log(x)}$ there are 4343 estimated prime numbers between 50000 and 100000, so there are plentiful of them to choose from.

Suppose we have an $N$-letter alphabet and want to send digraphs as our message units. As we have seen here, we can let each digraph correspond to an integer considered modulo $N^2$, i.e. to an element of $\mathbb{Z}/N^2\mathbb{Z}$. An alternate possibility is to let each digraph correspond to a vector $\begin{pmatrix}
x\\
y
\end{pmatrix}$ with $x,y\in\mathbb{Z}/N\mathbb{Z}$. For example, if we are using the 26-letter alphabet A- Z with numerical equivalents 0-25, respectively, then the digraph NO corresponds to the vector $\begin{pmatrix}
13\\
14
\end{pmatrix}$. We consider the $xy$-plane as the finite lattice $\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}=(\mathbb{Z}/N\mathbb{Z})^2$.

Let $M_2(\mathbb{Z}/N\mathbb{Z})$ denote the set of all $2\times 2$ matrices with entries in $\mathbb{Z}/N\mathbb{Z}$. Let $A=\begin{pmatrix}
a & b\\
c & d \end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and suppose that $D=\det(A)=ad-bc\in(\mathbb{Z}/N\mathbb{Z})^*$. Let $D^{-1}$ denote the multiplicative inverse of $D$ in $\mathbb{Z}/N\mathbb{Z}$. Then \begin{align*}
\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}&=\begin{pmatrix}
D^{-1}(da-bc) & 0\\
0 & D^{-1}(-cb+ad)
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\end{align*}
Similarly,
$$\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}$$
Thus, we see that
\begin{equation}
\label{eq:invmat}
A^{-1}=\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}
\end{equation}

Example. Find the inverse of $A=\begin{pmatrix}
2 & 3\\
7 & 8
\end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$.

Solution. $D=16-21=-5\equiv 21\mod 26$. Since $(21,26)=1$, there exists $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$. Remember that finding $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$ is equivalent to solving the diophantine equation $21x+26y=1$.
\begin{align*} 26&=21\cdot 1+5\\ 21&=5\cdot 4+1 \end{align*}
and
\begin{align*} 1&=21-5\cdot 4\\ &=21-(26-21)4\\ &=5\cdot 21+26(-4) \end{align*}
Thus, we find $21^{-1}\equiv 5\mod 26$.
\begin{align*} A^{-1}&=\begin{pmatrix} 5\cdot 8 & -5\cdot 3\\ -5\cdot 7 & 5\cdot 2 \end{pmatrix}\\ &=\begin{pmatrix} 40 & -15\\ -35 & 10 \end{pmatrix}\\ &\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$. Then
$$\begin{pmatrix}
x’\\
y’
\end{pmatrix}=A\begin{pmatrix}
x\\
y
\end{pmatrix}=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix}
x\\
y
\end{pmatrix}=\begin{pmatrix}
ax+by\\
cx+dy
\end{pmatrix}$$
This gives a linear map or a linear transformation from vectors to vectors.

We introduce the following theorem without proof.

Theorem. Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and set $D=ad-bc$ as before. Then the following are equivalent:

1. $(D,N)=1$.
2. $A$ has an inverse matrix.
3. if $x$ and $y$ are not both $0$ in $\mathbb{Z}/N\mathbb{Z}$, then $A\begin{pmatrix}x\\y \end{pmatrix}\ne\begin{pmatrix}0\\0\end{pmatrix}$.
4. $A$ gives a one-to-one correspondence of $(\mathbb{Z}/N\mathbb{Z})^2$ with itself.

Example. Solve the following systems of simultaneous congruences.

1. \begin{align*}2x+3y&\equiv 1\mod 26\\ 7x+8y&\equiv 2\mod 26 \end{align*}
2. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 2\mod 26 \end{align*}
3. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 1\mod 26 \end{align*}

Solution.

1. The system of simultaneous congruences can be written as the matrix congruence $AX\equiv B\mod 26$ or as the matrix equation $AX=B$ in $\mathbb{Z}/26\mathbb{Z}$, where $$A=\begin{pmatrix}2 & 3\\7 & 8\end{pmatrix},\ X=\begin{pmatrix}x\\y\end{pmatrix},\ B=\begin{pmatrix}1\\2\end{pmatrix}$$ $D=16-21=-5$ and $(-5,26)=1$, so by above Theorem, we see that $A^{-1}$ exists. In fact, we have already found $A^{-1}$ in the previous example. The solution $X$ is given by \begin{align*} X&\equiv A^{-1}B\mod 26\\&\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 26\\ &\equiv\begin{pmatrix} 10\\ 11 \end{pmatrix}\mod 26 \end{align*}
2. The matrix in parts 2 and 3 does not have an inverse matrix in $\mathbb{Z}/26\mathbb{Z}$ because $D=9-21=-12$ and $(-12,26)=2\ne 1$. However, it does have an inverse matrix in $\mathbb{Z}/13\mathbb{Z}$ and the solution is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 13\\ &\equiv\begin{pmatrix} 3\\ 8 \end{pmatrix}\mod 13 \end{align*} We now examine the possibilities of having solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 3\mod 13$ and $y\equiv 8\mod 13$, $x$ and $y$ can be written as $x=3+13k_1$ and $y=8+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Suppose that $k_1+k_2$ is even, so that $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 15+13(k_1+k_2)\mod 26\\ &\equiv 15\mod 26\\ &\not\equiv 2\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are no solutions for part 2.
3. Similarly to part 2, the solution in $\mathbb{Z}/13\mathbb{Z}$ is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix}\mod 13\\ &\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 13 \end{align*} We test the possibilities of solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 6\mod 13$ and $y\equiv 7\mod 13$, $x$ and $y$ can be written as $x=6+13k_1$ and $y=7+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Now we assume that $k_1+k_2$ is even, so that we have $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are solutions for part 3. Let $0\leq x,y\leq 25$. Then $k_1, k_2=0,1$. Since $k_1+k_2$ is even, we have either $k_1=k_2=0$ or $k_1=k_2=1$. Therefore, the solutions are \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 26\\ &\mbox{or}\\ \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 19\\ 20 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}
\in M_2(\mathbb{Z}/N\mathbb{Z})$ with $(D,N)=1$ where $D=ad-bc$ be an enciphering matrix. Then it defines the enciphering transformation $C=AP$ where $P=\begin{pmatrix} x\\ y
\end{pmatrix}$ and $C=\begin{pmatrix}
x’\\
y’
\end{pmatrix}$ are plaintext message unit and ciphertext, respectively. That is,
$$\begin{pmatrix}
x’\\
y’
\end{pmatrix}=\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}\begin{pmatrix} x\\ y
\end{pmatrix}$$
The deciphering transformation is then given by $P=A^{-1}C$, i.e.
$$\begin{pmatrix} x\\ y
\end{pmatrix}=\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}\begin{pmatrix} x’\\ y’
\end{pmatrix}$$

Example. Wokring in the 26-letter alphabet, use the matrix $A=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$ to encipher the message unit “NO”. $$AP=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13\\ 14 \end{pmatrix}=\begin{pmatrix} 68\\ 103 \end{pmatrix}\equiv\begin{pmatrix} 16\\ 21 \end{pmatrix}\mod 26 $$ Thus the ciphertext $C=AP$ is “QV”.

Remark. To encipher a plaintext sequence of $k$ digraphs $P=P_1P_1P_3\cdots P_k$, we can write the $k$ vectors as columns of a $2\times k$ matrix and then multiply $A$ by the $2\times k$ matrix $P$ to get a $2\times k$ matrix $C=AP$ of coded digraph vectors.

Example. Encipher “NOANSWER”.

Solution. The numerical equivalence of “NOANSWER” is $$\begin{pmatrix} 13\\ 14 \end{pmatrix}\begin{pmatrix} 0\\ 13 \end{pmatrix}\begin{pmatrix} 18\\ 22 \end{pmatrix}\begin{pmatrix} 4\\ 17 \end{pmatrix}$$ \begin{align*} C&=AP\\ &=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13 & 0 & 18 & 4\\ 14 & 13 & 22 & 17 \end{pmatrix}\\ &=\begin{pmatrix} 68 & 39 & 102 & 59\\ 203 & 104 & 302 & 164 \end{pmatrix}\\ &\equiv\begin{pmatrix} 16 & 13 & 24 & 7\\ 21 & 0 & 16 & 8 \end{pmatrix}\mod 26 \end{align*} i.e. the coded message is “QVNAYQHI”.

Example. In the situation of previous example, decipher the ciphertext “FWMDIQ”.

Solution.
\begin{align*} P&=A^{-1}C\\ &=\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 5 & 12 & 8\\ 22 & 3 & 16 \end{pmatrix}\\ &=\begin{pmatrix} 312 & 201 & 288\\ 305 & 234 & 296 \end{pmatrix}\\ &\equiv\begin{pmatrix} 0 & 19 & 2\\ 19 & 0 & 10 \end{pmatrix}\mod 26 \end{align*}
Hence, the deciphered plaintext is “ATTACK”.

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:

1. 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.
2. 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*}