Transposition

Transposition is the second great historical principle of encryption, complementary to substitution. Rather than replacing each letter, you keep the plaintext letters as they are and change their order following a deterministic rule. The plaintext ATTACK may become KCATTA (reversed), TKACTA (some other permutation), or any other anagram per the rule.

The signature: frequency preserved

Important consequence for cryptanalysis: letter frequencies are preserved exactly between plaintext and ciphertext. Counting letters in a Rail Fence or a Scytale gives exactly the same profile as the plaintext (E at 12.7 %, T at 9.1 %…) — frequency analysis is blind. This is the first signature that tells the cryptanalyst: “don’t waste time on a basic count”.

The index of coincidence of a transposition ciphertext is also identical to the plaintext’s (~0.067 EN, ~0.074 FR). Same letters, same proportions: just shuffled.

The weakness: digrams broken

On the other hand, digrams (pairs) and trigrams (triples) are broken. If you read TH 12 times in a plain English text, you’ll find it 0 times in its transposed ciphertext (barring accidents). Same for ES in French, ENT in French, THE in English.

That’s the classic cryptanalytic lever: rebuild the expected digrams by testing plausible permutations. Method:

1. Assume a grid width (for columnar transposition).
2. Slice the ciphertext into columns.
3. Try to reorder those columns so that pairs of adjacent letters form common English/French digrams.
4. The right order pops out when TH, EN, IN cascade into place.

On a short text, noise dominates and you may stall. On a long text, it’s mechanical.

Typical examples

Scytale (Sparta, 500 BCE)

The oldest attested cipher. You wrap a parchment around a staff of fixed circumference. You write the message line by line along the staff. Once unwound, the parchment carries the letters in a permuted order. A recipient with a same-circumference staff can read the message; anyone else reads gibberish. The key is the circumference.

Rail Fence

You write the plaintext in a zigzag across N “rails” (rows), then read row by row. For N = 3:

A . . . T . . . A . . . T
. T . . . A . . . C . . . K
. . T . . . . . . . . . .

Reading: ATAT + TACK + T. Very simple, ridiculous key space (just N), crackable in a few tries.

Columnar transposition

You write the plaintext into a grid of fixed width set by a key, then read the columns in the order dictated by the key. With key CIPHER (6 columns):

C I P H E R
1 4 5 3 2 6
A T T A C K
A T D A W N

Read column 1 (A,A), then 2 (C,W), then 3 (A,A)… per the alphabetic order of the key. Key space: n! possible permutations with a length-n key.

Double transposition

Two columnar passes with different keys. The result scrambles digrams to the point that cryptanalysis becomes very arduous. Used by the German army during World War I (ÜBCHI system), then broken by French services.

Rotating grid

A rectangular grid with holes, laid over a full grid. You write the plaintext in the holes, rotate the grid by a quarter turn, continue, and so on. At the end, you read the full grid row by row. Invented by the Italian mathematician Cardano in the 16th century.

Substitution versus transposition: recap

	Substitution	Transposition
Action	Replaces letters	Reorders letters
Plaintext frequency	Modified	Preserved exactly
Index of coincidence	Varies	Same as plaintext
Anagram of plaintext?	No	Yes
Cryptanalysis	Frequency analysis	Digram reconstruction

The modern marriage: Shannon, confusion + diffusion

The best modern ciphers always combine substitution AND transposition: that’s Shannon’s principle (1949) — “confusion + diffusion”. Substitution brings confusion (makes the relationship between key and ciphertext opaque). Transposition brings diffusion (spreads the effect of a single plaintext bit across the entire ciphertext).

• AES alternates SubBytes (non-linear substitution), ShiftRows (cyclic transposition), MixColumns (linear mixing), AddRoundKey on every round. Over 10-14 rounds.
• DES alternates S-Boxes (substitution) and P-box (permutation/transposition) over 16 Feistel rounds.
• ADFGVX (1918) German cipher of WWI’s end: Polybius substitution + columnar transposition. Broken by Painvin in 1918.

Pure transposition today

Pure transposition (without substitution) has become rare as production encryption — it doesn’t hold up against modern tools. But you still see it:

• In CTFs and cipher puzzles, as a pedagogical step.
• In linguistic steganography: permute a word’s letters to hide a meaning (name anagrams).
• In hybrid ciphers where transposition complements a substitution.

Key takeaways:

• Transposition = reorder letters without replacing them. A giant anagram.
• Preserves letter frequency and the IC of the plaintext → frequency analysis yields nothing.
• Classical break: rebuild expected digrams/trigrams by testing permutations.
• Examples: scytale, rail fence, columnar, double transposition, rotating grid.
• Modern ciphers (AES, DES) always combine substitution + transposition (Shannon’s confusion + diffusion doctrine).