4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Normally I'd say (when using the distribution-variable based definition): Use redundancies in the ciphertext to make certain plaintexts more likely, quantify that and there you have it, but this one seems harder than that (+1). $\endgroup$ – SEJPM Mar 28 '17 at 16:27
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Thanks for the great detailed answer. I'm just wondering: isn't the H(plaintext) = 2n/k * log(k)? The probability of every letter is 1/k, so we would have 2n * 1/k * log(k), no? Not exactly sure what I am missing here...For the rest, I'm definitely getting a feeling of how I should do this, so thanks a lot. $\endgroup$ – el-flor Mar 28 '17 at 20:02
  • $\begingroup$ The uniform distribution over an alphabet of $k$ letters (represented by the numbers from 1 to $k$) has an entropy of $-\sum_{i=1}^k p_i \log p_i = -\sum_{i=1}^k \frac1k \log \frac1k = -\log \frac1k = \log k$. It looks like you forgot to account for the factor of $k$ that comes from summing over all the possible letters. The uniform distribution over $n$-letter strings over the same alphabet just has $n$ times as much entropy (since it's just a product distribution of $n$ independent uniform distributions over the same alphabet). $\endgroup$ – Ilmari Karonen Mar 28 '17 at 20:10
  • $\begingroup$ Of course, my bad, stupid mistake. Thanks for the great explanations. I'll just check for the best way to explain it all and accept your answer! $\endgroup$ – el-flor Mar 28 '17 at 20:15
3
$\begingroup$

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$?

$\endgroup$

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.