| | |
Each possible pair of letters can be associated with a two-dimensional vector made from integers$\pmod{26}$ in the usual way (A=0, B=1, C=2, ..., Z=25). For example, the pair "NU" would be associated with the vector $\begin{pmatrix}13\\20\end{pmatrix}$.
To encrypt the letter block "NU", we apply an invertible linear transformation$\pmod{26}$ to the corresponding vector, and then interpret the result as another letter block.
So, for example, suppose the invertible linear transformation in question was
$$T = \begin{bmatrix} 5 & 11\\1 & 22\end{bmatrix}$$
Then to encode "NU" we would do the following
$$T(\textrm{"NU"}) = \begin{bmatrix} 5 & 11\\1 & 22\end{bmatrix} \begin{pmatrix}13\\20\end{pmatrix} = \begin{pmatrix}285\\453\end{pmatrix} \equiv \begin{pmatrix}25\\11\end{pmatrix} \pmod{26}$$
Lastly, we interpret the vector $\begin{pmatrix}25\\11\end{pmatrix}$ as the letter block "ZL".
Thus, "NU" gets encrypted as "ZL".
To encrypt a long message like: $$\textrm{"NUMBERTHEORYROCKSX"}$$ we simply break the message up into 2-letter blocks $$\textrm{"NU MB ER TH EO RY RO CK SX"}$$ and run each pair of letters through the matrix $T$. We have already seen what happens to "NU" given the linear transformation $T$ above. If we applied $T$ to the rest of the letter blocks above, we would produce the encrypted message:
$$\textrm{"ZL TI ZO QR SA LZ FN QO FE"}$$
Now, how might we break a Hill cipher of this sort described above?
It turns out, if we can make a good guess as to how just two of the letter blocks should be decrypted, we can deduce the matrix that will decrypt the entire message. Consider the following...
Suppose we started with the encrypted message seen above,
$$\textrm{"ZL TI ZO QR SA LZ FN QO FE"}$$
not knowing its complete decrypted form. However, suppose we did have a suspicion that the first word should be "NUMBER". This means that when we apply the inverse matrix for the linear transformation used to encipher our message to "ZL" and "TI", the results should be "NU" and "MB", respectively.
So let's try to find this (decrypting) matrix -- suppose, we denote it by $D$. If,
$$D=\begin{bmatrix}a & b\\c & d\end{bmatrix}$$
then knowing that "ZL" $\rightarrow$ "NU" and "TI" $\rightarrow$ "MB", we have
$$\begin{bmatrix}a & b\\c & d\end{bmatrix} \begin{pmatrix}25\\11\end{pmatrix} \equiv \begin{pmatrix}13\\20\end{pmatrix}$$
and
$$\begin{bmatrix}a & b\\c & d\end{bmatrix} \begin{pmatrix}19\\8\end{pmatrix} \equiv \begin{pmatrix}12\\1\end{pmatrix}$$
Evaluating the expressions on the left, we discover that
$$\begin{align*}
25a+11b &\equiv 13 \pmod{26}\\
25c+11d &\equiv 20 \pmod{26}\\
19a+8b &\equiv 12 \pmod{26}\\
19c+8d &\equiv 1 \pmod{26}
\end{align*}$$
Getting the congruences involving the same variables together, we have
$$\begin{align*}
25a+11b &\equiv 13 \pmod{26}\\
19a+8b &\equiv 12 \pmod{26}
\end{align*}
$$
$$
\begin{align*}
25c+11d &\equiv 20 \pmod{26}\\
19c+8d &\equiv 1 \pmod{26}
\end{align*}$$
Now, notice (and this is a nice trick) that we can write the two systems of congruences as matrix congruences. That is to say,
$$\begin{bmatrix}25 & 11\\19 & 8\end{bmatrix} \begin{pmatrix}a\\b\end{pmatrix} \equiv \begin{pmatrix}13\\12\end{pmatrix} \textrm{ and }
\begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}\begin{pmatrix}c\\d\end{pmatrix}\equiv\begin{pmatrix}20\\1\end{pmatrix} \pmod{26}$$
Both of these can be solved by applying the inverse of the matrix involved to both sides of the congruence...
$$\begin{pmatrix}a\\b\end{pmatrix} \equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}13\\12\end{pmatrix} \textrm{ and }
\begin{pmatrix}c\\d\end{pmatrix} \equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}20\\1\end{pmatrix} \pmod{26}$$
We just need to find the inverse matrix in question.
As seen previously, we can find the inverse of a matrix with the formula
$$M^{-1} = \begin{bmatrix}x & y\\z & w\end{bmatrix}^{-1} = \textrm{det}^{-1}\begin{bmatrix}w & -y\\-z & x\end{bmatrix}$$
Finding the determinant$\pmod{26}$ is easy enough,
$$\textrm{det}=25 \cdot 8 - 19 \cdot 11 = -9 \equiv 17 \pmod{26}$$
but to find $\textrm{det}^{-1}$, since we are working with congruences instead of equations, we need to find the multiplicative inverse of 17$\pmod{26}$. Recall that the product of any number and its multiplicative inverse must be the multiplicative identity, 1, so we need to solve
$$17m \equiv 1 \pmod{26}$$
This in turn, leads to solving (in integers) the equation,
$$17m + 26n = 1$$
To do this, we apply the Euclidean Algorithm:
$$\begin{align*}
26 &= 1 \cdot 17 + 9\\
17 &= 1 \cdot 9 + 8\\
9 &= 1 \cdot 8 + \boxed{1} \leftarrow \textrm{gcd}\\
8 &= 8 \cdot 1 + 0
\end{align*}$$
Now, we can use these calculations to write the greatest common divisor, 1, as a linear combination of 17 and 26...
$$\begin{align*}
1 &= 9 - 1 \cdot 8\\
&= 9 - 1 \cdot (17 - 1 \cdot 9)\\
&= 2 \cdot 9 - 1 \cdot 17\\
&= 2 \cdot (26 - 1 \cdot 17) - 1 \cdot 17\\
&= 2 \cdot 26 - 3\cdot 17
\end{align*}$$
Which reveals the value of $m$ and hence, the multiplicative inverse of the determinant:
$$\textrm{det}^{-1} = m = -3 \equiv 23 \pmod{26}$$
Returning to finding the inverse matrix desired, we have
$$\begin{align*}
\begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} &= \textrm{det}^{-1} \begin{bmatrix}8 & -11\\-19 & 25\end{bmatrix}\\
&\equiv 23 \begin{bmatrix}8 & -11\\-19 & 25\end{bmatrix} \\
&\equiv \begin{bmatrix}184 & -253\\-437& 575\end{bmatrix} \\
&\equiv \begin{bmatrix}2 & 7\\5 & 3\end{bmatrix} \pmod{26}
\end{align*}$$
Finally, recalling that
$$\begin{align*}
\begin{pmatrix}a\\b\end{pmatrix} &\equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}13\\12\end{pmatrix} \pmod{26} \quad \textrm{, and }\\
\begin{pmatrix}c\\d\end{pmatrix} &\equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}20\\1\end{pmatrix} \pmod{26}
\end{align*}$$
we can solve for $a$, $b$, $c$, and $d$:
$$\begin{align*}
\begin{pmatrix}a\\b\end{pmatrix} &\equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}13\\12\end{pmatrix}\\
&\equiv \begin{bmatrix}2 & 7\\5 & 3\end{bmatrix} \begin{pmatrix}13\\12\end{pmatrix} \\
&\equiv \begin{pmatrix}2 \cdot 13 + 7 \cdot 12\\5 \cdot 13 + 3 \cdot 12\end{pmatrix} \\
&\equiv \begin{pmatrix}110\\101\end{pmatrix} \\
&\equiv \begin{pmatrix}6\\23\end{pmatrix}
\end{align*}$$
So $a=6$ and $b=23$.
In a similar manner, we can solve for $c$ and $d$...
$$\begin{align*}
\begin{pmatrix}c\\d\end{pmatrix} &\equiv \begin{bmatrix}25 & 11\\19 & 8\end{bmatrix}^{-1} \begin{pmatrix}20\\1\end{pmatrix}\\
&\equiv \begin{bmatrix}2 & 7\\5 & 3\end{bmatrix} \begin{pmatrix}20\\1\end{pmatrix} \\
&\equiv \begin{pmatrix}2 \cdot 20 + 7 \cdot 1\\5 \cdot 20 + 3 \cdot 1\end{pmatrix} \\
&\equiv \begin{pmatrix}47\\103\end{pmatrix} \\
&\equiv \begin{pmatrix}21\\25\end{pmatrix}
\end{align*}$$
So $c=21$ and $d=25$.
Now we have our (decrypting) matrix!
$$D = \begin{bmatrix}a & b\\c & d\end{bmatrix} = \begin{bmatrix}6 & 23\\21 & 25\end{bmatrix}$$
Decrypting the rest of the message is now easy! We simply convert the letter blocks to vectors and apply $D$ to them, and out pops the vectors corresponding to the decrypted letter blocks!
So, for example, consider the third letter block "ZO", which we suspect should decrypt to "ER". Does it?
$$\begin{align*}
D(\textrm{"ZO"}) &= \begin{bmatrix}6 & 23\\21 & 25\end{bmatrix} \begin{pmatrix}25\\14\end{pmatrix} \\
&= \begin{pmatrix}6 \cdot 25 + 23 \cdot 14\\21 \cdot 25 + 25 \cdot 14\end{pmatrix} \\
&= \begin{pmatrix}472\\875\end{pmatrix} \\
&\equiv \begin{pmatrix}4\\17\end{pmatrix} \pmod{26}
\end{align*}$$
which, is the letter block "ER"! Looks like our guess about the word "NUMBER" was right!