4
$\begingroup$

I have been wondering what approach to take in order to figure out what key was used to encrypt a message using the hill cipher. I know it is possible to obtain it even if it were just a known-plaintext attack, so it should be fairly possible for a chosen-plaintext one. I'm trying to figure it out with just intuition, but since I know freq. analysis won't be of help, I don't know what else to try. I want to get my head around this, but could someone point me in the right direction?

$\endgroup$
3
$\begingroup$

Sure. Assuming that you're using the encoding $A = 0$, $B = 1$, etc., just choose your plaintext messages to be the one-block strings:

$$ BA \dots A \\ AB \dots A \\ \vdots \\ AA \dots B $$

The encryptions of these strings will then directly give you the columns of your key matrix.

$\endgroup$
  • $\begingroup$ Sorry, it seems like I misunderstood your answer. I thought I could just encrypt each letter in the plaintext at a time, but it doesn't work since the key matrix is at least 2x2, right? Could you elaborate a bit more on what you mean by one-block strings? $\endgroup$ – Emyr Sep 27 '12 at 2:04
  • 1
    $\begingroup$ @Emyr: See this description of the Hill cipher: for an n.n matrix, plaintext letters are grouped by vectors of n letters. Ilmari Karonen suggest to encipher the n distinct vectors of n letters with n-1 A and 1 B; the resulting ciphertext is n vectors of n letters, which form the n.n key matrix. $\endgroup$ – fgrieu Sep 27 '12 at 9:39
0
$\begingroup$

An easier way to say what Ilmari Karonen said is: Choose the plaintext to be the identity matrix. Thus, when it is multiplied by the key, the resultant ciphertext will be the key it self.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Cryptography. This is rather a comment. Also, the plaintext in the Hill cipher is not a Matrix, it is a vector. Ofcource you can calculate an $n$ vector by the $n\times x$ key matrix. $\endgroup$ – kelalaka Oct 18 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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