Skip to main content

Section 6.4 Decrypting Hill's Cipher

Recall that when we encipher a message using Hill's Cipher we use either the equation:

\begin{equation*} \mathtt{Cipher}\equiv m\cdot Message\ \text{or}\ \mathtt{Cipher}\equiv m\cdot Message+s. \end{equation*}

Solving these for the ciphertext we got the equations:

\begin{equation*} Message = m^{-1}\mathtt{Cipher}\ \text{or}\ Message = m^{-1}\mathtt{Cipher}+(-m^{-1}s). \end{equation*}

In either case we need to find \(m^{-1}\) and if there is a shift \((-m^{-1}s)\text{.}\) For more details on how we used this previously look back at Subsubsection 6.3.2.2. What is important here is that to decrypt Hill's cipher we will need to find the same values, but we will need to set up equations to find them, like we did when cracking affine ciphers in Subsection 6.2.2.

Subsection 6.4.1 Comments on Matrix Inverses

Recall from Subsubsection 6.3.2.2 that to find the inverse of a matrix \(m\) we need to find

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

And, the matrix \(m\) will have a multiplicative inverse \(m^{-1}\) if and only if \(det(m)=ad-bc\) has a multiplicative inverse. For example consider the matrix

\begin{equation*} m= \begin{pmatrix} 5 \amp 3 \\ 4 \amp 3 \end{pmatrix} \end{equation*}

using the formula above we get that the inverse is

\begin{align*} m^{-1} \amp=(det(m))^{-1}\begin{pmatrix}d & -b \\ -c & a\end{pmatrix}\\ \equiv\amp (5\cdot 3-3\cdot 4)^{-1}\begin{pmatrix}3 & -3 \\ -4 & 5\end{pmatrix}\\ \equiv\amp 3^{-1}\begin{pmatrix}3 & -3 \\ -4 & 5\end{pmatrix}\\ \equiv\amp 9\begin{pmatrix}3 & -3 \\ -4 & 5\end{pmatrix}\\ \equiv\amp \begin{pmatrix}1 & 25 \\ 16 & 19\end{pmatrix} \end{align*}

Decryption will require us to be able to find matrix inverses (again review Subsubsection 6.3.2.2). So, it will be helpful to be able to tell at a glance when a matrix definitely isn't invertible so that you don't spend time trying to find an inverse that doesn't exist. Fortunately, sense \((ad-bc)\) must be invertible modulo 26 for our examples we know that it must be relatively prime to 26, so it can not be divisible by 2 or 13. In order for \((ad-bc)\) to be odd it must have one of four formats:

\begin{align*} m\amp=\begin{pmatrix}n & odd \\ odd & even\end{pmatrix}\\ m\amp=\begin{pmatrix}odd & n \\ even & odd\end{pmatrix} \end{align*}
\begin{align*} m\amp=\begin{pmatrix}odd & even \\ n & odd\end{pmatrix}\\ m\amp=\begin{pmatrix}even & odd \\ odd & n\end{pmatrix} \end{align*}

In each case we get a determinant of the form \(n\cdot even-odd\cdot odd\) or \(odd\cdot odd-n\cdot even\) both of which will be odd for any value of \(n\text{.}\) They may still be a multiple of 13, but at least they won't be even.

Looking at the four types of matrices listed above try to determine if this matrix is invertible before calculating the determinant, then try to find the inverse if it exists. Be sure to justify your answers and show your work.

\begin{equation*} m= \begin{pmatrix} 5 \amp 3 \\ 4 \amp 3 \end{pmatrix} \end{equation*}
Answer

Yes this appear invertible and we can get:

\begin{equation*} m^{-1}= \begin{pmatrix} 1 \amp 25 \\ 16 \amp 19 \end{pmatrix} \end{equation*}

Looking at the four types of matrices listed above try to determine if this matrix is invertible before calculating the determinant, then try to find the inverse if it exists. Be sure to justify your answers and show your work.

\begin{equation*} m= \begin{pmatrix} 2 \amp 17 \\ 0 \amp 3 \end{pmatrix} \end{equation*}
Answer

Not invertible

Looking at the four types of matrices listed above try to determine if this matrix is invertible before calculating the determinant, then try to find the inverse if it exists. Be sure to justify your answers and show your work.

\begin{equation*} m= \begin{pmatrix} 3 \amp 4 \\ 15 \amp 7 \end{pmatrix} \end{equation*}
Answer

Not invertible

Looking at the four types of matrices listed above try to determine if this matrix is invertible before calculating the determinant, then try to find the inverse if it exists. Be sure to justify your answers and show your work.

\begin{equation*} m= \begin{pmatrix} 0 \amp 7 \\ -3 \amp 14 \end{pmatrix} \end{equation*}
Answer

