Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've been struggling on this problem for a while now : the Hill cipher is well-known to be vulnerable to known-plaintext attack due to its linearity. Given a key matrix $K$ of size $n\times n$, one can retrieve the key with as little as $n^2$ plaintext/cipher text couples.

All examples found on the Internet assume an alphabet where $A=0, B=1 \dots Z=25$, but how could we break the Hill cipher using a know-plaintext attack without any clue over the alphabet permutation nor the key matrix ?

I've tried several things such as linearizing the whole set of equations together, however it requires several divisions in $\bf{Z}_{26}$ which aren't possible (i.e. division by even numbers or 13)

share|improve this question

1 Answer

Well, I'll assume that we'll use the same mapping between letters and integers both to translate the plaintext into integers (to be matrix multipled), and the integers (after the matrix multiply) back into ciphertext. And, we don't know that mapping, the key matrix $K$, and possibly the value of $n$.

If so, the obvious place to start is to attempt to solve this $\bmod \ 2$. The key matrix $K$ consists of integers modulo 26; because 2 is a divisor of 26, it can be treated as if it consists of integers modulo 2. The mapping assigns 13 characters to even integers and 13 characters to odd integers; there are $\binom{26}{13} = 10,400,600$ possibilities. So, what we (actually, a computer, this is a bit much for hand computation) can do is scan through all 10 million possibilities (and through the reasonable values of $n$, if we don't know that), and check if that mapping to even/odd characters is consistent with the known plaintext/ciphertext.

The result of this will be the lsbits of the mapping (which are the 13 even characters, and which are the odd characters), the lsbits of the elements of $K$, and the value of $n$.

The next obvious thing to attack, if we have enough plaintext, is to recover the mapping of the even characters. There are $13! = 6,227,020,800$ such possible mappings; if we can find (say) $n+1$ blocks that consist of only even characters (and both the plaintext and the ciphertext blocks will consist of even characters; we know this because the mapping is consistent $\bmod \ 2$), then we can scan through the 13! possible mappings, and see if each such mapping is consistent with all $n+1$ plaintext/ciphertext pairs. If $n=5$, then we expect to be able to find 6 such blocks if we have at least 1200 characters of known plaintext; not unreasonable.

Once we have that, that gives us the value of $K$, and the mapping for the even characters. With that, deducing the mapping of the odd characters is straight-forward.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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