Cryptography/Transposition ciphers

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Another type of transpositional 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 cyphertext.

The following diagram shows the message "JIM ATTACKS AT DAWN" encoded using a 4x4 grille.

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

  1. blank grille on the paper.
  2. first four letters written in the blanks.
  3. grille rotated one position, second set of letters written.
  4. grille rotated two positions, third set of letters written.
  5. grille rotated three positions, fourth set of letters written.

After the letters in the message have all been written out, the ciphertext can be read from the paper: "JKDT STAA AIWM NCAT".

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.