Suppose a Hill cipher with block size 2 is given, with known plaintext and corresponding encryption
$E_K( ‘guns’ ) = ‘YGJC’$
What are the possibilities for the key $K$?
My initial thought was to setup:
$$KX=Y$$
Where $X$ is the matrix of the plaintext (guns) converted into columns of numbers where $a=0,b=1,…$, and $Y$ is the matrix of cipher text. I then solved for the key matrix $K=YX^{-1}$ and got
$$K=\begin{align*}
\begin{pmatrix}
\frac{-63}{38} & \frac{129}{76} \\ \frac{-17}{38} & \frac{33}{76}
\end{pmatrix}
\end{align*}$$
I feel modular arithmetic should be involved with the matrix, but I'm not sure how since the textbook doesn't mention anything nor did my professor do any examples. I'm under the impression that there might not even be a valid key matrix since the plaintext matrix is:
$$X=\begin{align*}
\begin{pmatrix}
6 & 13 \\ 20 & 18
\end{pmatrix}
\end{align*}$$
And $\det{(X)}=-152$ which is not coprime to $26$ so there's no multiplicative inverse $\mod{26}$??? I'm lost at how to find all the possible keys
Best Answer
You can write your equation $\ KX=Y\ $ as a set of four linear equations mod $26$ for the four unknown entries $\ k_{11},$$\,k_{21},$$\,k_{12},$$\,k_{22}\ $ of $\ K\ $: $$ \pmatrix{6&20&0&0\\ 13&18&0&0\\0&0&6&20\\0&0&13&18}\pmatrix{k_{11}\\k_{12}\\k_{21}\\k_{22}}=\pmatrix{24\\9\\6\\2}\ . $$ Because the integers modulo any prime form a field , the easiest way to find all the solutions (if any) of these equations is to find all the solutions mod $2$ and all the solutions mod $13$ and use the Chinese remainder algorithm to combine them together to get all the solutions of the original equations mod $26$. The coefficient matrix of the equations is singular mod $2$, with rank $2$. The equations are nevertheless consistent mod $2$, so you should be able to find a two-dimensional space of solutions for $\ k_{11},$$\,k_{21},$$\,k_{12},k_{22}\ $ mod $2$. Since there are only $\ 2\ $ elements in the field of integers mod $2$, this means that that there will be only four solution in your entire solution space. You should find, however, that two of these give you a matrix $\ K\ $ which isn't invertible mod $2$, so these can't provide you with a valid solution for $\ K\ $
The coefficient matrix of the above system of equations is non-singular mod $13$, which means there's a unique solution for $\ k_{11},$$\,k_{21},$$\,k_{12},k_{22}\ $ mod $13$, and this solution will give you a matrix $\ K\ $ which is invertible mod $13$. Having two solutions mod $2$ and a unique solution for $\ K\ $ mod $13$ means that you will have two solutions mod $26$. Once you've found them you can check that they both satisfy your equation $\ KX=Y\ $, so without further information you have no way of telling which of them is the actual key.
Response to queries from the OP in comments below
The equations for $\ k_{11},$$\,k_{21},$$\,k_{12},$$\,k_{22}\ $ above decouple into two pairs of two equations, one pair for $\ k_{11}\ $ and $\ k_{12}\ $ and the other for $\ k_{21}\ $ and $\ k_{22}\ $. To illustrate the procedure of Gaussian elimination mod $26$ I'll use it below to solve the first pair of equations for $\ k_{11}\ $ and $\ k_{12}\ .$ While the procedure is very similar to normal Gaussian elimination, all the elementary row operations you use must be reversible mod $26.$ This means that you can never multiply an equation by $13$ or an even number. Here is a sequence of elementary row operations for reducing the pair of linear congruences $$ 6k_{11}+20k_{12}\equiv24\pmod{26}\\ 13k_{11}+18k_{12}\equiv9\pmod{26} $$ to an equivalent pair for $\ k_{11}\ $ and $\ k_{12}\ $ separately. All the arithmetic in the procedure is carried out mod $26$. \begin{align} &\begin{array}{cc|cc} k_{11}&k_{12}\\ \hline 6&20&24\\ 13&18&9 \end{array}\\ &\begin{array}{cc|cc} k_{11}&k_{12}\\ \hline 6&20&24\\ 1&4&13&r_2\rightarrow r_2-2r_1 \end{array}\\ &\begin{array}{cc|cc} k_{11}&k_{12}\\ \hline 0&22&24&r_1\rightarrow r_1-6r_2\\ 1&4&13 \end{array}\\ &\begin{array}{cc|cc} k_{11}&k_{12}\\ \hline 0&2&14&r_1\rightarrow 19r_1\\ 1&4&13 \end{array}\\ &\begin{array}{cc|cc} k_{11}&k_{12}\\ \hline 0&2&14\\ 1&0&11&r_2\rightarrow r_2-2r_1 \end{array} \end{align} Thus, the above congruences are equivalent to $$ 2k_{12}\equiv14\pmod{26}\\ k_{11}\equiv11\pmod{26}\ $$ and the first of these has two solutions mod $26$—namely $\ k_{12}\equiv7\pmod{26}\ $ and $\ k_{12}\equiv20\pmod{26}\ $.