# Hill Cipher known plaintext attack

I know a plaintext - ciphertext couple of length 6 for a hill cipher where its key is a [3x3] matrix.

Based on what I've read and learned, to attack and crack keys of [n x n], if we know a plaintext - ciphertext duo of length $n^2$ then we have our set of n equations with n variables, and this is generally solvable. However in my case there is only length of $6$ instead of $n^2 = 9$ .

My question is, how will I solve this problem and find the key? Or, since this is an obvious homework question, what should be my way of thinking? I cannot think of anything else but matrix multiplications and inverses but they do not help me at all.

-
You're right, as far as I can tell that should not be enough to solve for the matrix. Do you have any additional information, like undecrypted ciphertext? Or could the keyspace be limited somehow? –  Ilmari Karonen Oct 16 '12 at 16:16
I have another ciphertext that I'm required to decrypt of length 12 and as a hint I know its first letter. The hint should be useful I believe but I could not use it. –  ecem Oct 17 '12 at 9:58
Is it correct that you are given 6+12 bytes of ciphertext, and 6+1 bytes of the corresponding plaintext, and want the 11 other bytes of plaintext? –  fgrieu Oct 17 '12 at 11:37
What are the second value and the third value of the ciphertext of length 12? (Or maybe you can post all of the values? We won't give the solution, but hint towards the method.) –  bob Oct 17 '12 at 12:10
@bob we know that "erkays" is encrypted to "devuao" and the ciphertext to be decrypted is "LQDUIRXSFFHO" and we know its first letter is S. That's all the information. –  ecem Oct 17 '12 at 12:28

Well, I went and solved the puzzle using brute force and Maple. I won't spoil the actual answer, but here are some tips that ought to make the process a bit more quicker.

• Solving the linear system modulo 2 gives you the parity of the second and third letters of the unknown plaintext. Note that all vowels in the English alphabet map to even numbers using the standard Hill cipher encoding!

• Conversely, solving the system modulo 13 tells you the fourth letter of the unknown plaintext (up to rot13). This, together with the mod 2 solution, should help you guess what the second and third letters could be.

• Even after correctly guessing the second and third letters, and ruling out any non-invertible decoding matrices, the modulo 2 solution will still not be fully determined. Thus, some brute force and/or guesswork will be required to decode the remaining letters. Hopefully, however, one of the possible plaintexts will show up as obviously more plausible than the others.

Ps. One more hint: 007.

-
+1 "All the vowels have the same parity." –  bob Oct 18 '12 at 18:25
+1 also for the idea of reducing to two problems modulo $\mathbb{Z}_2$ and $\mathbb{Z}_{13}$ –  fgrieu Oct 19 '12 at 5:51

However, there is still some information to be exploited: as you know already, the matrix used to encrypt (the secret key) need to be invertible in order to allow decryption. Since you basically know (say) the first column and the second column of the secret key from your plaintext/ciphertext, you derive from the invertibility of the matrix that the third one must not be co-linear to any (linear) combination of the first two.

You can also take the following view. Let us assume that you look for the decryption matrix: $$M=\pmatrix{A_0 & b_0 & c_0 \\ A_1 & b_1 & c_1 \\ A_2 & b_2 & c_2 \\} .$$ From your knowledge of the plaintext/cipertext pairs, you can rewrite it: $$M=\pmatrix{ A_0 & \alpha_0 A_0 + \beta_0 & \gamma_0 A_0 + \delta_0 \\ A_1 & \alpha_1 A_1 + \beta_1 & \gamma_1 A_1 + \delta_1 \\ A_2 & \alpha_2 A_2 + \beta_2 & \gamma_2 A_2 + \delta_2 \\ }$$ where the $\alpha_i$, $\beta_i$, $\gamma_i$, and $\delta_i$ are known. Now for the ciphertext $z$ that you try to decrypt, it can be the case that $M\times z$ exhibits some strange properties. For instance, it could be that $M\times z$ does not depend on some or all of the $A_i$, that is: $$z_0+\alpha_i z_1 + \gamma_i z_2 = 0\pmod{26}.$$

-
+1 for being first to suggest using the decryption matrix as unknown; we now are in agreement. –  fgrieu Oct 19 '12 at 5:55

There are 18 plaintext and ciphertext letters $p_j$ and $c_j$, $0\le j<18$ (with $j<6$ for the "first plaintext"), all of which are known except $p_7..p_{17}$.

Let $M=\pmatrix{m_{0,0}&m_{0,1}&m_{0,2}\\m_{1,0}&m_{1,1}&m_{1,2}\\m_{2,0}&m_{2,1}&m_{2,2}}$ be the key matrix (unknown, except that it is invertible).

We have 18 linear equations in $\mathbb{Z}_{26}$ $$c_j=m_{j\bmod3,0}\cdot p_{3{\lfloor{j/3}\rfloor}}+m_{j\bmod3,1}\cdot p_{3{\lfloor{j/3}\rfloor}+1}+m_{j\bmod3,2}\cdot p_{3{\lfloor{j/3}\rfloor}+2}$$ with 20 unknowns, and the tiny information that $M$ is invertible. By an entropy argument, this can't be solved in the general case unless by exploiting redundancy in the second plaintext.

One (naïve) possibility to solve the problem could be: using a computer, for each of the $26\cdot26=676$ combinations of $p_7$ and $p_8$, solve the first 9 equations (when possible and there is a unique invertible solution for $M$, which is I guess is for most combinations of $p_7$ and $p_8$), and display the resulting second ciphertext $p_6..p_{17}$; then find the most likely one using vision and brain.

Update: But wait, we should use as unknown the decryption matrix $\hat M$ and the equations $$p_j=\hat m_{j\bmod3,0}\cdot c_{3{\lfloor{j/3}\rfloor}}+\hat m_{j\bmod3,1}\cdot c_{3{\lfloor{j/3}\rfloor}+1}+\hat m_{j\bmod3,2}\cdot c_{3{\lfloor{j/3}\rfloor}+2}$$ The 3 unknowns $\hat m_{0,0},\hat m_{0,1},\hat m_{0,2}$ can (likely) be found just by solving the system of 3 equations involving $p_0, p_3, p_6$. We can then compute $p_9, p_{12}, p_{15}$ without any guesswork.

Similarly, any guess of any of the 8 remaining plaintext letters $p_j$ gives one extra equation involving $\hat m_{j\bmod3,0},\hat m_{j\bmod3,1},\hat m_{j\bmod3,2}$, which (likely) is enough to deduce these 3 unknowns and 3 others plaintext letters. That greatly ease tabulating the possible plaintexts, from which only a few will hopefully emerge as making sense. That could even be workable just with pencil and paper.

In a computer search, the possible plaintexts could be ranked by their likelyhood given the frequency of digrams in English text.

Further update: It could well be that the system of equations for $\hat m_{0,0},\hat m_{0,1},\hat m_{0,2}$ has several solutions (I guess 2, 13, or 26), making the problem harder. It could also be that this system has no solution, in which case we could rule out the statement as faulty.

-
It is interesting to see that your update expands the steps described in my comment that you doubt above. (We're not unlucky here since the system---leading to the discovery of the first row of the decryption matrix---has exactly two solutions.) btw: +1 for the clean description of the standard key recovery strategy (although you could have avoided the cumbersome indexing scheme: it's compact for you to write but a pain to read) –  bob Oct 18 '12 at 6:51
As far as I understand from both of your answers and comments, I should try to recover decryption matrix first, and the encryption key will be just its inverse. I'll try to solve the problem with the information you provided when I get an answer I'll let you know again. –  ecem Oct 18 '12 at 9:25
The first row of the decryption matrix is easily recovered (there are two possibilities unless I erred). jgrieu is correct that the decryption matrix cannot be determined entirely (there are two unknown parameters) but there are three letters ciphertexts that will have as an image a determined value, that is, independent of those parameters. Using this info (additional plaintext/ciphertext pairs) one might be able to infer a very low number of possible encryption matrices (far less than exhausting the two parameters). –  bob Oct 18 '12 at 13:06
Also, do not forget that since you might know the underlying language and since you know the first, fourth, seventh, and tenth letter of the plaintext (from the two possible instances for the first row of the decryption matrix) you might be able to guess additional information. –  bob Oct 18 '12 at 13:08