Skip to main content

Section 6.3 Hill's Cipher

Subsection 6.3.1 Matrices

Definition 6.3.1. Matrix.

A matrix is a rectangular array of numbers such as

\begin{align*} \begin{pmatrix}0 & 1 & 2 \\ 3 & 4 & 5\end{pmatrix} \end{align*}

which, in this setting, we will use to represent a transformation for enciphering and deciphering.

The cipher we will look at in this section, Hill's Cipher will work much like an affine cipher but will use matrices for the multiplier and shift and not just numbers. All the matrices we will use will be either square like this

\begin{align*} \begin{pmatrix}1 & 7 \\ 0 & 5\end{pmatrix} \end{align*}

so that it has the same number of rows and columns or will be a special type of matrix called a vector which has only one column like this

\begin{gather*} \begin{pmatrix} 18 \\ 7 \end{pmatrix}. \end{gather*}

Finally, all operations will be done using arithmetic modulo 26.

We can add and multiply matrices with one another or with vectors as long as the dimensions match.

Two \(2\times 2\) square matrices can be added like so

\begin{align*} \begin{pmatrix}23 & 3 \\ 0 & 15 \end{pmatrix} + \begin{pmatrix}9 & 2 \\ 5 & 19 \end{pmatrix} = \begin{pmatrix}23+9 & 3+2 \\ 0+5 & 15+19\end{pmatrix} \end{align*}

where the corresponding entries are added together. Then completing the addition and reducing modulo 26 we get

\begin{align*} \begin{pmatrix}32 & 5 \\ 5 & 34\end{pmatrix} \equiv \begin{pmatrix}6 & 5 \\ 5 & 8\end{pmatrix} \pmod{26}. \end{align*}

Likewise we can add two vectors

\begin{gather*} \begin{pmatrix}17 \\ 12 \end{pmatrix} + \begin{pmatrix}14 \\ 8 \end{pmatrix} \equiv \begin{pmatrix}5 \\ 20\end{pmatrix} \pmod{26}. \end{gather*}

But, we cannot add a matrix to a vector since they are not the same size.

In order to multiply a matrix with a vector or a matrix with another matrix we need to multiply rows by columns like so

\begin{align*} \begin{pmatrix}8 & 1 \\ 5 & 3 \end{pmatrix} \cdot \begin{pmatrix}1 \\ 10 \end{pmatrix} = \begin{pmatrix}8\cdot 1+1\cdot 10 \\ 5\cdot 1 + 3\cdot 10\end{pmatrix}. \end{align*}

Breaking that down a little more, the first entry on top is

\begin{align*} \begin{pmatrix}8 & 1 \end{pmatrix} \cdot \begin{pmatrix}1 \\ 10 \end{pmatrix} = \begin{pmatrix}8\cdot 1+1\cdot 10 \end{pmatrix} \end{align*}

and the second entry on bottom is

\begin{align*} \begin{pmatrix}5 & 3 \end{pmatrix} \cdot \begin{pmatrix}1 \\ 10 \end{pmatrix} = \begin{pmatrix}5\cdot 1 + 3\cdot 10\end{pmatrix}. \end{align*}

When we simplify the result modulo 26 we get

\begin{gather*} \begin{pmatrix}8\cdot 1+1\cdot 10 \\ 5\cdot 1 + 3\cdot 10\end{pmatrix}\equiv \begin{pmatrix}18 \\ 9 \end{pmatrix}\pmod{26}. \end{gather*}

Similarly we can multiply two matrices together

\begin{align*} \begin{pmatrix}3 & 8 \\ 5 & 15 \end{pmatrix} \cdot \begin{pmatrix}1 & 7\\ 13 & 16 \end{pmatrix} &= \begin{pmatrix}3\cdot 1+8\cdot 13 & 3\cdot 7 + 8\cdot 16 \\ 5\cdot 1+15\cdot 13 & 5\cdot 7 + 15\cdot 16\end{pmatrix} \\ &\equiv \begin{pmatrix}3 & 19 \\ 18 & 15\end{pmatrix} \pmod{26}. \end{align*}

Before moving on to see how Hill used these ideas to create a cipher, practice your arithmetic with matrices and vectors, you will want to use Figure C.0.14 so that the multiplication is not so tedious.

Carry out the arithmetic operations and simplify the results modulo 26.

\begin{gather*} \begin{pmatrix}17 \\ 5 \end{pmatrix} + \begin{pmatrix}13 \\ 9 \end{pmatrix} \end{gather*}
Answer
\begin{gather*} \begin{pmatrix}4\\14\end{pmatrix} \pmod{26} \end{gather*}

Carry out the arithmetic operations and simplify the results modulo 26.

