Cryptology Transposition Ciphers – Examples

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

A. Geometric Transpositions

Write down the plaintext in a certain order and read it off in a different order, like the spiral example. The transposition depends on the length of the text and is aperiodic (in general).

Example 1: The Scytale

… (σκυταλε, baton) was used by the Spartans in ancient Greece. They wrapped a leather strip around a cylinder and wrote the text on it. Unwrapping the strip separates adjacent letters and shows the letters in a permuted order.

Example 2: Columnar Transpositions

[Earliest known historic source: John FALCONER: Cryptomenytices Patefacta, 1685]

Write the plaintext in rows of width l and read it off by columns. Take the columns in a order defined by a key. [If you take the columns in their natural order—without using a key—, then the procedure amounts to a path transposition. The Scytale corresponds to such a columnar transposition with a trivial key.]

Example: l = 5,

Keyword   = A P P L E
Key       = 1 4 5 3 2

Plaintext = T H I S I
            S A C O L
            U M N A R
            T R A N S
            P O S I T
            I O N    

  TSUTP IILRS TSOAN IHAMR OOICN ASN

The legitimate receiver of the message knows the key, its length l, and the message length r (= 28 in the example). He calculates r/l, rounds this quotient up to the next integer m (28/5 → 6), and then writes down the ciphertext in columns of length m in the order given by the key. He fills the first r mod l (= 3 in the example) columns completely, and leaves blank the last positions of the remaining columns.

Variant: Instead of dealing with columns of different lengths one often pads the last row by random letters to fill the rectangle:

T H I S I
S A C O L
U M N A R
T R A N S
P O S I T
I O N X X

Note that padding with X's is not a good idea! Exercise: Why?

As shown in the example the key is usually not remembered as a number sequence but as a keyword. The number sequence derives from the alphabetical order of the keyword letters. If two (or more) letters coincide, the first one gets the lower number. Another example:

Keyword = F A R A D
Key     = 4 1 5 2 3

Example 2bis: Double Columnar Transpositions

The double columnar transposition consists of one more application of the procedure—possibly, although not necessarily—with another width and another key. This method was in wide use in World War I, also in World War II, and even sometimes later. In many cases the respective enemy could break it. However this is not so easy, especially when used with care.

Example:

Keyword        = F A R A D
Key            = 4 1 5 2 3

Plaintext      = T S U T P
(intermediate)   I I L R S
                 T S O A N
                 I H A M R
                 O O I C N
                 A S N    

  SISHO STRAM CPSNR NTITI OAULO AIN

A systematic treatment is in:

S. Kullback: General Solution for the Double Transposition Cipher. Aegean Park Press, Laguna Hills 1980.

Wayne G. Barker: Cryptanalysis of the Double Transposition Cipher. Aegean Park Press, Laguna Hills 1995.

George Lasry, Nils Kopal, Arno Wacker: Solving the double transposition challenge with a divide-and-conquer approach. Cryptologia 38 (2014), 197–214.

Example 3: Path Transpositions

The plaintext is written along a defined path, and the ciphertext is read off by rows (or along another defined path). We saw an example in the first section of this Chapter.

B. Grilles

… define periodic transpositions. In a simple form they were proposed by Ibn AD-DURAIHIM in 14^th and by Gerolamo CARDANO in 16^th century. These proposals however should be interpreted rather as steganographic methods than as cryptographic transpositions: The plaintext is written into the holes of the grille, then the grille is removed, and the blank spaces are filled with innocent looking letters. Ideally the resulting text should make some unsuspicious sense.

In contrast turning grilles describe transposition ciphers. In this form grilles are known already in 18^th century. Near the end of 19th century they became somewhat fashioned. For a description see the paper

F. L. Bauer: Fleissner-Raster und der Erzherzog, Informatik-Spektrum 30 (2007), 36–38,

A mixture of columnar transposition and grille was in occasional use still in World War II (»Wehrmacht-Rasterschlüssel 44« and variants, or »Crossword Ciphers«). Here the plaintext was written in the holes of the grille by rows. Some holes were reserved for null characters. Reading the text by columns yielded reasonably good transpositions.

C. Block Transpositions

… are the general periodic transpositions. A Perl programm for columnar and block transpositions is here.

Example: l = 2. The most simple block transposition consists in pairwise interchanging adjacent letters. Called PAIRTRANSP it is a counterpart of ROT13:

HTSISINAFOEFSNE

Also see Example 2 in the introductory section, here l = 5.

Key Lengths

For the simple columnar transposition as well as for the block transposition given the length l of the keyword the number of possible keys is l!. If the keyword length l is known a priori, then the effective key length in bits is the 2-logarithm of l!.

If the keyword length l is unknown a priori, but only an upper bound L, then we have to add the factorials l! for l up to L before taking the 2-logarithms. This doesn't make them significantly larger (21.9 instead of 21.8 in the last row).

The following table gives an impression of these numbers:

Manual exhaustion seems feasible for keyword lenghts up to 7 or 8, computerized exhaustion for keyword lengths even larger than 10.