Cryptanalysis of the Columnar Transposition Cipher
For a recap of how the columnar transposition cipher works, see here.
This page deals with automated cracking of columnar transposition ciphers with no known crib. The only thing we know about the plaintext is that it is English. For cracking these ciphers by hand or with a crib, different techniques can be used. The book by Helen Fouche Gains "Cryptanalysis - a study of ciphers and their solution" and the book by Sinkov "Elementary Cryptanalysis" both describe at great length how to break columnar transposition ciphers by hand.
The columnar transposition is a suprisingly secure cipher when long keys are used (key words around length 20), but much weaker if shorter keywords are used. In addition, if we know the keyword length most of our work is done. If we have a columnar transposition cipher, and we don't know the keyword length, there are several things we can try.
For the approaches described below, we need a way of determining how similar a piece of text is to english text. This is called rating the 'fitness' of the text. A piece of text very similar to english will get a high score (a high fitness), while a jumble of random characters will get a low score (a low fitness). For this we will use a fitness measure based on quadgram statistics. This method works by first determining the statistics of English text, then calculating the likelyhood that the ciphertext comes from the same distribution. An incorrectly deciphered (i.e. using the wrong key) message will probably contain sequences e.g. 'QKPC' which are very rare in normal english. In this way we can rank different decryption keys, the decryption key we want is the one that produces deciphered text with the fewest rare sequences.
Enumerate all Short Keywords §
The first step in attacking a columnar transposition cipher is to try all possible short keywords. If we check all keywords up to a length of 9 or so, we don't have to wait very long. For every keyword permutation we score the deciphered text, then choose the text with the highest score as our best candidate. The number of possible rearrangements of a length N key is N! (N factorial). This number grows very quickly as N gets larger. The number of possible keys for various length keywords is shown below:
| Key Length | No. of permutations | Examples |
|---|---|---|
| 2 | 2 | AB, BA |
| 3 | 6 | ABC, BAC, CBA, ... |
| 4 | 24 | ABCD, ABDC, ACBD, ... |
| 5 | 120 | ABCDE, ABCED, ... |
| 6 | 720 | ABCDEF, ABDCFE, ... |
| 7 | 5,040 | ABCDEFG, ABDCGEF, ... |
| 8 | 40,320 | ABCDEFGH, ... |
| 9 | 362,880 | ABCDEFGHI, ... |
| 10 | 3,628,800 | ABCDEFGHIJ, ... |
| 11 | 39,916,800 | ABCDEFGHIJK, ... |
| 12 | 479,001,600 | ABCDEFGHIJKL, ... |
Trying to test all possible combinations of a length 6 keyword is easy, 720 trial decryptions can be done very quickly. However, we have little hope of trying to enumerate all possible length 12 keywords, as it would take far too long. This is why we stop at around length 9 keywords.
If this stage fails to decrypt the ciphertext, there are two possibilities: the actual key is longer than 9, or the key is shorter than 9 but the plaintext contains many strange quadgrams, which leads us to discount it as a possibility due to its low score. This can be overcome by ensuring the pre-generated quadgram statistics come from text as similar as possible to the ciphers we are breaking.
Dictionary Attacks §
If the first step failed, we now move on to the second. The columnar transposition cipher is almost always keyed with a word or short phrase, so we may not need to test all possible transposition keys, we may only need to test common words. This involves having a large list of dictionary words including place names, famous people, mythological names, historical names etc. From this we generate a text file of possible keys. We only need consider words longer than length 9, since we tested all the shorter words in step 1. We then try to decrypt the ciphertext with all possible dictionary words and record the keyword that resulted in plaintext with the highest quadgram fitness. Having 1,000,000 dictionary words would be a good comprehensive target.
This step can work if the keyword was one of the words that you included in the dictionary, but it fails to work if the keyword is something like 'THEBLOOMSINSEPTEMBER'. We can't hope to include all possible short phrases in our dictionary, as there are simply far too many of them. If this step fails, we must move on to step 3.
Hill Climbing §
The hill climbing approach we use here is almost identical to that used to break substitution ciphers. We first assume the key length is 10, then choose a random starting keyword of this length. This is called the parent key. Child keys are generated by making random swaps in the parent keyword, and if any of the swaps lead to an increased fitness we replace the parent with the child that beat it. In addition to randomly swapping two elements, we also try rotating the key e.g. 'ABCDEFG' -> 'BCDEFGA', or cutting the key at a random point and swapping the ends e.g. 'ABCDEFG' -> 'EFGABCD'. This allows us to better search the keyspace.
This algorithm will very rarely get the correct answer on the first run, typically you would have to run it several hundred times, each time starting with a different random key, to be sure to get the correct decryption. If after many tries the correct key is not found, it is time to increment the key length to 11 and rerun everything. This must be performed for key lengths from 10,11,...,20. Keys of length 20 are very difficult to crack, and it gets much more difficult to crack keys as they become longer than 20.
This sort of cracking can take all night to complete, but if you really have to crack something you just have to take the time to do it. For long keys, length 20 and up, a simulated annealing algorithm would probably be a better choice and may reduce the number of iterations you need to perform to crack a cipher. But this introduces more variables: the starting temperature, the temperature step, and the number of iterations per step. These variables would also have to change for each different key length, which increases the complexity of use.
comments powered by Disqus