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. Find the matrix forms for both $M_1$ and $M_2$  

      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. Use the matrix form of $M_2 \pmod{26}$ to encrypt the message "NUMBERTHEORYROCKSX"  

      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. Now use the matrix form of $M_1 \pmod{26}$ to encrypt your answer to (b) (so that the original message has gone through two stages of encryption).  

      "ZLTIZOQRSALZFNQOFE"

    4. Find the matrix form for the composition $M_1$ and $M_2$, $\pmod{26}$  

      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 & 308\end{bmatrix} \\ &\equiv \begin{bmatrix}5 & 11\\1 & 22\end{bmatrix} \pmod{26} \end{align}$$

    5. Use the composition found in (d) to encrypt the message "NUMBERTHEORYROCKSX". Compare your answer with the answer to part (c).  

      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"

    6. Find the matrix form for the inverse$\pmod{26}$ of the composition found in (d), and show that when it is applied to the answer to (c), the original message "NUMBERTHEORYROCKSX" is revealed. Does encrypting a message twice with this type of encryption make things more difficult for the person trying to break the code?  

      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.