Columnar Transposition Cipher Description and Cryptanalysis

Back to: [Classical Cryptography and list of ciphers] [Classical Cryptanalysis] [Cryptography Home]

On this page: [Introduction] [Example] [Javascript Example] [Cryptanalysis] [Code] [References]

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:

nalcxehwttdttfseeleedsoaxfseahl

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

Cryptanalysis

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 Classical Cryptanalysis section 'Text Characterisation'. 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.

Code

I have included here some C code that does encryption and decryption of the columnar transposition cipher. It is only meant to show the working of the algorithm, not be a final polished solution.
C Implementation of columnar transposition cipher

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.