\begin{align*} \begin{pmatrix}3 & 11 \\ 17 & 5 \end{pmatrix} + \begin{pmatrix}9 & 25 \\ 1 & 4 \end{pmatrix} \end{align*}
Answer
\begin{align*} \begin{pmatrix}12 & 10 \\ 18 & 9 \end{pmatrix} \pmod{26} \end{align*}

Carry out the arithmetic operations and simplify the results modulo 26.

\begin{align*} \begin{pmatrix}4 & 19 \\ 15 & 22 \end{pmatrix} \cdot \begin{pmatrix}19 \\ 4 \end{pmatrix} \end{align*}
Answer
\begin{gather*} \begin{pmatrix}22\\9\end{pmatrix} \pmod{26} \end{gather*}

Carry out the arithmetic operations and simplify the results modulo 26.

\begin{align*} \begin{pmatrix}21 & 17 \\ 0 & 11 \end{pmatrix} \cdot \begin{pmatrix}14 \\ 5 \end{pmatrix} \end{align*}
Answer
\begin{gather*} \begin{pmatrix}15\\3\end{pmatrix} \pmod{26} \end{gather*}

Carry out the arithmetic operations and simplify the results modulo 26.

\begin{align*} \begin{pmatrix}16 & 3 \\ 7 & 1 \end{pmatrix} \cdot \begin{pmatrix}4 \\ 17 \end{pmatrix} + \begin{pmatrix}2 \\ 7 \end{pmatrix} \end{align*}
Hint

Order of operations is the same for matrices and vectors as it is for numbers, so first multiply and then add.

Answer
\begin{gather*} \begin{pmatrix}13\\0\end{pmatrix} \pmod{26} \end{gather*}

Subsection 6.3.2 Hill's Cipher

Subsubsection 6.3.2.1 Enciphering with Matrices

Let's see how we can encipher hill cipher using a key matrix

\begin{align*} m=\begin{pmatrix}7 & 12\\ 3 & 3 \end{pmatrix}. \end{align*}

Since it is a \(2\times 2\) matrix we will first break the message into groups of two letters

(hi) (ll) (ci) (ph) (er)

then to encipher each block we will convert each of these to a vector using \(a=0,\, b=1,\, c=2,\, \ldots\, etc. \) and multiply it by the matrix \(m\text{.}\) That is (hi) becomes

\begin{align*} m\begin{pmatrix}h\\ i\end{pmatrix}&= \begin{pmatrix}7 & 12\\ 3 & 3 \end{pmatrix}\begin{pmatrix}7\\8\end{pmatrix}\\ &\equiv \begin{pmatrix}15\\19\end{pmatrix} \pmod{26}\\ &\equiv \begin{pmatrix}P\\ T\end{pmatrix}. \end{align*}

Similarly we can encipher the (ll):

\begin{align*} m\begin{pmatrix}l\\ l\end{pmatrix}&= \begin{pmatrix}7 & 12\\ 3 & 3 \end{pmatrix}\begin{pmatrix}11\\ 11\end{pmatrix}\\ &\equiv \begin{pmatrix}1 \\ 14\end{pmatrix} \pmod{26}\\ &\equiv \begin{pmatrix}B\\ O\end{pmatrix}. \end{align*}

And for (ci) we get:

\begin{align*} m\begin{pmatrix}c\\ i\end{pmatrix}&= \begin{pmatrix}7 & 12\\ 3 & 3 \end{pmatrix}\begin{pmatrix}2\\ 8\end{pmatrix}\\ &\equiv \begin{pmatrix}6 \\ 4\end{pmatrix} \pmod{26}\\ &\equiv \begin{pmatrix}G\\ E\end{pmatrix}. \end{align*}

Finish enciphering hill cipher by enciphering the (ph) and the (er) just as we enciphered the other bi-grams.

Hint
  1. Change each pair of letters into a pair of numbers, this is a vector.
  2. Multiply the vector by the matrix \(m\text{.}\)
  3. Reduce the result modulo 26 and change back to letters, this is your cipher text.
Answer

(ph)\(\equiv\)HO and (er)\(\equiv\)YL

Try to encipher the message linear madness using the matrix

\begin{align*} m=\begin{pmatrix}15 & 0 \\ 17 & 7\end{pmatrix}, \end{align*}

note that since the message has odd length you will need to tack on an extra null letter, like a z.

Hint
  1. Change each pair of consecutive letters into a pair of numbers, this is a vector.
  2. Multiply the vector by the matrix \(m\text{.}\)
  3. Reduce the result modulo 26 and change back to letters, this is your cipher text.
Answer

Your enciphered message should be something like JJNPA PYWTM IMKN.

For a variation to Hill's Cipher you can both multiply by a matrix and add a shift, this make Hill's behave very much like an affine cipher. Try to encipher the word shifty by first multiplying by the matrix

