# How to solve cipher encrypted with Vigenère + Columnar Transposition?

Vigenère's weakness is Kasiski's test and index of coincidence. However, if you put columnar transposition on top of Vigenère, that weakness is gone. The text is now shuffled and you can't search for digrams/trigrams, because they will give you wrong key length pattern.

You also can't solve Columnar Transposition. For example, you try key length $i$ and you put the text in $i$ columns. Normal Columnar Transposition is solved by matching columns with each other and counting how good the match is (compared to English text digrams). The best match is then the correct column order. But because the text is encrypted with Vigenère and letters are substituted, you won't get correct result.

Is such a cipher considered very good / unbreakable or how does one attack it?

Obviously such a combination of ciphers is stronger than any of these two ciphers alone.

The Vigenere cipher provides "confusion", while the transposition cipher provides "diffusion". These are terms used by C. Shannon, refer to http://en.wikipedia.org/wiki/Confusion_and_diffusion.

Modern ciphers like AES are making use of diffusion and confusion as well. But - besides additional other operations - here several rounds are applied.

I think applying these two encryption methods (vigenere & transposition) to a plain text only once will still be a rather weak encryption (at least compared to AES).

In the following I provide some of my thoughts. I haven't verified them, so I cannot guarantee that everything described below works as expected. :-)

Some thoughts of how to attack such an encryption: Evolutionary algorithms (http://en.wikipedia.org/wiki/Evolutionary_algorithm) are one way to break transposition ciphers (btw, EAs can be used to break Vigenere ciphers as well). One variant of such an algorithm is called genetic algorithm (http://en.wikipedia.org/wiki/Genetic_algorithm). Investigations in this area have been done, e.g. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113.4358&rep=rep1&type=pdf.

One main function within a genetic algorithm (GA) is called fitness function. Once a key has been chosen the given cipher text is decrypted using this key and the resulting clear text is passed to the fitness function (http://en.wikipedia.org/wiki/Fitness_function). The fitness function returns a measure how close the result comes to an optimum solution.

In case simple transposition ciphers are to be solved the fitness function determines how close the clear text comes to the English language.

Now if a clear text is encrypted by the Vigenere cipher, and the resulting Vigenere cipher text is encrypted using the transposition cipher then the resulting cipher text can be attacked by treating it as a "simple" transposition cipher. The difference is now that the fitness function must return a measure how probable it is that the resulting clear text is a Vigenere cipher.

Vigenere ciphers have certain characteristics, e.g. an autocorrelation will show periodic maxima (http://www.cryptool-online.org/index.php?option=com_content&view=article&id=90&Itemid=107&lang=en). Thus it should not be a problem writing a fitness function which distinguishes a Vigenere cipher from a random sequence of characters.

Once the transposition cipher is solved solving the Vigenere cipher is rather straight forward.

Implementing a fitness function checking for the Vigenere cipher will probably be slower than a corresponding function checking for English text. Thus I expect that breaking the cipher "Vigenere & transposition" will require much more processing time than breaking any of these ciphers alone.

There is still an open question: How to find the key length for the transposition cipher? One possible way might be to apply an autocorrelation to the cipher text. I would expect to see maxima at multiples of the least common multiple of the Vigenere key length and the transposition key length. This should at least limit the potential key lengths to try.