## Section6.3Hill Cipher

Our second block cipher is the Hill cipher. This is a cipher which can operate on blocks of $n$ for any $n$ by using a $n \times n$ matrix. We will stay with blocks of size two for our examples. Of course, blocks of larger size would be more secure. (This cipher was suggested in a 1929 article by Lester Hill.)

Let's consider the plaintext message: NEARLY DONE. Again, we'll break it into blocks of two letters. It is possible to encrypt double letters with this system, so we don't need to separate them. But we still need to add an X if the last block only has one letter. NE AR LY DO NE. In order to use matrices, we need to convert the letters to numbers so we will use our usual conversion. $NE=[13,4], \;\;AR=[ 0,17], \;\;LY=[ 11,24], \;\;DO=[ 3,14], \;\; NE=[13,4]$

Then the encryption formula for a Hill cipher using a $2 \times 2$ matrix is

\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) \equiv \left( \begin{matrix} a \amp b \\ c \amp d \end{matrix} \right) \left( \begin{matrix} PT_1\\ PT_2 \end{matrix} \right) \pmod{26} \end{equation*}

We begin with an illuminating example. Let $\left( \begin{matrix} a \amp b \\ c \amp d \end{matrix} \right) = \left( \begin{matrix} 3 \amp 1 \\ 4 \amp 2 \end{matrix} \right) \text{.}$ We will examine what happens when we encrypt the above plaintext message with this matrix.

Applying the encryption formula to the first two letters, $[PT_1,PT_2]=[N,E]=[13,4]$ gives

\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) = \left( \begin{matrix} 3 \amp 1\\ 4 \amp 2 \end{matrix} \right) \left( \begin{matrix} 13\\4 \end{matrix} \right) = \left( \begin{matrix} 39+4\\ 52+8 \end{matrix} \right)= \left( \begin{matrix} 17\\ 8 \end{matrix} \right)\pmod{26}= \left( \begin{matrix} R\\ I \end{matrix} \right) \end{equation*}

Applying our formula to the second block of two letters, $PT_1,PT_2=A,R=0,17\text{,}$ gives

\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) = \left( \begin{matrix} 3 \amp 1\\ 4 \amp 2 \end{matrix} \right) \left( \begin{matrix} 0\\17 \end{matrix} \right) = \left( \begin{matrix} 17\\ 34 \end{matrix} \right)= \left( \begin{matrix} 17\\ 8 \end{matrix} \right)\pmod{26}= \left( \begin{matrix} R\\ I \end{matrix} \right) \end{equation*}

Yikes! this is a big problem, we won't be able to decrypt this!.

What went wrong? What conditions do we need to impose on our matrices to make decryption possible? Suppose we want to use our encryption formula to solve for a decryption formula. To solve

\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) \equiv \left( \begin{matrix} a \amp b \\ c \amp d \end{matrix} \right) \left( \begin{matrix} PT_1\\ PT_2 \end{matrix} \right) \pmod{26} \end{equation*}

for PT we need to reverse the matrix multiplication. We can do this using an inverse matrix. That is we want

\begin{equation*} \left( \begin{matrix} PT_1\\ PT_2 \end{matrix} \right) = \left( \begin{matrix} a \amp b\\ c \amp d \end{matrix} \right)^{-1} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) \pmod{26} \end{equation*}

Recall the inverse of a $2 \times 2$ matrix

\begin{equation*} \left( \begin{matrix} a \amp b \\ c \amp d \end{matrix} \right)^{-1} = \frac{1}{ad-bc}\left( \begin{matrix} d \amp -b \\ -c \amp a \end{matrix} \right) \end{equation*}

where $ad-bc$ is the determinant of the matrix. But we are working mod 26 so fractions make no sense. We can fix that by using the multiplicative inverse, but remember not everything has a multiplicative inverse mod 26. That is, we want

\begin{equation*} \left( \begin{matrix} a \amp b \\ c \amp d \end{matrix} \right)^{-1} \equiv ({ad-bc})^{-1}\left( \begin{matrix} d \amp -b \\ -c \amp a \end{matrix} \right) \pmod{26} \end{equation*}

Thus, in order for decryption to work, we need the determinant of the matrix to be relatively prime to 26. What was the determinant in our bad example?

\begin{equation*} \det \left( \begin{matrix} 3 \amp 1\\ 4 \amp 2 \end{matrix} \right) = (6-4) =2 \end{equation*}

So we can now see that this matrix did not work for the Hill cipher since the determinant is 2 which does not have a multiplicative inverse mod 26.

###### Definition6.3.1.

Let $A$ be an $n \times n$ matrix that is invertible mod 26. The Hill cipher encryption technique groups the plaintext into blocks of $n$ letters and encrypts a message by

\begin{equation*} \left( \begin{matrix} CT_1\\ \vdots \\ CT_n \end{matrix} \right) \equiv \left( A \right) \left( \begin{matrix} PT_1\\ \vdots \\ PT_n \end{matrix} \right) \pmod{26} \end{equation*}

We will now pick a better matrix to encrypt our plaintext message with. Let $A=\left( \begin{matrix} 11 \amp 2\\ 4 \amp 1 \end{matrix} \right)\text{.}$ Let's check to make sure its decryptable first.

\begin{equation*} \left( \begin{matrix} 11 \amp 2\\ 4 \amp 1 \end{matrix} \right)^{-1} = ({3})^{-1}\left( \begin{matrix} 1 \amp -2 \\ -4 \amp 11 \end{matrix} \right)\equiv 9\left( \begin{matrix} 1 \amp -2 \\ -4 \amp 11 \end{matrix} \right) \equiv \left( \begin{matrix} 9 \amp -18 \\ -36 \amp 99 \end{matrix} \right) \equiv \left( \begin{matrix} 9 \amp 8 \\ 16 \amp 21 \end{matrix} \right) \pmod{26} \end{equation*}

That works, so we can encrypt with this matrix.

\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) = \left( \begin{matrix} 11 \amp 2\\ 4 \amp 1 \end{matrix} \right) \left( \begin{matrix} 13\\ 4 \end{matrix} \right) = \left( \begin{matrix} 21\\ 4 \end{matrix} \right)\pmod{26}= \left( \begin{matrix} V\\ E \end{matrix} \right) \end{equation*}
\begin{equation*} \left( \begin{matrix} CT_1\\ CT_2 \end{matrix} \right) = \left( \begin{matrix} 11 \amp 2\\ 4 \amp 1 \end{matrix} \right) \left( \begin{matrix} 0\\ 17 \end{matrix} \right) = \left( \begin{matrix} 8\\ 17 \end{matrix} \right)\pmod{26}= \left( \begin{matrix} I\\ R \end{matrix} \right) \end{equation*}

The rest of the encryption can be performed with the help of Sage.