Columnar Transposition
Write in rows, read by columns — letter frequencies preserved, positions scrambled
Frequency analysis · Anagramming
Advanced Bounded Columnar Search
Supply a known width first. The staged option estimates column adjacency, and for incomplete rectangles retains the best relative-offset alignment. Segment slides and segment swaps preserve some neighboring columns while moving larger blocks. The second phase scores the full candidate text using the museum language model.
Change one option at a time to compare searches with the same seed and budget.
Limits: widths 2–12, at most 20,000 score evaluations, including adjacency preprocessing, phase-transition scoring and every restart. Unknown-width mode divides one total budget across widths 2–12; preprocessing may exhaust a width's allocation. This bounded adaptation samples moves and combines normalized adjacency/alignment scores; it does not reproduce Lasry's alternating thresholds, exhaustive neighborhoods, optimized triplet scores or large-key performance. Language-model fitness uses the museum's bigram/trigram model. A candidate remains unverified even if it looks readable.
Classroom experiment: run the fixed 24-trial comparison and keep its receipt. It reuses this solver with four supplied-answer messages, three seeds and two variants. The worksheet separates exact plaintext from exact key recovery and retains failed or preprocessing-exhausted runs. A shared seed alone does not make changed algorithms follow matching random paths.
Source: George Lasry, A Methodology for the Cryptanalysis of Classical Ciphers with Search Metaheuristics (2018), §§5.3.2–5.3.4, printed pp. 69–78 / supplied PDF pp. 90–99. Evaluation principles: §§4.5–4.7, printed pp. 57–60 / PDF pp. 78–81.
Why This Matters
Columnar transposition rearranges positions while preserving letter counts. It is a useful way to study the difference between a large number of possible keys and the statistical structure an attacker can exploit.
Columnar systems appear in historical military and recreational cryptography, sometimes combined with other operations. “Columnar transposition” describes a family of writing and reading conventions, not one securely dated nineteenth-century invention. Complete rectangles, incomplete final rows and padding rules produce different attack problems.
Write the message in rows across a grid whose width is the keyword length. Number the columns by alphabetical order of the keyword letters. Read off columns in that numbered order. Myszkowski transposition changes how repeated keyword letters are handled: tied columns are read together across each row.
Keyword: ZEBRA → Z=5, E=3, B=2, R=4, A=1
Columns: 5 3 2 4 1
W E A T H
E R F O R
E C A S T
I N G X X
Read col 1(A): HRTX
Read col 2(B): AFAG
Read col 3(E): ERCN
Read col 4(R): TOSX
Read col 5(Z): WEEI
Transposition preserves the plaintext's letter counts. A distribution resembling English can suggest transposition, but does not identify it with certainty. Analysts try plausible widths and rearrange columns, looking for useful letter contacts and readable text. Several messages with the same width and column order let them test one arrangement against more evidence.
Try it: rearrange several intercepts
One promising pair of letters can be a coincidence. Can you find an order that makes three messages readable at once? Each synthetic message fills four rows of five letters. The sender read the five columns in the same secret order; we have already split each received message into five equal strips.
Select a strip and move it left or right. The corresponding column moves in every message. Read each reconstructed message across its rows. Spaces were removed; no letters were added as padding.
Current order: A → B → C → D → E
across the three same-key messages. This counts adjacent letter pairs from a small English list, only within rows. It is a clue, not a probability or confirmation; a wrong order can also score well.
Try an arrangement, then check it against the prepared messages.
What this exercise assumes
The width, equal column lengths and shared key are supplied to isolate the rearrangement problem. Real analysis may need to establish those facts first and handle incomplete rectangles, padding or multiple transpositions. The fourth intercept deliberately uses a different column order: a key recovered for one group need not solve other traffic. “Check” compares with the known answer to these invented examples; a contact score alone cannot validate a real intercept.
Our small contact list is: TH, HE, IN, ER, AN, RE, ON, AT, EN, ND, TI, ES, OR, TE, OF, ED, IS, IT, AL, AR, ST, TO, NT, NG, SE, HA, AS, OU, IO, LE, VE, CO, BE, RT, WA, SC, RO and UR. It is a teaching heuristic, not a fitted language model.
Reading companions: Helen Fouché Gaines, Cryptanalysis: A Study of Ciphers and Their Solution (1939; Dover edition 1956), Chapter VII, “General Methods — Multiple Anagramming, Etc.”; Joshua Holden, The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption (2017), §3.7. These motivate the method; the messages and simplified score here were created for this exercise.
| Concept from Columnar Transposition | Modern Evolution |
|---|---|
| Column reordering | AES ShiftRows: cyclic shifts within the rows of the byte state |
| Grid-based permutation | Permutation layers rearrange positions; a Feistel round also combines values |
| Keyword-controlled order | A key can select a permutation; AES key expansion is a different operation |
| Exhibit | 14 of 172 |
| Era | 19th Century |
| Trust | Broken |
| Inventor | No single inventor established here |
| Year | Historical transposition family |
| Key Type | Column-ordering keyword |
| Broken By | Frequency analysis · Anagramming |
Classical transposition practice includes route systems, regular columnar, Myszkowski ordering, and compound forms such as double transposition. Each variant preserves letter frequencies while changing positional structure.
The Nihilist transposition family extends these ideas into numbered-grid operations, showing how small procedural tweaks can significantly change attack difficulty.