\begin{align*} m=\begin{pmatrix}23 & 14 \\ 7 & 9\end{pmatrix}, \end{align*}

and then adding the vector

\begin{gather*} s=\begin{pmatrix}10 \\ 3\end{pmatrix}. \end{gather*}
Answer

CKEADO

Subsubsection 6.3.2.2 Matrix Inverses and Deciphering

We will be able to decipher messages which used Hill's cipher in exactly the same way we enciphered them once we can find inverse matrices.

Definition 6.3.10. Inverse Matrix.

Given a matrix \(m\) the inverse matrix \(m^{-1}\) is the unique matrix such that

\begin{gather*} m\cdot m^{-1}=m^{-1}\cdot m = I \end{gather*}

where \(I\) is the identity matrix (i.e. \(I\cdot m= m\cdot I = m\) for all matrices \(m\)).

Consider the matrix

\begin{align*} m=\begin{pmatrix}8 & 1 \\ 5 & 3\end{pmatrix}, \end{align*}

the inverse for this will be

\begin{align*} m^{-1}=\begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix}, \end{align*}

and if we multiply them together we get

\begin{align*} m\cdot m^{-1} = \begin{pmatrix}8 & 1 \\ 5 & 3\end{pmatrix} \cdot \begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix} &=\begin{pmatrix}8\cdot 7 + 1\cdot 23 & 8\cdot 15 + 1\cdot 10 \\ 5\cdot 7 + 3\cdot 23 & 5\cdot 15 + 3\cdot 10\end{pmatrix}\\ &\equiv \begin{pmatrix}4 + 23 & 16 + 10 \\ 9 + 17 & 23 + 4\end{pmatrix} &\pmod{26}\\ &\equiv \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix} &\pmod{26} \end{align*}

which is the identity matrix since

\begin{align*} \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}\cdot \begin{pmatrix}a & b \\ c & d\end{pmatrix} = \begin{pmatrix}a & b \\ c & d\end{pmatrix} \end{align*}

for any values of \(a,\, b,\, c,\) and \(d\text{.}\) The matrix inverses and the identity matrix work just like the multiplicative inverses and multiplicative identities we discussed when we learned about affine ciphers and modular arithmetic; just as in that case, not all matrices will have a multiplicative inverse.

Definition 6.3.11. Determinant.

The determinant of a \(2\times 2\) matrix

\begin{align*} m=\begin{pmatrix}a & b \\ c & d\end{pmatrix} \end{align*}

is equal to

\begin{gather*} det(m)=ad-bc. \end{gather*}

The matrix \(m\) will have a multiplicative inverse \(m^{-1}\) if and only if \(det(m)\) has a multiplicative inverse, in which case we get

\begin{align*} m^{-1}=(det(m))^{-1}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}. \end{align*}

Going back to our previous example of

\begin{align*} m=\begin{pmatrix}8 & 1 \\ 5 & 3\end{pmatrix}, \end{align*}

we calculate the inverse as follows

\begin{align*} m^{-1}&=(8\cdot 3- 5\cdot 1)^{-1}\begin{pmatrix}3 & -1 \\ -5 & 8\end{pmatrix}\\ &\equiv 19^{-1}\begin{pmatrix}3 & 25 \\ 21 & 8\end{pmatrix} &\pmod{26}\\ &\equiv 11\cdot\begin{pmatrix}3 & 25 \\ 21 & 8\end{pmatrix} &\pmod{26}\\ &\equiv \begin{pmatrix}11\cdot 3 & 11\cdot 25 \\ 11\cdot 21 & 11\cdot 8\end{pmatrix} &\pmod{26}\\ &\equiv \begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix} &\pmod{26} \end{align*}

which is what we had before.

Check your understanding by finding the inverse of

\begin{align*} m=\begin{pmatrix}17 & 21 \\ 15 & 8\end{pmatrix}. \end{align*}
Hint
\begin{gather*} det(m)=ad-bc. \end{gather*}

and

\begin{align*} m^{-1}=(det(m))^{-1}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}. \end{align*}
Answer
\begin{align*} m^{-1}=\begin{pmatrix}20 & 19 \\ 21 & 23\end{pmatrix}. \end{align*}

Check your understanding by finding the inverse of

\begin{align*} m=\begin{pmatrix}3 & 7 \\ 2 & 1\end{pmatrix}. \end{align*}
Hint
\begin{gather*} det(m)=ad-bc. \end{gather*}

and

\begin{align*} m^{-1}=(det(m))^{-1}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}. \end{align*}
Answer
\begin{align*} m^{-1}=\begin{pmatrix}7 & 3 \\ 12 & 21\end{pmatrix}. \end{align*}

