TRANSPOSITION CIPHERS

Transposition ciphers rearrange the letters of the plaintext without changing the letters themselves. For example, a very simple transposition cipher is the rail fence, in which the plaintext is staggered between two rows and then read off to give the ciphertext. In a two row rail fence the message MERCHANT TAYLORS’ SCHOOL becomes:

M	R	H	N	T	Y	O	S	C	O	L
E	C	A	T	A	L	R	S	H	O

Which is read out as: MRHNTYOSCOLECATALRSHO.

The rail fence is the simplest example of a class of transposition ciphers called route ciphers. These were quite popular in the early history of cryptography. Generally, in route ciphers the elements of the plaintext (usually in this case single letters) are written on a pre-arranged route into a matrix agreed upon by the transmitter and receiver. The example above has a two row by n-column matrix in which the plaintext is entered sequentially by columns, the encryption route is therefore to read the top row and then the lower.

Obviously, to even approach an acceptable level of security, the route would have to be much more complicated than the one in this example. One form of transposition that has enjoyed widespread use relies on identifying the route by means of an easily remembered keyword. This can be done in several ways. One way, as in this example, is to define the order in which each column is written depending on the alphabetical position of each letter of the keyword relative to the other letters.

Using the keyword CIPHER, a matrix can be written out like the one below:

C	I	P	H	E	R
1	4	5	3	2	6
M	E	R	C	H	A
N	T	T	A	Y	L
O	R	S	S	C	H
O	O	L	Z	Z	Z

Unlike the previous example the plaintext has been written into the columns from left to right as normal, and the ciphertext will be formed by reading down the columns. The order in which the columns are written to form the ciphertext is determined by the key.

This matrix therefore yields the ciphertext: MNOOHYCZCASZETRORTSLALHZ.

The first column is first because C is the earliest in the alphabet, followed by the second to last column because E is the next in the alphabet.

The security of this method of encryption can be significantly improved by re-encrypting the resulting cipher using another transposition. Because the product of the two transpositions is also a transposition, the effect of multiple transpositions is to define a complex route through the matrix which would not by itself by easy to define with a simply remembered mnemonic.

When decrypting a route cipher, the receiver simply enters the ciphertext into the agreed-upon matrix

according to the encryption route and then simply reads out the plaintext.

In modern cryptography transposition cipher systems serve mainly as one of several methods used as a step in forming a product cipher.

Product Ciphers

In the days of manual cryptography i.e. without the aid of a computer product ciphers were a useful device for the cryptographer and double transposition ciphers on keyword-based matrices were, in fact, widely used. There was also some use of a particular class of product ciphers called fractionation systems. In a fractionation system a substitution is first made from symbols in the plaintext to multiple symbols (usually pairs, in which case the cipher is called a biliteral cipher) in the ciphertext, which is then superencrypted by a transposition.

One of the most famous field ciphers ever was a fractionation system - the ADFGVX cipher which was employed by the German Army during the first world war. This system was so named because it used a 6 ´ 6 matrix to substitution-encrypt the 26 letters of the alphabet and 10 digits into pairs of the symbols A, D, F, G, V and X. The resulting biliteral cipher is only an intermediate cipher, it is then written into a rectangular matrix and transposed to produce the final cipher which is the one which would be transmitted.

Here is an example of enciphering the phrase "Merchant Taylors" with this cipher using the key word "Subject".

	A	D	F	G	V	X
A	S	U	B	J	E	C
D	T	A	D	F	G	H
F	I	K	L	M	N	O
G	P	Q	R	V	W	X
V	Y	Z	0	1	2	3
X	4	5	6	7	8	9

Plaintext:

M

E

R

C

H

A

N

T

T

A

Y

L

O

R

S

Ciphertext:

FG

AV

GF

AX

DX

DD

FV

DA

DA

DD

VA

FF

FX

GF

AA

This intermediate ciphertext can then be put in a transposition matrix based on a different key.

C	I	P	H	E	R
1	4	5	3	2	6
F	G	A	V	G	F
A	X	D	X	D	D
F	V	D	A	D	A
D	D	V	A	F	F
F	X	G	F	A	A

The final cipher is therefore: FAFDFGDDFAVXAAFGXVDXADDVGFDAFA.