Prove Vigenere cipher isn't perfectly secret

Question

As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed in the alphabet, is perfectly secret.

The only theorem we have seen so far concerning perfect secrecy uses entropy: if the plain text and the cipher text are statistically independent (H(PlainText) = H(PlainText | Ciphertext)), the encryption is perfectly secret. Computing H(PlainText) is quite straightforward given the text is uniformly distributed on an alphabet of 26 elements.

But I don't know how to compute the conditional entropy of the plain text given the ciphertext to prove that these two aren't equal (I understand that this type of encryption isn't perfectly secret, mainly because the key is of length n and not 2n).

What is the way to approach this?

Answer 1

Given the ciphertext and the first $n$ characters of the plaintext, you can uniquely determine the remainder of the plaintext. Thus, for each ciphertext, there are only $k^n$ possible plaintexts (where $k = 26$ is the size of the alphabet).

In particular, this implies that if you have no prior knowledge of the plaintext, so that each of the $k^{2n}$ possible plaintexts is equally likely a priori, then: $${\rm H}(\text{plaintext}) = 2n \log k \ne n \log k = {\rm H}(\text{plaintext} \mid \text{ciphertext}).$$

For your assignment, you might want to work that out explicitly, using Bayes' theorem and the definition of conditional entropy. This would also allow you to derive the more general result for non-uniform priors, and to show that the entropies are only equal for some very special prior plaintext distributions (specifically, those for which the second half of the plaintext is always a Vigenère encryption of the first half using some fixed key). But all you really need to disprove the perfect secrecy of the Vigenère cipher is to show that it's not perfectly secret for some prior plaintext distribution (e.g. the uniform one), for which all you need is the formula for the entropy of the uniform distribution and the observation that the restriction of the uniform distribution to some subset of its support is still uniform, just with fewer choices.

Or, perhaps even simpler, you could just consider the case where you already know in advance that the plaintext is either "AAA...AAA" or "AAA...AAB", and show that the prior entropy in this case is 1 bit (assuming that each of these plaintexts is equally likely a priori), whereas the conditional plaintext distribution has 0 bits of entropy (since comparing the two halves of the ciphertext is enough to uniquely determine the plaintext).

Answer 2

One way to approach this is to look at the decryption process; the plaintext is a function of the ciphertext and the key. The conditional probability says you know the ciphertext (entropy 0), you don't know the key (entropy $n \log_2 26$); what's the entropy of the decrypted plaintext (which is a function of those two)? How does that compare to the entropy of an arbitrary plaintext of length $2n$?