Yes this appear invertible and we can get:

\begin{equation*} m^{-1}= \begin{pmatrix} 18 \amp 17 \\ 15 \amp 0 \end{pmatrix} \end{equation*}

Subsection 6.4.2 Ciphertext Only Attack

Suppose we intercept the message below and through espionage we know that it was enciphered using a Hill's Cipher with only a multiplier.

PUOSP MQUPO AUQYD LEGXC UJXFG ODGXP OQPOC RHPDY 
CLCZV RVSUB OXPEX IWGEB BJVEN SCVNB AOXPX PQUDG 
AOVDA MWQJS AOZTW SEDDT CJUAV AKEWN VSDUC JAIVR 
NOPUO SPMQU POKZQ TBUXP ZMDIZ TLKOC CAAVV DXPWG 
UTWGU ZABOA PEOQU PDSJC EJXCC ZDTCJ ZVOCH KPGWJ 
CLCZN BRWPS DEBMC LPVNS EVQTP OUHSU VECBE NVDEN 
DWZAX NQUDQ UTCUU JXPHC QIETD HCFXI YKWSU MEDCF 
DXAFX PJGUH BJVEU FNMBU NKXPN OOEWG JCWNN AUFDT 
CJZJU YUPDR CJABH LDIUT CXNAW JKZXP WUMMW GENGK 
DQCJY XWSKR MWUIS UNCWA CJUAV DPSVE XGDGC JAFVH 
NKYKD IXZWU ZSDQC JEGYR WSXPN OZQ

As always we need to start with frequency analysis, but if we assume the message used a Hill's cipher with a \(2\times 2\) matrix we will focus on bigrams. For the text above the bigrams frequencies are as follows:

Table 6.4.5. Bigrams from a message with 428 characters
Rank N-Gram Count Percent
1. XP 10 2.336
2. CJ 9 2.103
3. QU 5 1.168
4. WG 5 1.168
5. TC 5 1.168
6. PO 4 0.9346
7. WS 4 0.9346
8. VE 4 0.9346
9. VD 4 0.9346
10. UP 4 0.9346

From what is above we can guess that XP and CJ represent plaintext th and he or vice versa. Using this we can write the possible equations:

\begin{align*} m\begin{pmatrix} t \\ h\end{pmatrix}\amp\equiv \begin{pmatrix} X \\ P\end{pmatrix}\ \text{and}\\ m\begin{pmatrix} h \\ e\end{pmatrix}\amp\equiv \begin{pmatrix} C \\ J\end{pmatrix}. \end{align*}

Translating the letters into numbers this gives the equations:

\begin{align*} m\begin{pmatrix} 19 \\ 7\end{pmatrix}\amp\equiv \begin{pmatrix} 23 \\ 15\end{pmatrix}\ \text{and}\\ m\begin{pmatrix} 7 \\ 4\end{pmatrix}\amp\equiv \begin{pmatrix} 2 \\ 9\end{pmatrix} \end{align*}

which can be combined into the matrix equation:

\begin{equation*} m\begin{pmatrix} 19 \amp 7\\ 7\amp 4\end{pmatrix}\equiv \begin{pmatrix} 23\amp 2 \\ 15\amp 9\end{pmatrix}. \end{equation*}

Solving this for \(m^{-1}\) we get the inverse key:

\begin{align*} m^{-1}\amp\equiv \begin{pmatrix} 19 \amp 7\\ 7\amp 4\end{pmatrix} \begin{pmatrix} 23\amp 2 \\ 15\amp 9\end{pmatrix}^{-1}\\ \amp\equiv \begin{pmatrix} 19 \amp 7\\ 7\amp 4\end{pmatrix} \begin{pmatrix} 19\amp 16 \\ 3\amp 11\end{pmatrix}\\ \amp\equiv \begin{pmatrix} 23-5 \amp 18-1\\ 3+12\amp 8-8\end{pmatrix}\\ \amp\equiv \begin{pmatrix} 18 \amp 17\\ 15\amp 0\end{pmatrix} \end{align*}

Applying the inverse matrix

\begin{equation*} m^{-1}=\begin{pmatrix} 18 \amp 17\\ 15\amp 0\end{pmatrix} \end{equation*}

to the first little bit of the cipher text gives us the output

MRMCG REGOR CAUGH TSIGH TOFHI MATTH ECORN ERBUT

or “Mr. McGregor caught sight of him at the corner but ...”  1 

For another example of this be sure to read through Section E.4.

Suppose that frequency analysis tells you that a Hill's cipher with just a multiplier \(m\) seems to have enciphered th as QR and he as FI. Use this information to find the deciphering matrix \(m^{-1}\text{.}\)