Check your understanding by finding the inverse of

\begin{align*} m=\begin{pmatrix}3 & 3 \\ 6 & 9\end{pmatrix}. \end{align*}
Hint
\begin{gather*} det(m)=ad-bc. \end{gather*}

and

\begin{align*} m^{-1}=(det(m))^{-1}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}. \end{align*}
Answer
\begin{align*} m^{-1}=\begin{pmatrix}1 & 17 \\ 8 & 9\end{pmatrix}. \end{align*}

We are now, finally, ready to decipher a message. Suppose the message NDGUF SJV had been enciphered using Hill's cipher with multiplier

\begin{align*} m=\begin{pmatrix}8 & 1 \\ 5 & 3\end{pmatrix}, \end{align*}

to decipher we split the message into pairs and multiply those pairs by

\begin{align*} m^{-1}=\begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix}. \end{align*}

So for the first two letters we get

\begin{align*} m^{-1}\begin{pmatrix}N \\ D\end{pmatrix} =\begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix}\begin{pmatrix}13 \\ 3\end{pmatrix} \equiv\begin{pmatrix}6 \\ 17\end{pmatrix}\pmod{26} \equiv\begin{pmatrix}g \\ r\end{pmatrix}. \end{align*}

And, for the next two letters of cipher text

\begin{align*} m^{-1}\begin{pmatrix}G \\ U\end{pmatrix} =\begin{pmatrix}7 & 15 \\ 23 & 10\end{pmatrix}\begin{pmatrix}6 \\ 20\end{pmatrix} \equiv\begin{pmatrix}4 \\ 0\end{pmatrix}\pmod{26} \equiv\begin{pmatrix}e \\ a\end{pmatrix}. \end{align*}

Finish deciphering the message NDGUF SJV.

Hint
  1. Change each pair of consecutive letters into a pair of numbers, this is a vector.
  2. Multiply the vector by the matrix \(m^{-1}\text{.}\)
  3. Reduce the result modulo 26 and change back to letters, this is your plain text.
Answer

great job

Decipher the message TYEMC QDE which was enciphered with the matrix

\begin{align*} m=\begin{pmatrix}7 & 4 \\ 0 & 3\end{pmatrix}. \end{align*}
Hint
  1. Find the inverse matrix \(m^{-1}\text{.}\)
  2. Change each pair of consecutive letters into a pair of numbers, this is a vector.
  3. Multiply the vector by the matrix \(m^{-1}\text{.}\)
  4. Reduce the result modulo 26 and change back to letters, this is your plain text.
Answer

nice work

Decipher the message URYMB FXFLS which was enciphered by multiplying the plain text by

\begin{align*} m=\begin{pmatrix}7 & 4 \\ 0 & 3\end{pmatrix}, \end{align*}

and then adding the vector

\begin{gather*} s=\begin{pmatrix}7 \\ 5\end{pmatrix}. \end{gather*}
Hint
  1. Find the inverse matrix \(m^{-1}\text{.}\)
  2. Change each pair of consecutive letters into a pair of numbers, this is a vector.
  3. Subtract the vector \(s\) from this vector.
  4. Multiply the new vector by the matrix \(m^{-1}\text{.}\)
  5. Reduce the result modulo 26 and change back to letters, this is your plain text.
Answer

hello again

In conclusion we can give Hill's cipher the following general definition.

Definition 6.3.18. Hill's Cipher.

Hill's cipher is a cipher with a two part key, a multiplier \(m\) which is a square \(n\times n\) matrix and a shift \(s\) which is a vector with \(n\) entries; typically all the arithmetic is done modulo 26. Characters of the plain text are enciphered \(n\) at a time with the formula

\begin{equation*} CIPHER\,\equiv\, m(plain)+s\pmod{26}, \end{equation*}

where \(plain\) is a vector of \(n\) characters. Likewise, characters of the cipher text are deciphered \(n\) at a time with the formula

\begin{equation*} plain\,\equiv\, m^{-1}(CIPHER-s)\pmod{26}, \end{equation*}

or

\begin{equation*} plain\,\equiv\, m^{-1}CIPHER-m^{-1}s\pmod{26}. \end{equation*}

Note that the multiplier \(m\) must have a multiplicative inverse.

We end with two important observations. First, modern explanations of Hill's cipher focus on the simplest case when the matrix has dimension \(2\times 2\) and there is no shift. Second, you should be able to see that Hill's cipher is a variation on a affine cipher which enciphers multiple characters at a time in order to mix up the frequencies, this means it is a type of polygraphic cipher.

Figure 6.3.19. Hill's Cipher Cell

Subsubsection 6.3.2.3 Alternate Explanation

Figure 6.3.20. Modern look at Hill's Cipher