Transposition & Fractionation
Rearranging the message instead of replacing its letters
Substitution ciphers replace letters — but their frequencies always leak. What if instead you kept the letters but scrambled their positions? Transposition ciphers do exactly this. Combined with fractionation — splitting each letter into coordinate pieces before rearranging — these systems produced some of the most sophisticated manual ciphers ever designed, and directly inspired the diffusion layers in modern block ciphers.
Transposition vs Substitution: Substitution replaces letters (A→Q), preserving positions. Transposition keeps letters but moves them (position 1→7). Both methods preserve statistical information — substitution preserves frequency, transposition preserves frequency too. The letters are all still there. Only their arrangement changes.
Rail Fence Cipher — "HELLOWORLD" on 3 rails
Read row by row: HOL · ELWRD · LO → Ciphertext: HOLELWRDLO
Write the message in a zigzag across imaginary rails; read it row by row. The key is simply the number of rails. The entire keyspace is the number of possible rail counts — brute-forced in seconds even by hand.
Write the message in rows across a grid; read columns in keyword-specified order. The column ordering is the key. Frequency analysis still works because all original letters are present — just rearranged.
Apply columnar transposition twice with two different keys. The resulting permutation space is enormous. German military intelligence used this in WWI. Still difficult for computers if ciphertext is short and key length is unknown.
Felix Delastelle's masterwork: Polybius square converts letters to row/column coordinates, which are written in two separate rows, then recombined into new pairs. The fractionation mixes coordinate information across the entire message.
Delastelle's extension of Bifid into three dimensions. A 3×3×3 cube replaces the 5×5 square; each letter becomes three coordinates (layer, row, col) which are woven together across the message. Higher entropy fractionation.
Convert plaintext to Morse code (dots, dashes, spaces); group the resulting stream into triples; substitute each triple with a letter using a keyed alphabet. Morse's irregular letter lengths introduce structural noise that resists standard frequency analysis.
Transposition Lives in Every Modern Block Cipher
AES's ShiftRows step cyclically shifts the rows of its 4×4 state matrix — a direct descendant of columnar transposition. Every byte's position changes, ensuring that input patterns don't propagate directly to output patterns.
AES's MixColumns operation mixes the four bytes of each column using matrix multiplication over GF(2⁸) — exactly the fractionation principle from Bifid, made mathematically rigorous and non-linear.
Shannon defined "diffusion" as spreading the influence of each plaintext bit across many ciphertext bits. Double transposition approximates this. AES achieves it completely: after 2 rounds, every output bit depends on every input bit.