Code 14 : Columnar Transposition Cipher

In a columnar transposition, the message is written out in rows of a fixed length. The message is then read out by column by column, where the columns are chosen in some scrambled order. The number of columns and the order in which they are chosen is defined by a keyword. For example, the word ZEBRAS is 6 letters long. Therefore, there are 6 columns that will be read of in the following order: 6 3 2 4 1 5. The order is chosen by the alphabetical order of the letters in the keyword.
Regular Case
In a regular columnar transposition cipher, the empty spaces are filled with random letters. For example, suppose we use the keyword ZEBRAS and the message WE ARE DISCOVERED FLEE AT ONCE. Our grid would look like this:

Z E B R A S
6 3 2 4 1 5
- - - - - -
W E A R E D 
I S C O V E 
R E D F L E 
E A T O N C 
E Q K J E U 

The six columns are now written out in the scrambled order defined by the keyword:

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

Irregular Case
In the irregular case, the empty letters are not filled in with random letters:

Z E B R A S
6 3 2 4 1 5
- - - - - -
W E A R E D 
I S C O V E 
R E D F L E 
E A T O N C 
E 

This results in the following (shorter) ciphertext:

EVLNA CDTES EAROF ODEEC WIREE

To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. This step is slightly more difficult if the irregular case is used. After determining the number of columns, the message can be written in columns and rearranged back into the plaintext message.
Double Column Transposition
To make the message even more difficult to decipher, you can take the ciphertext produced by this algorithm and run it through the encryption again using a different keyword. This transposes the columns twice and makes the message extremely difficult to decipher.

 

Columnar Transposition Cipher

Introduction

The columnar transposition cipher is a fairly simple, easy to implement cipher. It is a transposition cipher that follows a simple rule for mixing up the characters in the plaintext to form the ciphertext.
Although weak on its own, it can be combined with other ciphers, such as a substitution cipher, the combination of which can be more difficult to break than either cipher on it's own. The ADFGVX cipher uses a columnar transposition to greatly improve its security.

Example

The key for the columnar transposition cipher is a keyword e.g. GERMAN. The row length that is used is the same as the length of the keyword. To encrypt a piece of text, e.g.

defend the east wall of the castle

we write it out in a special way in a number of rows (the keyword here is GERMAN):

G E R M A N
d e f e n d
t h e e a s
t w a l l o
f t h e c a
s t l e x x

In the above example, the plaintext has been padded so that it neatly fits in a rectangle. This is known as a regular columnar transposition. An irregular columnar transposition leaves these characters blank, though this makes decryption slightly more difficult. The columns are now reordered such that the letters in the key word are ordered alphabetically.

A E G M N R
n e d e d f
a h t e s e
l w t l o a
c t f e a h
x t s e x l

The ciphertext is read off along the columns:

nalcxehwttdttfseeleedsoaxfeahl

JavaScript Example of the Columnar Transposition Cipher

This is a JavaScript implementation of the Columnar Transposition Cipher. This implementation pads the plaintext so that its length is a multiple of the key length.
Plaintext
attack at dawn keyword = pad character =

Ciphertext

Cryptanalysis

For a guide on how to automatically break columnar transposition ciphers, see here.
Breaking columnar transposition ciphers by hand is covered in the book by Helen Fouche Gains "Cryptanalysis - a study of ciphers and their solution" and the book by Sinkov "Elementary Cryptanalysis". A comprehensive guide is also given in "Military Cryptanalysis - part IV" by Friedman.
The columnar transposition cipher is not the easiest of transposition ciphers to break, but there are statistical properties of language that can be exploited to recover the key. To greatly increase the security, a substitution cipher could be employed as well as the transposition.
A peculiarity of transposition ciphers is that the frequency distribution of the characters will be identical to that of natural text (since no substitutions have been performed, it is just the order that has been mixed up). In other words it should look just like this:

English Letter Frequencies

Cracking by hand is usually performed by anagramming, or trying to reconstruct the route. The more complex the route, the more difficult to crack.
For a method that works well on computers, we need a way of figuring out how "english like" a piece of text is, check out the Text Characterisation cryptanalysis section. The key that results in a decryption with the highest likelyhood of being english text is most probably the correct key. Of course, the more ciphertext you have, the more likely this is to be true (this is the case for all statistical measures, including the frequency approaches above). So the method used is to take the ciphertext, try decrypting it with each key, then see which decryption looks the best. In the case of this cipher, there are potentially a fair few keys. We can use an optimisation technique such as simulated annealing or a genetic algorithm to solve for the key.

References 

 http://practicalcryptography.com

• Wikipedia has a good description of the encryption/decryption process, history and cryptanalysis of this algorithm
• Simon Singh's 'The Code Book' is an excellent introduction to ciphers and codes. Singh, Simon (2000). The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. ISBN 0-385-49532-3.