Cryptography/Transposition ciphers

A transposition cipher encodes a message by reordering the plaintext in some definite way. Mathematically, it can be described as applying some sort of bijective function. The receiver decodes the message using the reordering in the opposite way, setting the ordering right again. Mathematically this means using the inverse function of the original encoding function.

For example, to encrypt the sentence "A simple kind of transposition cipher writes the message into a rectangle by rows and reads it out by columns," we could use the following rectangle:

Asimplekin
doftranspo
sitionciph
erwritesth
emessagein
toarectang
lebyrowsan
dreadsitou
tbycolumns

Then the encrypted text would be "Adsee tldts oirmo erbif tweab eymti rsrya cproi serdo lanta cosle ncegt wiuks iseas tmipp tinao nnohh ngnus."

This cipher is often complicated by permuting the rows and columns, as in columnar transposition.

Columnar transposition

The standard columnar transposition consists of writing the key out as column headers, then writing the message out in successive rows beneath these headers (filling in any spare spaces with nulls), finally, the message is read off in columns, in alphabetical order of the headers. For example suppose we have a key of 'ZEBRAS' and a message of 'WE ARE DISCOVERED. FLEE AT ONCE'. We start with:

Z	E	B	R	A	S
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

Then read it off as:

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then he can write the message out in columns again, then re-order the columns by reforming the key word.

Double transposition

A single columnar transposition could be attacked by guessing possible column lengths, writing the message out in its columns (but in the wrong order, as the key is not yet known), and then looking for possible anagrams. Thus to make it stronger, a double transposition was often used. This is simply a columnar transposition applied twice, with two different keys of different (preferably relatively prime) length. Double transposition was generally regarded as the most complicated cipher that an agent could operate reliably under difficult field conditions. It was in actual use at least as late as World War II (e.g. poem code).

Grille

Another type of transposition cipher uses a grille. This is a square piece of cardboard with holes in it such that each cell in the square appears in no more than one position when the grille is rotated to each of its four positions. Only grilles with an even number of character positions in the square can satisfy this requirement. As much message as will fit in the grille is written, then it is turned to another position and more message is written. Removing the cardboard reveals the ciphertext.

The following diagram shows the message "The report of my death was an exaggeration" with a 6x6 grille. The letter X is added at the end as padding.

The top row shows the cardboard grille and the bottom row shows the paper underneath the grille at five stages of encoding:

There are five main stages of encoding with a grille cipher:

1. Place a blank grille on the paper.
2. Write the first nine letters in the blanks.
3. Rotate the grille to the first position and write the second set of letters.
4. Rotate the grille to the second position and write the third set of letters.
5. Rotate the grille one more time and write the final set of letters.

After the letters in the message have all been written out, the ciphertext can be read from the paper: "TWGASO FEMRHA YADNEE XRETPI EAAOTN XORHTG".

The sender and receiver must agree on the initial orientation of the grille, the direction to rotate the grille, the order in which to use the spaces on the grille, and the order in which to read the ciphertext characters from the paper.