Transposition cipher
Encyclopedia
In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, a transposition cipher is a method of encryption by which the positions held by units of plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....

 (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...

 constitutes a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 of the plaintext. That is, the order of the units is changed. Mathematically a bijective function is used on the characters' positions to encrypt and an inverse function
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...

 to decrypt.

Following are some implementations.

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 downwards on successive "rails" of an imaginary fence, then moving up when we get 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 cipherer 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 cipherer has broken this ciphertext up into blocks of five to help avoid errors.)

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:

EJXCTEDECDAEWRIORFEONALEVSE

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
American Civil War
The American Civil War was a civil war fought in the United States of America. In response to the election of Abraham Lincoln as President of the United States, 11 southern slave states declared their secession from the United States and formed the Confederate States of America ; the other 25...

. 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
Code (cryptography)
In cryptography, a code is a method used to transform a message into an obscured form, preventing those who do not possess special information, or key, required to apply the transform from understanding what is actually transmitted. The usual method is to use a codebook with a list of common...

. The cipher clerk may also add entire null words, which were often chosen to make the ciphertext humorous.

Columnar transposition

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 word 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 ZEBRAS and the message WE ARE DISCOVERED. FLEE AT ONCE. In a regular columnar transposition, we write this into the grid as:
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 (QKJEU) at the end. 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

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 serious purposes as a component of more complex ciphers at least into the 1950's.

Double transposition

A single columnar transposition 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 anagram
Anagram
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I'm a dot in place, Tom Marvolo Riddle = I am Lord Voldemort. Someone who...

s. Thus to make it stronger, a double transposition was often used. This is simply a columnar transposition applied twice. The same key can be used for both transpositions, or two different keys can be used.

As an example, we can take the result of the irregular columnar transposition in the previous section, and perform a second encryption with a different keyword, STRIPE, which gives the permutation "564231":
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

As before, this is read off columnwise to give the ciphertext:

CAEEN SOIAE DRLEF WEDRE EVTOC

If multiple messages of exactly the same length are encrypted using the same keys, they can be anagrammed simultaneously. This can lead to both recovery of the messages, and to recovery of the keys (so that every other message sent with those keys can be read).

During World War I
World War I
World War I , which was predominantly called the World War or the Great War from its occurrence until 1939, and the First World War or World War I thereafter, was a major war centred in Europe that began on 28 July 1914 and lasted until 11 November 1918...

, the German military used a double columnar transposition cipher, changing the keys infrequently. The system was regularly solved by the French, naming it Übchi, who were typically able to quickly find the keys once they'd intercepted a number of messages of the same length, which generally took only a few days. However, the French success became widely-known and, after a publication in Le Matin
Le Matin
Le Matin is a daily newspaper published by Edipresse in Lausanne, Switzerland. The French language tabloid has a circulation of 69,350 and a readership of 331,000.The Sunday edition Le Matin dimanche has a circulation of 207,945....

, the Germans changed to a new system on 18 November 1914.

During World War II, the double transposition cipher was used by Dutch Resistance groups, the French Maquis
Maquis (World War II)
The Maquis were the predominantly rural guerrilla bands of the French Resistance. Initially they were composed of men who had escaped into the mountains to avoid conscription into Vichy France's Service du travail obligatoire to provide forced labour for Germany...

 and the British Special Operations Executive
Special Operations Executive
The Special Operations Executive was a World War II organisation of the United Kingdom. It was officially formed by Prime Minister Winston Churchill and Minister of Economic Warfare Hugh Dalton on 22 July 1940, to conduct guerrilla warfare against the Axis powers and to instruct and aid local...

 (SOE), which was in charge of managing underground activities in Europe. It was also used by agents of the American Office of Strategic Services
Office of Strategic Services
The Office of Strategic Services was a United States intelligence agency formed during World War II. It was the wartime intelligence agency, and it was a predecessor of the Central Intelligence Agency...

 and as an emergency cipher for the German Army and Navy.

Until the invention of the VIC cipher
VIC cipher
The VIC cipher was a pencil and paper cipher used by the Soviet spy Reino Häyhänen, codenamed "VICTOR".It was arguably the most complex hand-operated cipher ever seen, when it was first discovered...

, double transposition was generally regarded as the most complicated cipher that an agent could operate reliably under difficult field conditions.

Myszkowski transposition

