Vigenère cipher

Question

I am attending a cryptography course on Coursera. I am stuck at one question which I cannot answer right, even after a few tries.

Which of the following are true about Vigenère cipher? (Check all that apply)

1. A Vigenère cipher with key of length 100 can be broken (in a reasonable amount of time) using exhaustive search of the key space.
2. The Vigenère cipher can always be broken, regardless of the length of the key and regardless of the length of plaintext being encrypted
3. The Vigenère cipher is computationally infeasible to break if the key has length 100, even if 1000s of characters of plaintext are encrypted.
4. The Vigenère cipher is perfectly secret if the length of the key is equal to the length of the messages in the message space.

I am not sure about answer nr. 1--whether it can be broken in a reasonable amount of time. Non-computationally? For sure not.

I think the second answer is also wrong, as by definition. If the key and message are the same length, it is perfectly secret. (well the key has to be randomly chosen...)

Third answer is also wrong since the key repeats.

The fourth one is true as I mentioned for the second one.

I am not sure what possibilities I have tried, but I cannot pass this one.

Answer 1

Let's consider claim 1 first. If the ciphertext alphabet has, say, 26 letters, then a Vigenère cipher with a 100-character key length has $26^{100}$ possible keys. You may wish to do your own back-of-the envelope calculation of how long it would take to exhaustively search that keyspace, assuming e.g. that you have access to a billion computers that can each test a billion keys per second. Or just let Google do it for you.

As you've correctly noted, a Vigenère cipher provides perfect secrecy if the keys is (at least) as long as the message, perfectly random and never used more than once. This implies that claim 2 is false. It also almost implies that claim 4 is true, except for those pesky details about the key having to be random and used only once.

As for claim 3, you should have learned during the course how to break a Vigenère cipher one key letter at a time, given enough ciphertext and some mild assumptions about the character frequency distribution of the plaintext. Or, easier yet, having access to at least one key length of known plaintext and corresponding ciphertext will obviously reveal the full key.