## Transposition Ciphers

What is it?  A transposition cipher is one that rearranges the ordering of letters in a message according to some specified transposition algorithm. Transposition ciphers can be very difficult to decode when they implement obscure algorithms and they are extremely difficult to decrypt by hand unless the algorithm is known. This category of ciphers tends to be less well-known by cryptographers simply because of how complicated the algorithms can become. Following are examples of more commonly used algorithms:

Reversing a message is the simplest transposition algorithm, but it is often overlooked. Always consider that the message might have been reversed. Often, transposition ciphers involve multi-step algorithms in which reversal is the final step. Even consider that a substitution cipher may have been reversed to add an extra layer of security.

The simple horizontal transposition cipher is also sometimes referred to as anagramming. The key is a permutation of some length L. To encrypt, a message is split into L-grams and the permutation is applied to each L-gram. Then, the permuted L-grams are spliced together:

Ex. P = ABCDEF, permutation = (2, 1, 3)

Split the message into 3-grams: ABC|DEF

Permute each 3-gram: BAC|EDF --> C = BACDEF

As you can see, even this simple algorithm is very complicated in its own way. Sometimes, it helps to put the letters in a grid to better visualize how a message might have been transposed. The permutation may also be represented alphabetically:

Ex. A key of  "KEY" corresponds to the permutation (2, 1, 3) due to alphabetical order

The Route cipher involves writing a message in a grid and consists of three keys. One key specifies the direction in which the plaintext will be written, another key specifies the direction that it will be read to produce the ciphertext. And the last key is a number chosen to represent the width of the grid. There are evidently hundreds of possible routes and messages, but one route is much more commonly used than others: write horizontally in rows and read down the columns. This specific pattern is known as a Swagman cipher. A sample encryption is shown below:

P = ABCDEF                                          Grid:    A  B  C   (read down)

Key = 3                                                               D  E  F

In case the grid was not constructed perfectly, the encryptor could choose to use padding (typically the letter 'X') or leave the empty cells blank:

P = ABCDE                                           Grid:   A  B  C  (read down)

Key = 3                                                             D  E  X

Given a ciphertext with a lot of padding, if we know that the padding has to appear at the end of the message, it could be a clue as to what transposition algorithm was used. Note that this cipher works very well with messages whose lengths are perfect squares, so if the length of the message is a perfect square, it might be a hint that this cipher was used.

The columnar transposition cipher is similar to the Route cipher described above, except that the key is a permutation instead of a number. Essentially, the columns in the grid are rearranged according to the permutation, and the plaintext is read down the columns:

1  2  3                           2  1  3

P = ABCDEF                                        Grid:  A  B  C            -->          B  A  C  (read down)

Key = (2, 1, 3)                                                D  E  F                            E  D  F

The rail fence cipher is similar to a Route cipher, except the key specifies the HEIGHT of the grid rather than its width. The pattern looks like a rail fence, hence the cipher's name:

P = ABCDEFGHI                                Grid:   A               E             I     (read across)

Key = 3                                                               B      D     F     H

C =  AEIBDFHCG                                                   C            G

There are many more transposition algorithms and complex variants, including the Myskowski transposition cipher, the redefence cipher, and hundreds of possible Route cipher patterns. But these are the more commonly known and used algorithms.

How do I recognize it?  Transposition ciphers are actually quite easy to recognize. If a ciphertext has letter frequencies that match up almost exactly with standard English letter frequencies (ETAION SHRDLCU) then it has probably been transposed. This is because rearranging the letters in a message does not affect their frequencies. The index of coincidence should be approximately equal to 0.667, the IOC for an English plaintext.

How do I break it?   Look at the factors of the length of the ciphertext. The encryptor most likely chose a key that would work well with the length of the message, so when trying all possible keys, start with the factors. Note that this does not always hold true -- the encryptor may have purposely chosen a key that works poorly with the length of the message to throw off cryptanalysts. Additionally, some transposition algorithms are independent of the length of the message. The rail fence cipher works equally well no matter what key is chosen. Learn more from Sample Challenges #3 and #4 under Tutorials

There is no way to properly determine exactly WHICH transposition algorithm was used, so the only way to break a message is to try all of them! All possible algorithms and all possible keys. This is known as a brute-force method. I have provided some encryption/decryption Python programs for the common transposition algorithms in Tools, but it is up to you to do the brute-forcing. Patience is a must.

Takeaway: A transposition cipher can easily be recognized, but the specific transposition algorithm that was used to transpose the message can be difficult to determine. The only feasible way to break such a cipher using modern computing is with a brute-force method that cycles through all the common transposition algorithms and possible keys.