Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Multiple Vigenère ciphers do not repeat the key until the message gets longer than the LCM of the cipher lengths. Are messages shorter than that safe? If not, what is the attack strategy?
I believe there is a known plaintext attack which has an algebraic solution if the message is longer than the sum of the cipher lengths. Are messages shorter than that safe?
Are messages shorter than the longest key in the set of ciphers safe?
Yes, if you know the key lengths and have a sufficient amount of known plaintext, you can easily recover the keys (or at least something equivalent to them) using linear algebra.
How much is "a sufficient amount"? Well, to fully recover all the key characters, you would need to solve as many linear equations as there are characters in all the keys combined, and would thus need at least that many ciphertext/plaintext character pairs to get a unique solution.
However, in general, some of those equations will be redundant, because multiple Vigenère encryption has equivalent key(set)s. This implies that a) you cannot, in general, fully recover the original keys, but b) you can generally recover an equivalent set of keys with less known plaintext than the combined length of all the keys.
The exact amount of redundancy will depend on the key lengths. As an extreme example, encrypting a message with two keys of length $a$ and $b$, where $a$ is an integer multiple of $a$, is obviously equivalent to encrypting it with a single key of length $a$.
More generally, adding a constant to all characters of one key and subtracting the same constant from all characters of another key obviously won't change the result of the encryption. By choosing suitable constants, we can transform any set of keys to an equivalent one where (e.g.) the first character of each key except one is zero. So, in general, a set of $n$ keys with total length $\ell$ can have at most $\ell - n + 1$ non-redundant characters, and thus finding an equivalent keyset requires at most that many known plaintext characters.
(Of course, that's assuming that each ciphertext/plaintext character pair actually contributes to the solution. Depending on where the known pairs are located in the message, this may not always be the case, either. For example, trivially, two ciphertext/plaintext character pairs separated by a distance that is divisible by the least common multiple of the key lengths will be encrypted with the same key characters, and thus knowing them both won't provide any more information about the key than just knowing one of them. On the other hand, I would conjecture — but cannot prove off the top of my head — that a sequence of $\ell - n + 1$ consecutive ciphertext/plaintext character pairs should always be sufficient to find an equivalent keyset.)
If all the key lengths are coprime, I believe $\ell - n + 1$ ciphertext/plaintext character pairs is also the minimum number needed to fully determine the key set (up to equivalency). Otherwise, fewer should be sufficient.
Also, yes, if the message is no longer than the longest key, and that key is fully random, independent of the other keys and used only for one message, then the system is equivalent to a one-time pad, and thus provides perfect secrecy.
Essentially, this is because just encrypting the message with that one key is sufficient to provide perfect secrecy, and anything else we do with the message cannot compromise that.
In fact, since Vigenère encryptions commute with each other, we can always arrange them so that the encryption with the long random one-time key happens last. Thus, we can treat the result of all the other encryptions as the plaintext input to a one-time pad scheme, which of course perfectly conceals its input. Thus, nothing about any of the other keys matters in any way, as long as at least one of the keys satisfies the criteria (randomness, independence, length, non-reuse) for being a secure one-time pad.
Nova is wrong. You cannot attack the cipher you describe with traditional Vigenere attacks. There is no known (practical) attack on your cipher (trust me, I've looked everywhere).
EDIT: It was recommended that I explain why this is true. Well the traditional attacks rely on comparing portions of ciphertext separated by a distance equal to the length of the key. Obviously this cannot be done if the key is longer than the message.
