Hill cipher cryptanalysis - known plaintext known key size

Question

Hello I want to know how to go about this problem I know the plaintext "abcdef" and the ciphertext. The key size is 2. I really can't figure out how to find the key for decrypting and encrypting.

Answer 1

Let $k=\left(\begin{array}{cc}k_0 & k_1\\k_2 & k_3\end{array}\right)$ be the key. And I'll assume the transformation $a=0$, $b=1$, and so on.

So you know $k\left(\begin{array}{c}0\\1\end{array}\right)=\left(\begin{array}{c}c_0\\c_1\end{array}\right)$ where you know $c_0$ and $c_1$.

Thus $c_0=0k_0+1k_1$ and $c_1=0k_2+1k_3$. So that is two equations, 4 unknowns. Can't be solved yet. But you have more data which gives you $c_2=2k_0+3k_1$, $c_3=2k_2+3k_3$, $c_4=4k_0+5k_1$ and $c_5=4k_2+5k_3$. Now you have 6 equations and 4 unknowns. Setup a system of linear equations and solve. That will give you the $k_i$ values for your key. The decryption key is just the inverse.

Remember that the math is done modulo 26.

You won't always be able to solve the system of linear equations, but you likely have enough plaintext ciphertext pairs to get it done. Using the PT/CT pairs in the comments, for example, you would end up with the following equations for $k_0,k_1$.

$$ \begin{align*} 2k_0+17k_1&=11\\ 24k_0+15k_1&=3\\ 19k_0+14k_1&=3 \end{align*} $$

From there, my preferred method is to take two of the equations, build an augmented matrix and put it in reduced row echelon form. So you'd first have

$$\left(\begin{array}{cc|c}19&14&3\\2&17&11\end{array}\right)$$

Instead of doing all the math, I'll just get you started. Start by multiplying the first row by $19^{-1}=11$. Then you would have

$$\left(\begin{array}{cc|c}1&24&7\\2&17&11\end{array}\right)$$

Then you want to get rid of the $2$ on the second row, so do $row_2=row_2-2row_1$. Eventually you'll be in the right form and have $k_0$ and $k_1$. Repeat this process for $k_2$ and $k_3$. For this one it will work out. If you had started with the $3=24k_0+15k_1$ row on top, you may have gotten stuck since $24$ has no inverse. So if you get stuck (needing to invert something that is non-invertible), try a different equation or a different set of elementary row operations.