Columnar Transposition

IPhenomenon

Write the plaintext in rows under the keyword. Then number the keyword's letters in alphabetical order, and read the columns in that numbered order.

Keyword BRASS, plaintext LOOM NEVER STOPS:

The keyword's alphabetical order is A(3), B(1), R(2), S(4), S(5), so the reading order is column 3, then 1, then 2, then 4, then 5. Reading that way gives OE P then LET then OVO then MRS then NSX, joined as OEPLETOVOMRSNSX.

Then the padding: the final row needed an X to close the rectangle, and the receiver has to know to discard it. That is the whole method — and note how differently it fails from a substitution. The letters are all exactly where the alphabet left them; only their neighbours changed.

IIKey space

A keyword of k distinct letters gives k! possible column orderings. For k = 8 that is 40,320; for k = 10, 3.6 million.

That is respectable, and it is why militaries used it. But two practical factors shrink it badly. First, the keyword must be memorable, so real keys come from a small pool of words. Second, and more importantly, an attacker rarely needs the key — they need the column order, and the column order can be recovered statistically.

The attack on a transposition cipher is not a search over keys. It is a search over orderings, guided by the statistics of the language.

The standard technique is to compare digraph and trigraph frequencies across candidate column pairs. Certain pairs of letters occur together far more often than chance — TH, HE, IN, ER — and a wrong column adjacency kills those pairs. With a few hundred letters of ciphertext, the ordering falls out.

IIIEnciphering

• Choose a keyword with no repeated letters if possible, and write it across the top of the page.
• Number the columns by the alphabetical rank of each keyword letter, left to right.
• Write the plaintext in rows beneath the keyword, one letter per column.
• Pad the final row with filler to close the rectangle, and choose filler that does not distort the digraph statistics if you can — X and Q are good, E is not.
• Read the columns in rank order, top to bottom, left to right by rank.
• Write the result as a continuous string and group in fives.
• For military traffic, encipher the result again with a substitution, and never send the keyword by the same channel.

IVDeciphering

• Count the ciphertext letters and divide by the key length to get the number of rows. If there is a remainder, the last few columns are one letter shorter — work out which.
• Write the ciphertext into the columns in rank order, filling each column to its computed height.
• Re-order the columns into their original sequence using the keyword.
• Read across the rows to recover the plaintext.
• Discard the filler at the tail.
• For an unknown key, guess the length from the message length and the number of possible rectangles, then score candidate column orderings by digraph frequency. TH, HE and IN together will usually fix the correct order within a few hundred letters.

VWeakness

Anagramming works. Because the letters are all present, the analyst can try candidate orderings and score them against language statistics, and the search converges quickly.

Padding leaks length. A rectangle that does not close needs filler, and the amount of filler tells the analyst the message length modulo the key length.

Short keys are fatal. Under about seven letters the space is small enough to enumerate cheaply, especially with a crib.

Repeated phrases are fatal. Anything the sender writes twice in the same position — a standard opening, a signature, a routing header — lines up in the columns and reveals the structure directly.

Single transposition is not enough. Every serious user composed it with something else: a substitution first to remove the letter frequencies, then transposition to remove the order. The German ADFGVX and the British double transposition systems are both this pattern.

VIPractice

·History note

Columnar transposition has no single inventor and appears in European military manuals from the eighteenth century onward. It reached its highest form in the German ADFGVX field cipher of 1918, which combined a 6 x 6 fractionating substitution with a columnar transposition keyed by a word. The French cryptanalyst Georges Painvin broke ADFGVX in June 1918 under extreme pressure, reading a message that revealed the location of the German spring offensive's artillery, and the intelligence is credited with contributing to the Allied recovery in that year. Britain's First World War double transposition systems and the later SOE agent ciphers were direct descendants.

·Further reading

Columnar transposition is the last purely mechanical cipher on this loom before the age of machines, and it is a good place to see the general pattern of twentieth-century cryptography: compose a substitution that destroys letter identity with a transposition that destroys order, and repeat.

It is also the clearest illustration of why order carries information. A shuffled message retains every letter and loses every relationship, and the relationships are where the meaning lives. Modern block ciphers do the same thing in every round.

Next on the loom: baconian-cipher returns to substitution with a scheme that hides the message in the form of the text rather than its content.

+Weave into