Take the 2-minute tour ×
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 am going to apply a simple substitution cipher to my input, then encrypt the result with a Hill cipher. How can this be broken, in a chosen-plaintext threat model?

In other words, instead of the standard mapping of letters to numbers (A=0, B=1, .., Z=25), I will randomly reorder them (e.g., A=22, B=12, ...), where the particular bijection between letters and numbers is part of the key. Then, I'll encrypt the result using a Hill cipher. So far I've been using a Hill cipher with a $2\times 2$ matrix, but I'd also be interested in the answer for a general $n \times n$ matrix.

share|improve this question
1  
user9, Please do not deface your question! This site is intended to be a question-and-answer site for the common good. In particular, when you post here, you accept that the community has some ownership of your question; you are not a sole owner. If you deface your question, you render it useless to others -- which is inappropriate, as the main purpose of this site is to be useful to the world, not just to you. It is considered inappropriate to deface or delete your own question after you received an answer. See, e.g., meta.stackexchange.com/q/106807/160917 –  D.W. May 22 '13 at 4:36
add comment

1 Answer 1

up vote 3 down vote accepted

This can be broken. The exact nature of the attack will depend what modulus you use for the Hill cipher: are you working modulo a prime number, or working modulo 26?

Working modulo a prime $p$

A simple attack, with no fancy mathematics needed. One simple attack is to start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ.

Note that after simple substitution, the message AAAA will become the 4-vector $(a,a,a,a)$ for some number $a$, and then we'll encrypt this by multiplying the vector $(a,a,a,a)$ with a matrix that is the Hill cipher's secret key. Similarly, the message BBBB will become $(b,b,b,b)$ and then will get multiplied by the same matrix. Since every number has an inverse modulo $p$, there's some constant $c$ such that $b=a \times c \pmod p$ (namely, $c = b a^{-1} \pmod p$). This means that $(b,b,b,b)$ is a constant $c$ times the vector $(a,a,a,a)$. Consequently, the Hill-cipher-encryption of $(b,b,b,b)$ will be a constant $c$ times the Hill-cipher-encryption of the vector $(a,a,a,a)$.

Guess what number A maps to; say A maps to the number $a$. Then each other ciphertext will be a constant multiple of the ciphertext for AAAA, and that constant will reveal what the corresponding letter maps to. For instance, suppose each number in the ciphertext for BBBB is 9 times the corresponding number in the ciphertext for AAAA; then we know that B maps to $9a \pmod p$. (In general, it is guaranteed that there will always be some constant we can substitute in place of 9.) Thus, if we guess correctly what number A maps to, then we will learn what number each other letter maps to.

Now apply a standard attack for defeating the Hill cipher. You'll repeat this $p$ times, once per guess at the number that A maps to. You can confirm whether the guess was right, by confirming whether you have successfully broken the Hill cipher and can decrypt the ciphertexts to meaningful-looking plaintext. One of your 26 guesses will lead to correct-looking plaintext; that's the right guess, and now you're done.

Working modulo 26

A simple attack, with no fancy mathematics needed. We can generalize the above attack so that it also works if we're working modulo 26. Now we have to deal with the fact that not all numbers have an inverse modulo 26.

As before, we start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ. One of those will encrypt to the all-zeros ciphertext; say it is the message QQQQ. Then you have learned that Q maps to 0.

Another of those ciphertexts will contain only the numbers 0 and 13; say it is the message DDDD that encrypted to this. Then you have learned that D maps to 13.

Now you can apply a similar attack, by guessing which number A maps to, and then applying similar reasoning.

A fancier attack

There's a more sophisticated way you can attack this, by using some fancier mathematics. Introduce 26 unknowns $x_A, x_B, \dots,x_Z$. Here $x_A$ represents the number that A maps to, $x_B$ represents the number that B maps to, etc. We don't know a priori what these numbers are; that's why they are unknowns (variables).

Also, let the $n\times n$ matrix $M$ denote the Hill cipher matrix used for encrypting $n$-letter messages. We can think of each of the $n^2$ entries of $M$ as another unknown; i.e., $M_{i,j}$ is an unknown, for each $i,j$.

Now each known plaintext-ciphertext pair gives us a system of equations on these unknowns. For instance, suppose the message WINK encrypts to the ciphertext $(17,5,20,2)$. Then we learn the following equation:

$$M (x_W, x_I, x_N, x_K) = (17,5,20,2).$$

Why? Because after simple substitution, WINK becomes the column vector $(x_W, x_I, x_N, x_K)$. The Hill-cipher-encipherment then multiplies this by the matrix $M$. We know what the resulting ciphertext is.

Notice that this is a system of $n$ equations in $n^2+26$ unknowns. Sadly, they are not linear equations; they are quadratic equations. Nonetheless, there are techniques known for solving a system of quadratic equations. We can expect that once we obtain a bit more than $n^2+26$ equations in $n^2+26$, there will be a unique solution. There are techniques (e.g., relinearization) for computing this unique solution, when the number of equations is large enough. For instance, if we have at least $(n^2+26)^2$ quadratic equations in $n^2+26$ unknowns, simple relinearization will find us the value of all of those unknowns using $O(n^{12})$ time. This number of equations can be gathered after observing $(n^2+26)^2/n$ known plaintext-ciphertext pairs.

Getting even fancier

Hey, why stop there? We can actually solve this purely with linear algebra.

Notice that we can rewrite the previous equation as

$$(x_W, x_I, x_N, x_K) = M^{-1} (17,5,20,2).$$

So now let's choose a slightly different set of unknowns: the unknowns are $x_A, x_B, \dots,x_Z$ (this part is the same as before) and the entries of $M^{-1}$, i.e., $(M^{-1})_{i,j}$ for each $i,j$ (this part is different). There are still $n^2+26$ unknowns.

With this change, each known plaintext-ciphertext pair gives us $n$ linear equations in $n^2+26$ unknowns. Now the equations are linear, so they are even easier to solve. Once we've obtained a bit more than $n^2+26$ equations, there should be a unique solution, and it can be found using Gaussian elimination in $O(n^6)$ time. So, if we can gather a bit over $(n^2+26)/n$ known plaintext-ciphertext pairs, we can break the cipher using linear algebra. Cool, eh?

share|improve this answer
add comment

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.