A variant form of columnar transposition, proposed by Émile Victor Théodore Myszkowski in 1902, requires a keyword with recurrent letters. In usual practice, subsequent occurrences of a keyword letter are treated as if the next letter in alphabetical order, e.g., the keyword TOMATO yields a numeric keystring of "532164."

In Myszkowski transposition, recurrent keyword letters are numbered identically, TOMATO yielding a keystring of "432143."

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

Plaintext columns with unique numbers are transcribed downward;
those with recurring numbers are transcribed left to right:

ROFOA CDTED SEEEA CWEIV RLENE

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.

Grilles

Another form of transposition cipher uses grilles, or physical masks with cut-outs, rather than a mathematical algorithm. This can produce a highly irregular transposition over the period specified by the size of the grille, but requires the correspondents to keep a physical key secret. Grilles were first proposed in 1550, and were still in military use for the first few months of World War One.

Detection and cryptanalysis

Since transposition does not affect the frequency of individual symbols, simple transposition can be easily detected by the cryptanalyst
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

 by doing a frequency count. If the ciphertext exhibits a frequency distribution
Frequency distribution
In statistics, a frequency distribution is an arrangement of the values that one or more variables take in a sample. Each entry in the table contains the frequency or count of the occurrences of values within a particular group or interval, and in this way, the table summarizes the distribution of...

 very similar to plaintext, it is most likely a transposition. This can then often be attacked by anagram
Anagram
An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I'm a dot in place, Tom Marvolo Riddle = I am Lord Voldemort. Someone who...

ming - 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 algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...

s.

A detailed description of the cryptanalysis of a German transposition cipher
can be found in chapter 7 of Herbert Yardley's "The American Black Chamber."

Combinations

Transposition is often combined with other techniques. For example, a simple substitution cipher
Substitution cipher
In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...

 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 (see Polybius square
Polybius square
In cryptography, the Polybius square, also known as the Polybius checkerboard, is a device invented by the Ancient Greek historian and scholar Polybius, described in , for fractionating plaintext characters so that they can be represented by a smaller set of symbols.-Basic form :The original square...

 and Straddling checkerboard
Straddling checkerboard
In cryptography, a straddling checkerboard is a device for converting an alphabetic plaintext into digits whilst simultaneously achieving fractionation and data compression relative to other schemes using digits...

). Another method of fractionation is to simply convert the message to Morse code
Morse code
Morse code is a method of transmitting textual information as a series of on-off tones, lights, or clicks that can be directly understood by a skilled listener or observer without special equipment...

, 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
Confusion and diffusion
In cryptography, confusion and diffusion are two properties of the operation of a secure cipher which were identified by Claude Shannon in his paper Communication Theory of Secrecy Systems, published in 1949....

. Examples of ciphers that combine fractionation and transposition include the bifid cipher
Bifid cipher
In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion...

, the trifid cipher
Trifid cipher
In classical cryptography, the trifid cipher is a cipher invented around 1901 by Felix Delastelle, which extends the concept of the bifid cipher to a third dimension, allowing each symbol to be fractionated into 3 elements instead of two...

, the ADFGVX cipher
ADFGVX cipher
In cryptography, the ADFGVX cipher was a field cipher used by the German Army during World War I. ADFGVX was in fact an extension of an earlier cipher called ADFGX. Invented by Colonel Fritz Nebel and introduced in March 1918, the cipher was a fractionating transposition cipher which combined a...

 and the VIC cipher
VIC cipher
The VIC cipher was a pencil and paper cipher used by the Soviet spy Reino Häyhänen, codenamed "VICTOR".It was arguably the most complex hand-operated cipher ever seen, when it was first discovered...

.

Another choice would be to replace each letter with its binary representation, transpose that, and then convert the new binary string into the corresponding ASCII characters. Looping the scrambling process on the binary string multiple times before changing it into ASCII characters would likely make it harder to break. Many modern block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

s use more complex forms of transposition related to this simple idea.

See also

  • Permutation cipher
    Permutation cipher
    In classical cryptography, a permutation cipher is a transposition cipher in which the key is a permutation.To apply a cipher, a random permutation of size e is generated...

  • Substitution cipher
    Substitution cipher
    In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...

  • Ban (information)
    Ban (information)
    A ban, sometimes called a hartley or a dit , is a logarithmic unit which measures information or entropy, based on base 10 logarithms and powers of 10, rather than the powers of 2 and base 2 logarithms which define the bit. As a bit corresponds to a binary digit, so a ban is a decimal digit...

     With Centiban table
  • Topics in cryptography
  • Numerical cipher
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK