4
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 16, 2012 at 16:16
  • $\begingroup$ 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. $\endgroup$
    – ecem
    Oct 17, 2012 at 9:58
  • $\begingroup$ 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? $\endgroup$ Oct 17, 2012 at 11:37
  • $\begingroup$ 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.) $\endgroup$
    – bob
    Oct 17, 2012 at 12:10
  • 2
    $\begingroup$ @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. $\endgroup$
    – ecem
    Oct 17, 2012 at 12:28

3 Answers 3

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ +1 also for the idea of reducing to two problems modulo $\mathbb{Z}_2$ and $\mathbb{Z}_{13}$ $\endgroup$ Oct 19, 2012 at 5:51
4
$\begingroup$

Your reasoning is correct.

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}.$$

$\endgroup$
1
  • $\begingroup$ +1 for being first to suggest using the decryption matrix as unknown; we now are in agreement. $\endgroup$ Oct 19, 2012 at 5:55
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$
    – bob
    Oct 18, 2012 at 6:51
  • $\begingroup$ 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. $\endgroup$
    – ecem
    Oct 18, 2012 at 9:25
  • $\begingroup$ 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). $\endgroup$
    – bob
    Oct 18, 2012 at 13:06
  • $\begingroup$ 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. $\endgroup$
    – bob
    Oct 18, 2012 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.