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 on cryptography course and there is a homework question to show that Hill cipher doesn't have perfect security.

So assume we have an cryptosystem $(P,C,K)$, where $P = C = \mathbb Z_{26}^N$ and $K$ is the set of invertible $N \times N$-matrices modulo $26$. Now we also have some probability distribution on $P$ and also some distribution on $K$.

A cryptosystem has perfect secrecy if $p(x) = p(x|y), \forall x\in P \wedge y\in C.$

Now, one option I considered is that according to Bayes rule, if system has perfect secrecy, the cardinalities of these sets $P,C,K$ must fulfill $|K| \ge |C| \ge |P|$. But this seems to be the case, so I can't use that.

The $p(x)$ is whatever the original distribution says it is. Now $p(x|y)$ cannot be the same as $p(x)$ for this homework to make sense. $$p(x|y) = \frac{p(y|x) p(x)}{p(y)}$$ $p(y) = \sum p(k) p(d_k(y))$, so probability that key used was $k \in K$ times the probability of decrypted message being $d_k(y)$. I would think $p(d_k(y))$ is same as $p(x)$, as $x$ is $y$ encrypted and as we sum over all the keys, for any key there is some $y \in C$ which maps back to a given $x \in P$, this is same as $p(x).$

Thus $p(x|y) = p(y|x)$. I would think that as we know $x$, and every key maps every plaintext to different cryptotext, they would have same distribution, so $p(x|y) = p(y|x) = p(x)$.

So we have perfect secrecy.

Now, what am I not getting here? I am sure I do something wrong, but help would be welcome.

share|improve this question
    
Hint: Hill cipher, unknown letter value –  e-sushi Feb 4 at 19:24
add comment

1 Answer

up vote 3 down vote accepted

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large....

Another possibility you might be missing is the consequences of the fact that you are working modulo $26$. I think you need to calculate out $p(y|x)$ carefully. You might start by considering what happens when $N=1$. Can you calculate the value of $p(y|x)$ and $p(x|y)$, for all possible values of $x,y$? Maybe write a program to do it, or do the case analysis so you don't have to consider $26\times 26$ cases exhaustively. I think you'll find that is enough to let you figure out what's going on.

I don't want to say more, because this is an exercise, and should solve your own exercise.

share|improve this answer
    
Well, I did some calculations. If we have plaintext {0,0,0...}, then no matter what key we use, the cryptotext is also {0,0,0...}. So p(0,0,0...) = 1/something, but p(0,0,0...|y) = 0 or 1, depending on the y... So they are not same. Am I correct? –  Valtteri Feb 4 at 21:13
    
@Valtteri, well done! –  D.W. Feb 4 at 22:34
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.