Transposition Ciphers : Information Security

     
A transposition cipher is a method of encryption by which the positions held by units of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed.    

    Transposition ciphers are rather simple to understand. As the name implies, a transposition cipher involves the transposing – or moving – of characters from one place to another. See the example below. You’ll notice that all the characters used in the original text are also present in the transposed text.

Original Text: HELLO WORLD
Transposed Text: HLOOLOLWRD
Side note: This is an example of a rail fence cipher. A rail fence cipher is computed as follows. Notice the words are spelled out in columns, starting at the top left:

HLOOL
ELWRD

Cracking the Code

Cracking a transposition cipher can be accomplished with a process called anagramming.  Using language statistics, its relatively easy to crack a transposition cipher. If you know the frequency in which certain letter combinations occur, it is possible to crack a transposition cipher (see Alan Konheim’s book for an in-depth review).  In this case, we can crack the cipher as such:

The letter pairs HL, HW, HR and HD have a frequency of less than 0.0010 in the English language, so we’ll discard those for now. HE has a frequency of 0.0305. However, other arrangements – “HO” for example – are also candidates which shouldn’t be ruled out. In the end, you should get something like:

HE
LL
OW
OR
LD

While this method is rather reliable, remember that you’re also relying on statistical pattern matching, which is always error prone to some degree.

By themselves, transposition ciphers provide very little confidentiality.  Modern algorithms still use transposition, however only as a piece of the algorithm – not the whole.

Other methods for Transposition Cipher:

One of the oldest ways to do this was created by the ancient Egyptians and Greeks. It uses a stick called scytale . They would have used wooden sticks and parchment, but we're going to use poster tubes and adding machine tape!

How the scytale cipher works

1. Get a scytale and a strip of parchment.
2. Wrap your parchment around your scytale until the stick is covered. Try to avoid overlapping and gaps.
3. Write your message along the length of the stick, one character per pass of the paper. If you need more space, rotate the stick away from you and keep writing.
4. Unwrap the scytale and send the scrambled message to a friend with the same-diameter stick.
5. The friend then wraps his scytale with the encoded parchment. Since the diameters are the same, the message is clearly legible!

This technique was very useful in ancient battles; the Spartans are known to have used this rather extensively. Each general was given a stick of uniform diameter so that he could quickly encipher and decipher any message sent from other generals. Notice how quick and easy this is to use!

          However, it is also rather easy to crack. In a battle situation, the most likely way to crack this would be to steal a general's scytale. Then, each message could be read easily. However, it can be cracked even without stooping to theivery. As it ends up, the scytale is just a very old (and rather simple) version of a greater class of ciphers called matrix transposition ciphers. The way the simplest of these works is by picking a matrix of a fixed size (say, 6x10) and then writing your message across the rows. The encipherment step consists of writing down the letters in the matrix by following the columns. Here's a simple 6x10 example:

T	R	O	O	P	S	H	E	A	D
I	N	G	W	E	S	T	N	E	E
D	M	O	R	E	S	U	P	P	L
I	E	S	S	E	N	D	G	E	N
E	R	A	L	D	U	B	O	I	S
M	E	N	T	O	A	I	D

Where we've written the message:

troops heading west need more supplies. send general dubois' men to aid

row by row into the matrix. Then, to encipher this, we simply read off the columns to get:

TIDIE MRNME REOGO SANOW RSLTP EEEDO
SSSNU AHTUD BIENP GODAE PEIDE LNS

The scytale cipher is just like one of these. Note that the number of "rows" in your message is determined by the diameter of your stick and the size of your writing. Cracking them, as you may guess, is just a matter of systematic guess-and-check.

How to crack the simple matrix transposition ciphers:

1. Count how many letters are in the ciphertext (for this example, assume the ciphertext is 99 letters long)
2. Make all of the matrices that would fit such a length (e.g. 2x50, 3x33, 4x25, 5x20, 6x17, 7x15, 8x13, 9x11, 10x10). Use TWO of each size.
3. For each size matrix, write out the ciphertext across the rows on one copy. On the other copy, write out the ciphertext down the columns.
4. At each stage, see if you can find anything legible, reading perpendicular to how you put the ciphertext in.

A harder version of the matrix transposition cipher is the column-scrambled matrix transposition cipher. Just like the ones above, you find a matrix of suitable dimensions and write your text in row-by-row. If there are blank cells left, fill them in with a dummy character (sometimes an 'X'). However, before writing down the ciphertext from the columns, you first scramble the columns. This generates a new matrix of the same size. Now read off the text down the columns, as before. This is a harder cipher, but there is a systematic way to crack it.

How to crack the column-scrambled matrix transposition ciphers:

1. Count how many letters are in your ciphertext (for example, 75) and factor that number (75 =5*5*3).
   
   
2. Create all of the possible matrices to fit this ciphertext (in our case, 3x25, 5x15, 15x5, 25x3).
   
   
3. Write the ciphertext into these matrices down the columns.
   
   
4. For each of your matrices, consider all of the possible permutations of the columns (for n columns, there are n! possible rearrangements). In our case, we hope that the message was enciphered using one of the last two matrices (the 15x5 and the 25x3), since in those cases, we have only 6 and 120 possibilites to check (3! = 6, 5! = 120, 15! ~ 1.31x10^12, 25! ~ 1.55x10^25).
   
   
5. Rearrange each matrix to see if you get anything intelligible. Read the message off row-by-row. Note that this is much more easily done by a computer than by hand, but it is doable (for small matrices).

Material referenced from Infosecschool and Cornell University