# Hill cipher cryptanalysis - known plaintext known key size

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.

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.

• How do I solve the linear equations? I have tried choosing some equations and solve for k0 and then find if it has a multiplicative inverse. But it doesn't seem to work – cryptonoob123 Mar 7 '14 at 17:05
• Can you post the cipher texts? Also are you sure the math is done mod 26 (that was my assumption)? – mikeazo Mar 7 '14 at 17:49
• Yes I am sure it is mod 26. Another example is m = 2, 17, 24, 15, 19, 14. c = 11, 18, 3, 10, 3, 7. Try this example :-) and thanks – cryptonoob123 Mar 7 '14 at 17:53
• @cryptonoob123 because I didn't know if this was homework or not, I didn't want to give a complete answer. Hopefully this helps at least. – mikeazo Mar 7 '14 at 18:30