  ## Exercises - The Hill Cipher

1. Suppose $M_1$ and $M_2$ are linear transformations which operate on blocks of two letters, as represented by two integers chosen in the usual way (A=0, B=1, ..., Z=25), and treated as a vector. It is known that $M_1(\unicode{x201C}\textrm{BA"})=\unicode{x201C}\textrm{TR"}$, $M_1(\unicode{x201C}\textrm{AB"})=\unicode{x201C}\textrm{IL"}$, $M_2(\unicode{x201C}\textrm{BA"})=\unicode{x201C}\textrm{BI"}$, and $M_2(\unicode{x201C}\textrm{AB"})=\unicode{x201C}\textrm{LL"}$.

1. Noting that $T=19$, $R=17$, $I=8$, and $L=11$, we have

$$M_1= \begin{bmatrix} 19 & 8\\ 17 & 11 \end{bmatrix}$$

In a similar way, noting that $B=1$, $I=8$, and $L=11$, we have

$$M_2= \begin{bmatrix} 1 & 11\\ 8 & 11 \end{bmatrix}$$

2. Consider the first block of two letters in our message, "NU". Translating this into a vector, we have $\begin{pmatrix}13\\20\end{pmatrix}$ Then, applying the linear transformation $M_2$, by "multiplying" by its matrix form, we get

$$\begin{bmatrix}1 & 11\\8 & 11\end{bmatrix} \begin{pmatrix}13\\20\end{pmatrix} = \begin{pmatrix}1 \cdot 13 + 11 \cdot 20\\ 8 \cdot 13 + 11 \cdot 20\end{pmatrix} = \begin{pmatrix}233\\324\end{pmatrix}$$

Now, reducing this vector$\pmod{26}$, so that we can interpret it as a pair of letters, we have

$$\begin{pmatrix}233\\324\end{pmatrix} \equiv \begin{pmatrix}25\\12\end{pmatrix} \pmod{26}$$

This in turn yields the encrypted block of letters "ZM".

Doing this for each block of two letters in our message, and then putting the encrypted blocks together in the same order, yields the ciphertext: "ZMXDJLSVCEVKPEIWLH"

3. Recall, the composition of linear transformations can be found by "multiplying" their matrix forms: \begin{align} M_1 \circ M_2 &= \begin{bmatrix}19 & 8\\17 & 11\end{bmatrix} \cdot \begin{bmatrix}1 & 11\\8 & 11\end{bmatrix}\\ &= \begin{bmatrix}19 \cdot 1 + 8 \cdot 8 & 19 \cdot 11 + 8 \cdot 11\\ 17 \cdot 1 + 11 \cdot 8 & 17 \cdot 11 + 11 \cdot 11 \end{bmatrix}\\ &= \begin{bmatrix}83 & 297\\105 & 208\end{bmatrix} \\ &\equiv \begin{bmatrix}5 & 11\\1 & 22\end{bmatrix} \pmod{26} \end{align}

4. Proceeding in a way very similar to part (a), we can see the first block of two letters, "NU", gets turned into $$\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}$$

Note, this yields the same encrypted block of two letters, "ZL", arrived at by first encrypting "NU" by $M_2$ and then by $M_1$. The rest of the blocks of letters behave in a similar manner, when the composition is applied to them. So our final encrypted message is the same as before: "ZLTIZOQRSALZFNQOFE"

5. Noting that the determinant of the composition is

$$\begin{vmatrix}5 & 11\\1 & 22\end{vmatrix} = 5 \cdot 22 - 1 \cdot 11 = 99 \equiv 21 \pmod{26}$$

we will need to first find the multiplicative inverse of 21$\pmod{26}$. Of course, if $x$ is the multiplicative inverse of 21$\pmod{26}$, then

$$21x \equiv 1 \pmod{26}$$

Solving this linear congruence in the usual way, we find $x \equiv 5 \pmod{26}$. So, the matrix form of the inverse of the composition$\pmod{26}$ is given by:

$$\begin{bmatrix}5 & 11\\1 & 22\end{bmatrix}^{-1} = 5\begin{bmatrix}22 & -11\\-1 & 5\end{bmatrix} = \begin{bmatrix}110 & -55\\-5 & 25\end{bmatrix} \equiv \begin{bmatrix}6 & 23\\21 & 25\end{bmatrix}$$

Now, applying this inverse matrix to the first two-letter block,"ZL", of our encrypted message, we arrive at

$$\begin{bmatrix}6 & 23\\21 & 25\end{bmatrix} \begin{pmatrix}25\\11\end{pmatrix} = \begin{pmatrix}403\\800\end{pmatrix} \equiv \begin{pmatrix}13\\20\end{pmatrix}$$

which gets interpreted as the letters "NU". Note these are the first two letters of our original message. Applying the inverse matrix to the rest of the two-letter blocks yields similar results. Taken all together, our original message, "NUMBERTHEORYROCKSX" is revealed.