Breaking Columnar Transposition

Candidate widths from the divisors, then every one of the m! orderings ranked by a bigram score.

CryptanalysisAnagrammingdemo

Objectives

Derive the candidate key lengths from the ciphertext length alone.
Rank every column ordering with a bigram score and recover the key.
Explain why the same attack resolves a paragraph and not a sentence.

33%

The key is a permutation of m columns, so the whole keyspace is m! orderings.

Columnar key (the secret)

Plaintext

ciphertext, 376 letters

UIFEV ICONO OESCY TYFDA SHTTD TBDBI WASDS NEIOS LIFDN OXSDD EOBEA OTARS EFOEL EILEV DESOI ETGPE RROHN HOTBT OUFHE AETLE OORMD WNTOA ABOEU DLOAY TFIWH OTTTR STAEL AUNYI NHEEE HASDW RORHP DTTED NYYGL TEUAE LDPAA HPAED TTILA IGXOD ARATU TARME IAAOS OEDES HSOAT NSKOL TNIOG NNIOD ONGNX HHHRU EFWRO NOITR DLACM OREFW TUELA SORUE UEDER AYFUR YILET WEMHM DWRPP ETHLR TLTAE HUHRL UNAYT FHTAS MADOS FITXS VRHDN RROOT CTYMY SLRAR AIOYD OCFAA RHSSU THRIE NLDSN G

The grid was rectangular, so the key length divides the ciphertext length. That single fact is the whole candidate list, and no statistics are needed to produce it.

candidate widths

The number beside each width is m!, the orderings to try. The greyed ones are not secure, only slow: a width this page refuses in a tab is minutes on any real machine.

Every one of the 40,320 orderings, scored on bigrams

score	order	plaintext
-408.7	6 0 2 4 5 1 7 3	SHESHOULDHAVEDIEDHEREAFTERTHEREWOU
-439.2	4 0 6 2 3 1 5 7	SHHOULESDHEDIEAVDHEAFTEREREREWTHOU
-439.5	6 0 4 2 3 1 7 5	SHHOESULDHEDAVIEDHEAERFTERERTHEWOU
-440.2	1 3 5 7 0 4 2 6	OULSHESHDIEDHAVEAFTDHEREREWERTHEAV
-441.1	2 4 6 0 1 5 3 7	HOULSHESEDIEDHAVEAFTDHEREREWERTHHA

Chi-square is blind here, because the letters never changed. A bigram score is not, because pairs are exactly what moved. The true order is 6 0 2 4 5 1 7 3.

The same key on the 23-letter sentence

ciphertext

ARLWO THEEV BEEOA ELHMT XAAD

-17.0	5 1 6 3 4 2 0 7	MWEVEAHATOLBOREAXTHEALED
-17.3	2 3 5 0 1 4 7 6	VEAWEHAMBOROLEATEALTHEDX

The true order ranks 99 of 40,320. Too little text to separate: the top few anagrams all read as almost-English, and nothing in the score prefers the right one.

Text length decides it, not the keyspace. The paragraph resolves and the sentence does not, with the same cipher, the same key, and the same attack. That is a property of the message, which is not something a cipher designer controls.

step 1/3

CPE 645 / CS 685

Breaking Columnar Transposition

Breaking the Rail Fence

Breaking a Product Cipher