Editing Transposition cipher (section)

== Columnar transposition ==
<!-- This section is linked from [[Substitution cipher]] -->

=== Encryption ===

In a columnar transposition, the message is written out in rows of a fixed length, and then read out again column by column, and the columns are chosen in some scrambled order. Both the width of the rows and the permutation of the columns are usually defined by a keyword. For example, the keyword {{mono|ZEBRAS}} is of length 6 (so the rows are of length 6), and the permutation is defined by the alphabetical order of the letters in the keyword. In this case, the order would be "6 3 2 4 1 5".

In a regular columnar transposition cipher, any spare spaces are filled with nulls; in an irregular columnar transposition cipher, the spaces are left blank. Finally, the message is read off in columns, in the order specified by the keyword. For example, suppose we use the keyword {{mono|ZEBRAS}} and the message {{mono|WE ARE DISCOVERED. FLEE AT ONCE}}. In a regular columnar transposition, we write this into the grid as follows:
 6 3 2 4 1 5
 W E A R E D
 I S C O V E 
 R E D F L E 
 E A T O N C 
 E Q K J E U 
providing five nulls ({{mono|QKJEU}}), these letters can be randomly selected as they just fill out the incomplete columns and are not part of the message. The ciphertext is then read off as:
 EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

In the irregular case, the columns are not completed by nulls:
 6 3 2 4 1 5
 W E A R E D 
 I S C O V E 
 R E D F L E 
 E A T O N C 
 E 
This results in the following ciphertext:
 EVLNA CDTES EAROF ODEEC WIREE

=== Decryption ===

To decipher it, the recipient has to work out the shape of the enciphering grid by dividing the message length by the key length to find the number of rows in the grid. The length of the grid's last line is given by the remainder. The key is written above the grid, and the ciphertext is written down the columns of the grid in the order given by the letters of the key. The plaintext appears on the rows. A partial decipherment of the above ciphertext, after writing in the first column:

 6 3 2 4 1 5
 . . . . E .
 . . . . V .
 . . . . L .
 . . . . N .
 .

In a variation, the message is blocked into segments that are the key length long and to each segment the same permutation (given by the key) is applied. This is equivalent to a columnar transposition where the read-out is by rows instead of columns.

=== History ===

In the middle of the 17th century, [[Samuel Morland]] introduced an early form of columnar transposition. {{Citation needed|date=May 2025}} The technique was developed further over the next two centuries and became widely used in the late 19th and 20th centuries, notably by French military services, Japanese diplomats, and Soviet intelligence agencies.

John Falconer's ''[[Cryptomenysis Patefacta]]'' (1685) contains one of the earliest known English-language explanations of a keyed columnar transposition. Falconer gives no account of the cipher's origin, but he does explain how to write the plaintext into a rectangular grid, pad the final row with null letters, and extract the columns in a secret order determined by a keyword.<ref name="Falconer1685">{{cite book |last=Falconer |first=John |title=Cryptomenysis Patefacta; or, ''The Art of Secret Information Disclosed Without a Key'' |location=London |publisher=Daniel Brown|year=1685 |url=https://archive.org/details/cryptomenysispat00falc/page/62/mode/2up |page=62}}</ref>

Even more importantly, Falconer offers a worked method of cryptanalysis. He shows that an analyst can test different grid heights and reorder the columns by trial and error until readable text emerges, noting that the cipher preserves normal letters frequencies and is therefore susceptible to detection. He indicates that such letter frequencies can be used to detect the likely language of the text, even without knowing its contents, as letter frequencies differ between languages. Falconer does not discuss double transposition or how to solve ciphers where nulls are not provided in the final column, which suggests these were not widespread at the time.

Columnar transposition was subsequently incorporated into more elaborate systems—most famously the double transposition used by French military and diplomatic services, Japanese and German ciphers of the First and Second World Wars, and Soviet agents—remaining in serious use into the 1950s.  Falconer’s analysis anticipates many of the systematic attacks later refined against those double-stage versions, making ''Cryptomenysis Patefacta'' a landmark in the early literature of cryptanalysis.