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 (see the section on "Detection and cryptanalysis" below), 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 (see below) 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
(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, (pronounced or ) 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
… excerpt ends here. Continue reading the full article.
