Transposition cipher
In classical cryptology, a transposition cipher encodes a message by reordering the plaintext in some definite way. Mathematically, it can be described as applying some sort of bijective function. The receiver decodes the message using the reordering in the opposite way, setting the ordering right again. Mathematically this means using the inverse function of the original encoding function.
A simple kind of transposition cipher writes the message into a rectangle by rows and reads it out by columns.
Asimplekin
doftranspo
sitionciph
erwritesth
emessagein
toarectang
lebyrowsan
dreadsitou
tbycolumns
Adsee tldts oirmo erbif tweab eymti rsrya cproi serdo lanta cosle ncegt wiuks iseas tmipp tinao nnohh ngnus. This cipher is often complicated by permuting the rows and columns.
Another cipher uses a grille. This is a square with holes in it such that each cell in the square appears in no more than one position when the grille is rotated to each of its four positions. As much message as will fit in the grille is written, then it is turned to another position and more message is written.
Scytale
One of the earliest known transposition ciphers - and indeed, earliest known cipher of any type -- the scytale was a simple mechanical way to transpose a text, using a baton as the key. See: scytale for more information.
Rail fence
In the rail fence cipher, the plaintext is written downwards on successive "rails" of an imaginary fence, starting a new column when we get to the top. The message is then read off in rows. For example, if we have 3 "rails" and a message of 'WE ARE DISCOVERED. FLEE AT ONCE', the cipherer writes out:
| 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 extra odd letters at the end are "nulls", added to round off the pattern, or to confuse a cryptanalyst. Then reads off:
WRIOR FEOEE ESVEL ANJAD CEDET CXPQT
(Grouping into blocks of standard size, typically five, is an old device to help cipher clerks avoid errors).
Rail fence is not very strong; the number of practical keys is small enough that a cryptanalyst can try them all by hand.
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 and grid 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:
EJX CTE DEC DAE WRI ORF EON ALE VSE
(The clerk has broken this ciphertext up into blocks of three to help avoid errors).
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.
An interesting 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! See [1] and [2] for examples.
Columnar transposition
The standard columnar transposition consists of writing the key out as column headers, then writing the message out in successive rows beneath these headers (filling in any spare spaces with nulls), finally, the message is read off in columns, in alphabetical order of the headers. For example suppose we have a key of 'ZEBRAS' and a message of 'WE ARE DISCOVERED. FLEE AT ONCE'. We start with:
| Z | E | B |
R | A | S |
| 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 |
Then read it off as:
EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then he can write the message out in columns again, then re-order the columns by reforming the key word.
Columnar transposition continued to be used for seriosu purposes as a component of more complex ciphers at least into the 1950's.
Double transposition
A single columnar transpostion could be attacked by guessing possible column lengths, writing the message out in its columns (but in the wrong order, as the key is not yet known), and then looking for possible anagrams. Thus to make it stronger, a double transposition was often used. This is simply a columnar transposition applied twice, with two different keys of different (preferably relatively prime) length. Double transposition was generally regarded as the most complicated cipher that an agent could operate reliably under difficult field conditions. It was in actual use at least as late as World War II (e.g. see poem code).
Disrupted transposition
In a disrupted transposition, certain positions in a grid are blanked out, and not used when filling in the plaintext. This breaks up regular patterns and makes the cryptanalyst's job more difficult.
Detection and cryptanalysis
Since transposition does not affect the frequency of individual symbols, simple transposition can be easily detected by the cryptanalyst by doing a frequency count. If the ciphertext exhibits a frequency distribution very similar to plaintext, it is most likely a transposition. This can then often be attacked by anagramming - sliding pieces of ciphertext around, then looking for sections that look like anagrams of English words, and solving the anagrams. Once such anagrams have been found, they reveal information about the transposition pattern, and can consequently be extended.
Simpler transpositions also often suffer from the property that keys very close to the correct key will reveal long sections of legible plaintext interspersed by gibberish. Consequently such ciphers may be vulnerable to optimum seeking algorithms such as genetic algorithms.
Combinations
Transposition is often combined with other techniques. For example, a simple substitution cipher combined with a columnar transposition avoids the weakness of both. Replacing high frequency ciphertext symbols with high frequency plaintext letters does not reveal chunks of plaintext because of the transposition. Anagramming the transposition does not work because of the substitution. The technique is particularly powerful if combined with fractionation (see below). A disadvantage is that such ciphers are considerably more laborious and error prone than simpler ciphers.
Fractionation
Transposition is particularly effective when employed with fractionation - that is, a preliminary stage that divides each plaintext symbol into several ciphertext symbols. For example, the plaintext alphabet could be written out in a grid, then every letter in the message replaced by its co-ordinates. Another method of fractionation is to simply convert the message to Morse code, with a symbol for spaces as well as dots and dashes.
When such a fractionated message is transposed, the components of individual letters become widely separated in the message, thus achieving Claude E. Shannon's diffusion. Examples of ciphers that combine fractionation and transposition include the bifid cipher, the trifid cipher, the ADFGVX cipher and the VIC cipher.
See also:
Referenced By
List of combinatorics topics | Topics in cryptography
|
