2
$\begingroup$

In polyalphabetic substitution cipher, if we have a key $k$ (a string of letters) of length $n$ does the plaintext $m$ (also a string of letters) have to satisfy $|m| \geq n$?

Also, side question, do we have to include a requirement that at least one letter in the key is different from the others? Because otherwise it becomes a simple shift cipher (Not poly at all)

Improve this question
$\endgroup$
4
  • $\begingroup$ Why should it have to? $\endgroup$
    – yyyyyyy
    May 15, 2015 at 10:44
  • $\begingroup$ I'm not sure, does it not matter at all? Reading about more advanced topics like Shannon's theorem for perfect secrecy where they focused a lot on key length got me thinking. Is it not a factor for simple ciphers such as this? Also, side question, do we have to include a requirement that at least one letter in the key is different from the others? Because otherwise it becomes a simple shift cipher (Not poly at all) $\endgroup$
    – Gordon
    May 15, 2015 at 10:53
  • $\begingroup$ Well, there's two things to talk about: correctness and security. Correctness, i.e. decryption is the inverse of encryption, is easy (for all the cases you mentioned, including $\lvert k\rvert>\lvert m\rvert$). Security is also easy for Vigenère ciphers since they are broken using statistical analysis. In fact, the only case in which such a system may be secure, depending on the choice of key, is when $\lvert k\rvert\geq\lvert m\rvert$. Using a "weak key" does not impact correctness, but decreases the security of the system even more. $\endgroup$
    – yyyyyyy
    May 15, 2015 at 11:37
  • $\begingroup$ Vigenère with a key as long as the plaintext is just a one-time pad. $\endgroup$
    – fkraiem
    May 15, 2015 at 12:28

1 Answer 1

Reset to default
2
$\begingroup$

I'm not aware of any classical polyalphabetic ciphers where the key could not be longer than the message.

For the Vigenère cipher, the key is, effectively, repeated to make it as long as the message. There is no reason why it could not be repeated less than once, effectively discarding the unnecessary characters at the end of the key.

Similarly, in the autokey cipher, the key is dynamically extended by appending either the plaintext or the ciphertext message to it, ensuring that the extended key never runs out of characters. If the message is no longer than the key, however, this extension is never needed, and the autokey cipher behaves exactly like the Vigenère cipher.

In fact, if the key for the Vigenère or autokey cipher is:

  1. at least as long as the message,
  2. composed of purely random characters, and
  3. never used to encrypt more than one message,

then the cipher becomes an unconditionally secure one-time pad. This is the most secure kind of cipher, being provably impossible to decrypt without knowledge of the key. Alas, the strict requirements on the key — not the least being that it needs to be at least as long as the message being encrypted — make it rather impractical for most purposes.

As for your side question, obviously, if you deliberately choose only keys that consist of a single repeated character, then a Vigenère cipher becomes just a simple shift cipher. However, if you're using a one-time pad with random keys, there is a (very small) probability that all the random characters will be the same, and that's perfectly fine.

In fact, if you threw out such keys, your key selection process would no longer be perfectly random, and so an attacker could potentially learn some information about the plaintext just by inspecting the ciphertext and knowing that the key cannot be one that has all its characters identical.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.