Answer
\begin{equation*} m^{-1}=\begin{pmatrix} 5 \amp 1\\ 10\amp 17\end{pmatrix} \end{equation*}

Suppose that frequency analysis tells you that in a message enciphered with Hill's cipher with just a multiplier \(m\) the three most common bigrams are HR, KL, and TY. Given that the most common English bigrams are th, he, and in, try and find the deciphering matrix \(m^{-1}\text{.}\)

Hint

After enciphering th is not necessarily going to be the most common bigram but it will probably be near the top along with he.

Answer
\begin{equation*} m^{-1}=\begin{pmatrix} 6 \amp 1\\ 5\amp 15\end{pmatrix} \end{equation*}

Given a message with 1230 characters and the following bigrams:

Table 6.4.9.
Rank N-Gram Count Percent
1. DT 25 2.033
2. LY 23 1.87
3. ZN 18 1.463
4. FU 17 1.382
5. YK 14 1.138
6. SY 14 1.138
7. IH 14 1.138
8. AO 13 1.057
9. KB 12 0.9756
10. XO 11 0.8943

Which bigrams most likely represent th and he? Try to use this information to find the deciphering matrix \(m^{-1}\text{.}\) Check your work by deciphering this snippet of the text ORLQO EZHXB CRQHY JDTPT YLJQE QTRHS SYQQG PANVJ ... .

Hint

After enciphering th is not necessarily going to be the most common bigram but it will probably be near the top along with he.

Answer

In this case DT is he and LY is th. Using this information we can get:

\begin{equation*} m^{-1}=\begin{pmatrix} 9 \amp 14\\ 9\amp 7\end{pmatrix} \end{equation*}

Subsection 6.4.3 Known Plaintext Attack

Suppose that you know your opponent issues a status update to their minions every day at 5 am and always signs it “Benevolent Leader.” This is an example of a crib (see Definition 4.1.15). We can use this to crack whatever cipher that is being used.

Let's assume in this instance that a Hill's cipher with a shift was used so that the enciphering algorithm looked like

\begin{equation*} \mathtt{C}\equiv m\, M+s \end{equation*}

this means we will use

\begin{equation*} M\equiv m^{-1}\, \mathtt{C}+(-m^{-1}s) \end{equation*}

to decipher. Suppose the message ends with EN OL YT IH TM IH SE AG which corresponds to “Benevolent Leader”, this is our crib, using these we get the following equations (once we change the letters to numbers):

\begin{align} m\begin{pmatrix}1\\ 4\end{pmatrix}+s\amp \equiv \begin{pmatrix}4 \\ 13\end{pmatrix}\label{kpt_hill_eq1}\tag{6.4.1}\\ m\begin{pmatrix}13\\ 4\end{pmatrix}+s\amp \equiv \begin{pmatrix}14 \\ 11\end{pmatrix}\label{kpt_hill_eq2}\tag{6.4.2}\\ m\begin{pmatrix}21\\ 14\end{pmatrix}+s\amp \equiv \begin{pmatrix}24 \\ 19\end{pmatrix}\label{kpt_hill_eq3}\tag{6.4.3}\\ m\begin{pmatrix}11\\ 4\end{pmatrix}+s\amp \equiv \begin{pmatrix}8 \\ 7\end{pmatrix}\tag{6.4.4} \end{align}
\begin{align} m\begin{pmatrix}13\\ 19\end{pmatrix}+s\amp \equiv \begin{pmatrix}19 \\ 12\end{pmatrix}\label{kpt_hill_eq5}\tag{6.4.5}\\ m\begin{pmatrix}11\\ 4\end{pmatrix}+s\amp \equiv \begin{pmatrix}8 \\ 7\end{pmatrix}\label{kpt_hill_eq6}\tag{6.4.6}\\ m\begin{pmatrix}0\\ 3\end{pmatrix}+s\amp \equiv \begin{pmatrix}18 \\ 4\end{pmatrix}\label{kpt_hill_eq7}\tag{6.4.7}\\ m\begin{pmatrix}4\\ 17\end{pmatrix}+s\amp \equiv \begin{pmatrix}0 \\ 6\end{pmatrix}\label{kpt_hill_eq8}\tag{6.4.8} \end{align}

Just as with an affine cipher we need to subtract pairs of equations from one another to get rid of the shift \(s\text{.}\) But, we need to be sure we are left with matrices that can be inverted. For example if we subtracted equation (6.4.2) from equation (6.4.1) and equation (6.4.3) from (6.4.2) we are left with the matrix equation:

\begin{equation*} m\begin{pmatrix}-12 \amp-8 \\ 0 \amp -10\end{pmatrix}\equiv\begin{pmatrix}-10 \amp -10 \\ 2 \amp -8 \end{pmatrix} \end{equation*}

