6
$\begingroup$

Please forgive my ignorance here as I'm far from a math major and I've never looked into cryptography before so if this seems stupid - it probably is. There is a question in a quiz I'm attempting that is just doing my head in. If you are wondering - I'm not doing this course for credit or receiving any certification for passing it, just for my own interest.

I've attempted this question multiple times now and I'm still getting it wrong and I don't understand why. Here is the question:

Consider the Vigenere cipher over the lowercase English alphabet, where the key has length 6. For which of the following message spaces will this scheme be perfectly secret? (Check all that apply.)

  1. The set of all 7-character strings of lowercase English letters.
  2. The set of all strings of lowercase English letters containing at most 6 characters.
  3. The set of all 6-character strings of lowercase English letters.
  4. The set of all 5-character strings of lowercase English letters.

I know I'm getting punished by the combinations that are available due to the 'check all that apply' criteria, but I'm now at the point of blind guessing - which just isn't learning.

I'm particularly annoyed with this because further down in the same quiz the following is considered to be a correct answer for an aspect of another question:

'The Vigenere cipher is perfectly secret if the length of the key is equal to the length of the messages in the message space.'

To me then, it seems that the answer would be: 2 and 3 and 4 - Wrong

Perhaps this is wrong because 'the key' is only as long as one individual member of 'the strings' in the message space, not the length of 'all the messages in the message' space combined? (i.e. which would effectively be turning it into a One Time Pad where the key is the same length as the total message space?)

How should I go about breaking down this question to arrive at the answer with some sort of mathematical reasoning, rather than taking blind shots at it (which is where I'm at now)?

Description of the Vigenere Cipher

Now when we introduced the Vigenère cipher, we presented it in the following way. We said that the key was a string of letters. From the English alphabet and the plaintext will also consist of letters from the English alphabet. To encrypt a given plaintext with a key, what you do is simply shift every character in the plaintext by the amount dictated by the next character of the key. You can view this simple as addition modular 26, because there are 26 letters in the English alphabet. And if the key is shorter then the plaintext you simply wrap around in the key as needed, and decryption just reverses the process.

$\endgroup$
  • 1
    $\begingroup$ How do you define the Vigenère cipher? In particular, when the key is longer than the message. $\endgroup$ – fkraiem Jun 20 '16 at 10:58
  • 1
    $\begingroup$ So, my second answer was just 2 and 3. That was also wrong. Then I thought it was a trick in the wording that I was missing so I answered with 2 alone, and then with 3 alone. Both wrong as well. $\endgroup$ – Chris Jun 20 '16 at 11:06
  • 2
    $\begingroup$ I would say that under reasonable definitions of the Vigenère cipher and of the notion of perfect secrecy, the correct answers should be 2, 3, and 4. Hence why I asked what definitions you are working under. $\endgroup$ – fkraiem Jun 20 '16 at 11:23
  • $\begingroup$ Yep, unfortunately that is all the information provided in the question, there is no further context. $\endgroup$ – Chris Jun 20 '16 at 11:29
  • $\begingroup$ Probably the definitions are somewhere in your class material. (Otherwise, I don't think it's a very good course.) $\endgroup$ – fkraiem Jun 20 '16 at 11:30
5
$\begingroup$

As far as I can tell, your original reasoning is correct. To obtain perfect secrecy with a Vigenère cipher, the key must not repeat. The key does not repeat whenever it is at least as long as the message, so option 2 is clearly a sufficient (and indeed necessary) condition for perfect secrecy, at least as far as only key length is considered. Options 3 and 4 are subsets of option 2, so if choice 2 is correct, then they must be correct as well. Thus, the correct answer (unless this is a trick question) should be (2, 3, 4).

Note, however, that there are conditions on the perfect secrecy of a Vigenère cipher other than key length. In particular, to obtain perfect secrecy with a Vigenère cipher:

  1. the key must be at least as long as the message,
  2. each of the key letters must be selected independently and uniformly at random from the entire ciphertext alphabet, and
  3. the same key must not be used for more than one message.

The options in the question you quote make no mention of the second and third conditions, so arguably, none of them is sufficient to guarantee perfect secrecy. While I would consider this to be a rather nasty trick to play on the test-taker (especially given that such an argument would seem to contradict the "correct" answer to the other question you quote), technically this would be a valid answer (and arguably the valid answer) to the question.


Ps. One possible interpretation, which just occurred to me, is that your course might be using a definition of perfect secrecy which is violated if the length of the message is revealed to the attacker (and is not the same for all valid messages). This is actually a reasonable definition to adopt: if the attacker knows in advance e.g. that your message is either yes or no, then simply learning the length of the message will tell them which one it is.

Since Vigenère encryption does reveal the message length, this would rule out option 2, leaving only options 3 and 4 (where revealing the message length gives no information to the attacker, since all valid messages have the same length) as correct answers.

$\endgroup$
  • 1
    $\begingroup$ Thank you for the detailed response. Based on your original answer, it would seem to me that under those conditions, the Vigenere cipher is essentially just a Vernam cipher (i.e. a one time pad), which does ensure perfect secrecy. Is that an accurate conclusion? I did also try the answer of 'nothing applies', that was also considered wrong. Your postscript suggestion is a good one, that hadn't occurred to me. Thanks. $\endgroup$ – Chris Jun 20 '16 at 11:49
  • 1
    $\begingroup$ You sir, are correct, option 3 and 4 it was. It hadn't occurred to me at all that it was leaking information about the message length until you mentioned it - which seems rather stupid of me in hindsight, but live and learn! $\endgroup$ – Chris Jun 20 '16 at 11:55
  • $\begingroup$ @ilmari, wanted to make sure you saw this answer. $\endgroup$ – mikeazo Aug 26 '16 at 13:45
  • 1
    $\begingroup$ The question looks like something from one of the crypto courses in Coursera, and isn't unlike the other quizzes on the course. It was actually explained in the course material, and the argument went something like this: for perfect secrecy, seeing the ciphertext shouldn't provide any additional information about the plaintext to an attacker. Or, that the attacker must not gain new knowledge of the probabilities of any plaintexts after seeing the ciphertext. Leaking the length violates this, as you noted. $\endgroup$ – ilkkachu Aug 26 '16 at 14:39
  • $\begingroup$ @ilkkachu, I'm curious if the course went over one-time pad and how they got around the issue with it. $\endgroup$ – mikeazo Aug 26 '16 at 15:18
4
$\begingroup$

2 can't be correct and it's not a trick, message space should be equal or smaller than key space, in 2 message space is much larger, its : $\sum_{i=1}^{6} 26^{i}$

$\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.