*In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext (which are
*commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a
*permutation of the plaintext. That is, the order of the units is changed (the plaintext is reordered). Mathematically a bijective function
*is used on the characters' positions to encrypt and ani nverse function to decrypt.
*Following are some implementations.
*Contents
*1 Rail Fence cipher
*2 Route cipher
*3 Columnar transposition
*4 Myszkowski transposition
*5 Detection and cryptanalysis
*6 References
*
*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. 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.)
*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 forr ail 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.
*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 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".
*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), 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
*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.
*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 identical,l yTOMATO 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
*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