and the matrix on the right hand side is not invertible. So, we need to keep in mind the ideas from Subsection 6.4.1 and pick the equations that will leave us some invertible matrices.

Since equation (6.4.5) is the only one that has an odd number in the first entry on the right it turns out we have to use that one. We can subtract equation (6.4.2) from it to get:

\begin{gather*} m\begin{pmatrix} 0 \\ 15 \end{pmatrix}\equiv\begin{pmatrix} 5 \\ 1 \end{pmatrix} \end{gather*}

Since we have two odds on the right we need to combine a couple equations to get an even and an odd, and a determinant that isn't a multiple of 13. For example subtracting equation (6.4.8) from equation (6.4.6) we get

\begin{gather*} m\begin{pmatrix} 7 \\ -13 \end{pmatrix}\equiv\begin{pmatrix} 8 \\ 1 \end{pmatrix}. \end{gather*}

Combining the previous two equations we get the matrix equation:

\begin{equation*} m\begin{pmatrix}0 \amp 7 \\ 15 \amp 13\end{pmatrix}\equiv\begin{pmatrix} 5 \amp 8 \\ 1 \amp 1 \end{pmatrix}. \end{equation*}

Now we can solve for \(m^{-1}\) as we have before:

\begin{align*} m^{-1} \amp\equiv \begin{pmatrix}0 \amp 7 \\ 15 \amp 13\end{pmatrix}\begin{pmatrix} 5 \amp 8 \\ 1 \amp 1 \end{pmatrix}^{-1}\\ \amp\equiv \begin{pmatrix}0 \amp 7 \\ 15 \amp 13\end{pmatrix}\begin{pmatrix} -9 \amp -6 \\ 9 \amp 7 \end{pmatrix}^{-1}\\ \amp\equiv \begin{pmatrix}11 \amp 23 \\ 8 \amp 1\end{pmatrix}. \end{align*}

Finally, back substituting this into equation (6.4.8) we can solve for \(m^{-1}s\text{:}\)

\begin{align*} m^{-1}s\amp \equiv \begin{pmatrix}11 \amp 23 \\ 8 \amp 1\end{pmatrix}\begin{pmatrix}0 \\ 6 \end{pmatrix}-\begin{pmatrix} 4 \\ 17\end{pmatrix}\\ \amp \equiv \begin{pmatrix} 8 \\ 6 \end{pmatrix}-\begin{pmatrix} 4 \\ 17\end{pmatrix}\\ \amp \equiv \begin{pmatrix} 4 \\ -11 \end{pmatrix}\equiv \begin{pmatrix} 4 \\ 15\end{pmatrix}. \end{align*}

Armed now with the decryption key:

\begin{equation*} m^{-1}=\begin{pmatrix}11 \amp 23 \\ 8 \amp 1\end{pmatrix}\ \text{and}\ (-m^{-1}s)= \begin{pmatrix} -4 \\ -15\end{pmatrix} \end{equation*}

we can check that it works to decipher our known piece of text and then decipher the original message.  2 

For another example of this be sure to read through Section E.5.

Given the cipher text EIYPL HZPXJ XE and corresponding known plaintext “weather alert” determine the deciphering key.

Hint
Only a matrix was used to encipher the message, there is no shift.
Answer
\begin{equation*} m^{-1}=\begin{pmatrix}17 \amp 4\\ 7 \amp 23\end{pmatrix} \end{equation*}

Given the cipher text XSVCC KZYLL LV and corresponding known plaintext “status update” determine the deciphering key.

Hint
This cipher used a shift as well as a multiplier.
Answer
\begin{equation*} m^{-1}=\begin{pmatrix}4 \amp -1\\ -11 \amp 3\end{pmatrix}\ \text{and}\ m^{-1}s=\begin{pmatrix}4\\ 16\end{pmatrix} \end{equation*}

Given the cipher text UIYJG NQTYF GM and corresponding known plaintext “dear students” determine the deciphering key.

Hint
This cipher used a shift as well as a multiplier.
Answer
\begin{equation*} m^{-1}=\begin{pmatrix}19 \amp -1\\ 16 \amp 1\end{pmatrix}\ \text{and}\ m^{-1}s=\begin{pmatrix}5\\ 12\end{pmatrix} \end{equation*}

Subsection 6.4.4 Utilities

When you are enciphering you need to put in the keys \(m\) and \(s\text{.}\) When deciphering you need to put in \(m^{-1}\) and \((-m^{-1}s)\text{.}\)

Figure 6.4.13. Hill's Cipher Cell
Figure 6.4.14. N-Gram Analysis Cell