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

keyword = pad character =

Ciphertext

Other Implementations §

To encipher your own messages in python, you can use the pycipher module. To install it, use pip install pycipher. To encipher messages with the Columnar transposition cipher (or another cipher, see here for documentation):

>>>from pycipher import ColTrans
>>>ColTrans("HELLO").encipher('defend the east wall of the castle')
'ETSLELDDALHTFHTOCEEEWFANEATS'
>>>ColTrans("HELLO").decipher('ETSLELDDALHTFHTOCEEEWFANEATS')
'DEFENDTHEEASTWALLOFTHECASTLE'

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:

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 §

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.