Transposition cipher
In cryptography, a transposition cipher (also known as a permutation cipher) is a method of encryption which scrambles the positions of characters (transposition) without changing the characters themselves. Transposition ciphers reorder units of plaintext (typically characters or groups of characters) according to a regular system to produce a ciphertext which is a permutation of the plaintext. They differ from substitution ciphers, which do not change the position of units of plaintext but instead change the units themselves. Despite the difference between transposition and substitution operations, they are often combined, as in historical ciphers like the ADFGVX cipher or complex high-quality encryption methods like the modern Advanced Encryption Standard (AES).
General principle
Plaintexts can be rearranged into a ciphertext using a key, scrambling the order of characters like the shuffled pieces of a jigsaw puzzle. The resulting message is hard to decipher without the key because there are many ways the characters can be arranged.
For example, the plaintext “THIS IS WIKIPEDIA” could be encrypted to “TWDIP SIHII IKASE”. To decipher the encrypted message without the key, an attacker could try to guess possible words and phrases like DIATHESIS, DISSIPATE, WIDTH, etc., but it would take them some time to reconstruct the plaintext because there are many combinations of letters and words. By contrast, someone with the key could reconstruct the message easily:
C I P H E R Key
1 4 5 3 2 6 Sequence (key letters in alphabetical order)
T H I S I S Plaintext
W I K I P E
D I A * * *
Ciphertext by column:
#1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SE
Ciphertext in groups of 5 for readability:
TWDIP SIHII IKASE
In practice, a message this short and with a predictable keyword would be broken almost immediately with cryptanalysis techniques.
Transposition ciphers have several vulnerabilities, and small mistakes in the encipherment process can render the entire ciphertext meaningless.
However, given the right conditions—long messages (e.g., over 100–200 letters), unpredictable contents, unique keys per message, strong transposition methods, and so on—guessing the right words could be computationally impossible without further information. In their book on codebreaking historical ciphers, Elonka Dunin and Klaus Schmeh describe double columnar transposition as “one of the best manual ciphers known”.
Rail Fence cipher
The Rail Fence cipher is a form of transposition cipher that gets its name from the way in which it is encoded. In the rail fence cipher, the plaintext is written downward and diagonally on successive “rails” of an imaginary fence, then moves up when it gets to the bottom. The message is then read off in rows. For example, using three “rails” and a message of “WE ARE DISCOVERED FLEE AT ONCE”:
W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .
Then reads off:
WECRL TEERD SOEEF EAOCA IVDEN
(The cipher has broken this ciphertext up into blocks of five to help avoid errors. This is a common technique used to make the cipher more easily readable. The spacing is not related to spaces in the plaintext and so does not carry any information about the plaintext.)
Scytale
The rail fence cipher follows a pattern similar to that of the scytale, a mechanical system of producing a transposition cipher used by the ancient Greeks. The system consisted of a cylinder and a ribbon that was wrapped around the cylinder. The message to be encrypted was written on the coiled ribbon. The letters of the original message would be rearranged when the ribbon was uncoiled from the cylinder. However, the message was easily decrypted when the ribbon recoiled on a cylinder of the same diameter as the encrypting cylinder. Using the same example as before, if the cylinder has a radius such that only three letters can fit around its circumference:
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 .
In this example, the cylinder is running horizontally and the ribbon is wrapped around vertically. Hence, the cipherer then reads off:
WOEEV EAEAR RTEEO DDNIF CSLEC
Route cipher
In a route cipher, the plaintext is first written out in a grid of given dimensions, then read off in a pattern given in the key. For example:
W R I O R F E O E
E E S V E L A N J
A D C E D E T C X
The key might specify “spiral inwards, clockwise, starting from the top right”. That would give a ciphertext of:
EJXCTEDEC DAEWRIORF EONALEVSE
A variation of the route cipher was the Union Route Cipher, used by Union forces during the American Civil War. This worked much like an ordinary route cipher, but transposed whole words instead of individual letters. Because this would leave certain highly sensitive words exposed, such words would first be concealed by code. The cipher clerk may also add entire null words, which were often chosen to make the ciphertext humorous.
Columnar transposition
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 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”.
Regular transposition with padding:
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
Ciphertext:
EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
Irregular (no padding):
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
Ciphertext:
EVLNA CDTES EAROF ODEEC WIREE
Decryption
To decipher it, the recipient reconstructs the grid by dividing the message length by the key length. Then fill columns in the order given by the key.
History
In the middle of the 17th century, Samuel Morland introduced an early form of columnar transposition. John Falconer’s Cryptomenysis Patefacta (1685) contains one of the earliest known English-language explanations of a keyed columnar transposition. 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.
Double transposition
A single columnar transposition could be attacked by guessing possible column lengths and looking for anagrams. To make it stronger, a double transposition was often used: a columnar transposition applied twice.
Visual demonstration of double transposition
Example keys: JANEAUSTEN and AEROPLANES.
Step 1: The plaintext message is written into the first grid (which has the key JANEAUSTEN).
The columns are read off in alphabetical order according to the key, into the next grid (see step 2).
Step 2: The columns from step 1 are written into the second grid (which has the key AEROPLANES).
The columns are read off in alphabetical order according to the key, into the next grid (see step 3).
Step 3: The ciphertext is often written out in blocks of 5, e.g. RIAES NNELI EEIRP etc.
Another example
Using keyword STRIPE after an irregular columnar transposition:
5 6 4 2 3 1
E V L N A C
D T E S E A
R O F O D E
E C W I R E
E
Ciphertext:
CAEEN SOIAE DRLEF WEDRE EVTOC
This system was used in WWI (called Übchi) and WWII by resistance groups, SOE, OSS agents, and German forces.
Myszkowski transposition
Proposed by Émile Victor Théodore Myszkowski in 1902, using keywords with repeated letters. Example with TOMATO:
4 3 2 1 4 3
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
Result:
ROFOA CDTED SEEEA CWEIV RLENE
Disrupted transposition
A disrupted transposition cipher further complicates the transposition pattern with irregular filling of the rows.
Comb approach
Starts a new row once the plaintext reaches a column whose key number equals the current row number. Produces irregular row lengths.
Numerical sequence approach
Blanks are inserted based on a number sequence from a password. Example with CRYPTO and SECRET yields ciphertext:
WCEEO ERET RIVFC EODN SELE ADA
Grilles
Another form of transposition cipher uses grilles, or physical masks with cut-outs. This can produce a highly irregular transposition but requires keeping a physical key secret. Proposed in 1550, still used in WWI.
Detection and cryptanalysis
Since transposition does not affect symbol frequencies, transposition is easily detected with frequency analysis. Vulnerabilities include:
- Known-plaintext attack
- Brute-force attack
- Depth attack
- Statistical attack
Examples include 19th-century cryptanalysis of political telegrams, Yardley’s The American Black Chamber, and the Zodiac Killer’s Z-340 cipher (solved in 2020).
Combinations
Transposition is often combined with substitution, especially with fractionation, to strengthen the cipher.
Fractionation
Fractionation splits plaintext symbols into multiple parts (e.g., Polybius square, Morse code). Transposing these parts increases diffusion. Examples: bifid, trifid, ADFGVX, VIC cipher.
See also
- Substitution cipher
- Ban (unit)
- Topics in cryptography
References
- Kahn, David. The Codebreakers: The Story of Secret Writing. Scribner, 1996.
- Yardley, Herbert. The American Black Chamber. Bobbs-Merrill, 1931.