Cryptology by Discovery: An Introduction to Conjecture and Proof

Section 6.3 Hill 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

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

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

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

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

Recall the inverse of a \(2 \times 2\) matrix

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

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?

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.

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.

That works, so we can encrypt with this matrix.

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