# When does a multiple Vignere cipher become intractable?

Multiple Vignere 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?

• What's a multiple vignere cipher? Just multiple Vigenère encryptions with different keys? If yes, you would attack that the same as normal Vigenère ciphers, see here: crypto.stackexchange.com/questions/19353/… – Nova May 6 '18 at 18:24
• I saw that. A bit of background. I am looking for a system that one could memorize. So really long keys are out. Multiple vignere generates a long key from a set of short ones. Yes, to use this system one would generate a long enough key and then use that, I would describe that as an implementation detail. – Jim Rootham May 7 '18 at 13:59
• For shorter keys, a dedicated person, could do something since this is not one-timepad. – kelalaka Oct 19 '18 at 7:26

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.

• @IImari Karonen Concerning "...and that the key is fully random, independent of the other keys and..." If that key is fully random, then it must be independent of the other keys, right? Or did I miss something? – Patriot Aug 15 '19 at 2:50
• @Patriot: In mathematics, random does not necessarily imply independent. For example, if one key was chosen uniformly at random from the set of possible keys of length $\ell > 1$, and another was constructed by, say, taking the first key and reversing the order of its characters, then either key alone would be perfectly random (in the sense of being uniformly distributed over the keyspace, and thus having the maximum possible entropy), but their combination clearly wouldn't be. Thus, where independence is required, it's worth being explicit about it to avoid any ambiguity. – Ilmari Karonen Aug 15 '19 at 21:14

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.

• An argument/demonstration as to why this is the case instead of a simple assertion would make for a better answer. – Ella Rose Sep 19 '18 at 1:55
• Okay, I edited my answer according to your recommendation. – Meler Lawler Sep 19 '18 at 3:16
• Or, Vigenère with a key longer than the message is just a one-time pad... – fkraiem Sep 19 '18 at 4:23
• Technically, that is not the only requirement. The key must be be truly random. It is not in this case; it is composed of subkeys superimposed upon each other at different offsets. – Meler Lawler Sep 19 '18 at 4:26
• As Nova and others stated, here the multiple encryption simply a single encryption with a longer key. So we simply have a Vignere with longer key, As a result, we only need longer ciphertext. – kelalaka Sep 19 '18 at 16:58