Hill's Cipher Analysis (Known Plaintext)

Section E.5 Hill's Cipher Analysis (Known Plaintext)

Suppose that we intercept the following cipher text:

VDIAU ZQPBI NPEAF LFJHZ WNVRK YOHWB IWQSV DIAUZ 
YHMGK FLPRH LKYKK FJFSN MTHFS KPZKL FWBRK NVAUI 
ZNJAZ DFOAS LMIWZ DFOSG IAVDE KRHLK EKJVV SRHXA 
XNEKD LJEJV VSGMY PWEAS SGMGL HBDXA MGTCM GTTVA 
SLCVT ABBXG BZYIG RBZBU BRWBV FLMUZ ENGZQ YOOLH 
QOVDE KMGCT JZXRI STNKI MLXAZ TJZAX DCPLM LLJPO 
LDOQF DYWQS WHVVI SOQKY BBSXP OFNAK DPAXO RMWMQ 
QSMTJ BIWET BZGPX DOUDG UZZNP UIYJF TCQSW HRZUZ 
UBVAU IZNJA ZDFOA SLMIW ZDFOT JCLWE RXTNG RRHLK 
VTBDX GXUZF KYBDL KYITV VFMTI BZSBR MLNKZ TSLGG 
VTBDX GENXU ZFLKZ FDSKY NXNKZ TSLGG VTBDX GBZDJ 
IBMMO UWNGV KOZFM GBDET NXLDD FMTDL HWLCB RHBWB 
IWKYY SMTCL MTJAL HXRWE RLWZT NZTNU QPPLS ORLSD 
UZLKI XKFIN LHYPH TQSCB ACGYM GIASK RTQDK ALCQO 
UIIKW WDZWH TVVFM TBDBW HXCDZ SBRML

And, further suppose that we know it is a weather report of some sort so that it starts with the word “weather.” That is we know that the ciphertext VDIAUZQ pairs with the plaintext “weather,” this is called a crib. Finally, suppose that either through analysis or espionage we know that a Hill's Cipher was used to encipher the message. Let's see if we can recover the key.

Using the crib (VDIAUZQ equals “weather”) we can set up three equations, the minimum needed to solve a general Hill's cipher:

\begin{align*} \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} V \\ D\end{pmatrix}+s & \equiv \begin{pmatrix}w \\ e \end{pmatrix} \\ \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} I \\ A\end{pmatrix}+s & \equiv \begin{pmatrix}a \\ t \end{pmatrix} \\ \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} U \\ Z\end{pmatrix}+s & \equiv \begin{pmatrix}h \\ e \end{pmatrix} \end{align*}

or written with numbers:

\begin{align} \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 21 \\ 3\end{pmatrix}+s & \equiv \begin{pmatrix}22 \\ 4 \end{pmatrix} \label{hill_KPT_equation_1}\tag{E.5.1}\\ \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 8 \\ 0\end{pmatrix}+s & \equiv \begin{pmatrix}0 \\ 19 \end{pmatrix} \label{hill_KPT_equation_2}\tag{E.5.2}\\ \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 20 \\ 25\end{pmatrix}+s & \equiv \begin{pmatrix}7 \\ 4 \end{pmatrix} \label{hill_KPT_equation_3}\tag{E.5.3} \end{align}

If we subtract equation (E.5.2) from (E.5.1) and (E.5.3) from (E.5.2), we eliminate the \(s\) and can then solve for the matrix (remember that all the arithmetic is modulo 26):

\begin{align*} \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 13 \\ 3\end{pmatrix} & \equiv \begin{pmatrix}22 \\ 11 \end{pmatrix} \\ \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 14 \\ 1\end{pmatrix} & \equiv \begin{pmatrix}19 \\ 15 \end{pmatrix} \end{align*}

or condensed to a single equation:

\begin{align*} \begin{pmatrix} a & b\\ c & d\end{pmatrix}\begin{pmatrix} 13 \amp 14\\ 3 \amp 1\end{pmatrix} & \equiv \begin{pmatrix}22 \amp 19 \\ 11\amp 15 \end{pmatrix}. \end{align*}

Solving for the unknown matrix we get:

\begin{align} \begin{pmatrix} a & b\\ c & d\end{pmatrix} & \equiv \begin{pmatrix}22 \amp 19 \\ 11\amp 15 \end{pmatrix}\begin{pmatrix} 13 \amp 14\\ 3 \amp 1\end{pmatrix}^{-1}\notag\\ & \equiv \begin{pmatrix}22 \amp 19 \\ 11\amp 15 \end{pmatrix}(23^{-1})\begin{pmatrix} 1 \amp -14\\ -3 \amp 13\end{pmatrix}\notag\\ & \equiv \begin{pmatrix}3 \amp 3 \\ 20\amp 21 \end{pmatrix}=m^{-1}.\label{hill_KPT-matrix}\tag{E.5.4} \end{align}

Armed now with the matrix from equation (E.5.4) we can substitute that into equation (E.5.1) to find \(s\text{:}\)

\begin{align} s\amp = \begin{pmatrix}22 \\ 4 \end{pmatrix}- \begin{pmatrix}3 \amp 3 \\ 20\amp 21 \end{pmatrix}\begin{pmatrix}21 \\ 3 \end{pmatrix}\notag\\ \amp = \begin{pmatrix}2 \\ 15 \end{pmatrix}.\label{hill_KPT_shift}\tag{E.5.5} \end{align}

Finally, we can test our work by applying the shift \(s\) from equation (E.5.5) and the matrix \(m^{-1}\) from equation (E.5.4) to our cipher text using the Hill's Cipher App in Appendix B to see if we get a meaningful message. The key does give a message; it appears to be part of the following weather advisory:

WEATHER ADVISORY
ISSUED: 10:54 AM MAR. 26, 2021 – NATIONAL WEATHER SERVICE
...WIND ADVISORY REMAINS IN EFFECT UNTIL MIDNIGHT EDT TONIGHT...

* WHAT...West winds 15 to 30 mph with gusts up to 50 mph
expected.

* WHERE...Southern Vermont, Litchfield County, Connecticut, the
Berkshires of western Massachusetts, the eastern Catskills,
Mohawk Valley, Schoharie Valley, Greater Capital Region,
Taconics, and the mid Hudson Valley.

* WHEN...Until midnight EDT tonight.

* IMPACTS...Gusty winds could blow around unsecured objects. Tree
limbs could be blown down, large tree limbs could come down and
a few power outages may result.

PRECAUTIONARY/PREPAREDNESS ACTIONS...

Use extra caution when driving, especially if operating a high
profile vehicle. Secure outdoor objects.

Below is a copy of the scrap hand work that went into finding the key for this cipher.