Transposition cipher
In cryptography, a transposition cipher is a method of encryption which scrambles the positions of characters without changing the characters themselves. Transposition ciphers reorder units of plaintext 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.
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
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, 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', the encrypter writes out: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
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, the cipherer writes out: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, using the same plaintext that we used for rail fence: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 cipher text of:
EJXCTEDEC DAEWRIORF EONALEVSE
Route ciphers have many more keys than a rail fence. In fact, for messages of reasonable length, the number of possible keys is potentially too great to be enumerated even by modern machinery. However, not all keys are equally good. Badly chosen routes will leave excessive chunks of plaintext, or text simply reversed, and this will give cryptanalysts a clue as to the routes.
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 is 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 and the message. 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, 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 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. 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 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.
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.