HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, a transposition cipher is a method of encryption which scrambles the positions of characters (''transposition'') without changing the characters themselves. Transposition ciphers reorder units of
plaintext In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
(typically characters or groups of characters) according to a regular system to produce a
ciphertext In cryptography, ciphertext or cyphertext 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 ...
which is a
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of the plaintext. They differ from
substitution ciphers In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, tri ...
, 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 In cryptography, the ADFGVX cipher was a manually applied field cipher used by the Imperial German Army during World War I. It was used to transmit messages secretly using wireless telegraphy. ADFGVX was in fact an extension of an earlier cipher ca ...
or complex high-quality encryption methods like the modern
Advanced Encryption Standard The Advanced Encryption Standard (AES), also known by its original name Rijndael (), is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001. AES is a variant ...
(AES).


General principle

Plaintexts can be rearranged into a ciphertext using a
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
, scrambling the order of characters like the shuffled pieces of a
jigsaw puzzle A jigsaw puzzle is a tiling puzzle that requires the assembly of often irregularly shaped interlocking and mosaiced pieces, each of which typically has a portion of a picture. When assembled, the puzzle pieces produce a complete picture. In th ...
. 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 downwards and diagonally 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 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 In cryptography, a scytale (; also transliterated skytale, grc, σκυτάλη ''skutálē'' "baton, cylinder", also ''skútalon'') is a tool used to perform a transposition cipher, consisting of a cylinder with a strip of parchment wound aro ...
, (pronounced "SKIT-uhl-ee") a mechanical system of producing a transposition cipher used by the
ancient Greeks Ancient Greece ( el, Ἑλλάς, Hellás) was a northeastern Mediterranean civilization, existing from the Greek Dark Ages of the 12th–9th centuries BC to the end of classical antiquity ( AD 600), that comprised a loose collection of cultu ...
. 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 The American Civil War (April 12, 1861 – May 26, 1865; also known by other names) was a civil war in the United States. It was fought between the Union ("the North") and the Confederacy ("the South"), the latter formed by states th ...
. 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 In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...
. 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 keyword 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 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 To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then they can write the message out in columns again, then re-order the columns by reforming the key word. In a variation, the message is blocked into segments that are the key length long and to each segment the same permutation (given by the key) is applied. This is equivalent to a columnar transposition where the read-out is by rows instead of columns. Columnar transposition continued to be used for serious purposes as a component of more complex ciphers at least into the 1950s.


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 An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
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, , 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 (28 July 1914 11 November 1918), often abbreviated as WWI, was one of the deadliest global conflicts in history. Belligerents included much of Europe, the Russian Empire, the United States, and the Ottoman Empire, with fightin ...
, 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'', 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 may refer to: Resistance groups * Maquis (World War II), predominantly rural guerrilla bands of the French Resistance * Spanish Maquis, guerrillas who fought against Francoist Spain in the aftermath of the Spanish Civil War * The network ...
and the British
Special Operations Executive The Special Operations Executive (SOE) was a secret British World War II organisation. It was officially formed on 22 July 1940 under Minister of Economic Warfare Hugh Dalton, from the amalgamation of three existing secret organisations. Its pu ...
(SOE), which was in charge of managing underground activities in Europe. It was also used by agents of the American
Office of Strategic Services The Office of Strategic Services (OSS) was the intelligence agency of the United States during World War II. The OSS was formed as an agency of the Joint Chiefs of Staff (JCS) to coordinate espionage activities behind enemy lines for all branc ...
and as an emergency cipher for the German Army and Navy. Until the invention of the
VIC cipher Vic (; es, Vic or Pancracio Celdrán (2004). Diccionario de topónimos españoles y sus gentilicios (5ª edición). Madrid: Espasa Calpe. p. 843. ISBN 978-84-670-3054-9. «Vic o Vich (viquense, vigitano, vigatán, ausense, ausetano, ausonense): ...
, double transposition was generally regarded as the most complicated cipher that an agent could operate reliably under difficult field conditions.


Cryptanalysis

The double transposition cipher can be treated as a single transposition with a key as long as the product of the lengths of the two keys. In late 2013, a double transposition challenge, regarded by its author as undecipherable, was solved by George Lasry using a divide-and-conquer approach where each transposition was attacked individually.


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

A disrupted transposition cipher further complicates the transposition pattern with irregular filling of the rows of the matrix, i.e. with some spaces intentionally left blank (or blackened out like in the
Rasterschlüssel 44 Rasterschlüssel 44 (abbr. RS 44) was a manual cipher system, used by the German Wehrmacht during the Second World War. The cipher was designed by the astronomer and sometime cryptographer Walter Fricke while working as a conscript in Section IIb ...
), or filled later with either another part of the plaintext or random letters.


Comb approach

One possible algorithm is to start a new row whenever the plaintext reaches a password character. For example, F O R E V E R J I G S A W < Key 4 8 9 2 12 3 10 7 6 5 11 1 13 Blanks after no.: C O M P L I C A T E S T * 1 H E T R * * * * * * * * * 2 A N S P O S * * * * * * * 3 I * * * * * * * * * * * * 4 T I O N P A T T E R * * * 5 N L I K E A C O M * * * * 6 B _ _ _ _ _ _ _ * * * * * 7 The columns are then taken off as per regular columnar transposition: TPRPN, KISAA, CHAIT, NBERT, EMATO, etc.


Numerical sequence approach

Another simple option would be to use a password that places blanks according to its number sequence. E.g. "SECRET" would be decoded to a sequence of "5,2,1,4,3,6" and cross out the 5th field of the matrix, then count again and cross out the second field, etc. The following example would be a matrix set up for columnar transposition with the columnar key "CRYPTO" and filled with crossed out fields according to the disruption key "SECRET" (marked with an asterisk), whereafter the message "we are discovered, flee at once" is placed in the leftover spaces. The resulting ciphertext (the columns read according to the transposition key) is "WCEEO ERET RIVFC EODN SELE ADA". C R Y P T O 1 4 6 3 5 2 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 *


Grilles

Another form of transposition cipher uses ''grilles'', or physical masks with cut-outs. 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 (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
by doing a frequency count. If the ciphertext exhibits a
frequency distribution In statistics, the frequency (or absolute frequency) of an event i is the number n_i of times the observation has occurred/recorded in an experiment or study. These frequencies are often depicted graphically or in tabular form. Types The cumula ...
very similar to plaintext, it is most likely a transposition. In general, transposition methods are vulnerable to
anagram An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once. For example, the word ''anagram'' itself can be rearranged into ''nag a ram'', also the word ...
ming—sliding pieces of ciphertext around, then looking for sections that look like anagrams of words in English or whatever language the plaintext was written in, and solving the anagrams. Once such anagrams have been found, they reveal information about the transposition pattern, and can consequently be extended. Simpler transpositions 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 In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to gene ...
s and hill-climbing algorithms. There are several specific methods for attacking messages encoded using a transposition cipher. These include: #
Known-plaintext attack The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secr ...
: Using known or guessed parts of the plaintext (e.g. names, places, dates, numbers, phrases) to assist in reverse-engineering the likely order of columns used to carry out the transposition and/or the likely topic of the plaintext. #
Brute-force attack In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correc ...
: If keys are derived from dictionary words or phrases from books or other publicly available sources, it may be possible to brute-force the solution by attempting billions of possible words, word combinations, and phrases as keys. # Depth attack: If two or more messages of the same length are encoded with the same keys, the messages can be aligned and anagrammed until the messages show meaningful text in the same places, without needing to know the transposition steps that have taken place. # Statistical attack: Statistics about the frequency of 2-letter, 3-letter, etc. combinations in a language can be used to inform a scoring function in an algorithm that gradually reverses possible transpositions based on which changes would produce the most likely combinations. For example, the 2-letter pair QU is more common than QT in English text, so a cryptanalyst will attempt transpositions that place QU together. 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." A cipher used by the
Zodiac Killer The Zodiac Killer is the pseudonym of an unidentified serial killer who operated in Northern California in the late 1960s. The case has been described as the most famous unsolved murder case in American history. It became a fixture of popular c ...
, called "Z-340", organized into triangular sections with substitution of 63 different symbols for the letters and diagonal "knight move" transposition, remained unsolved for over 51 years, until an international team of private citizens cracked it on December 5, 2020, using specialized software.


Combinations

Transposition is often combined with other techniques such as evaluation methods. For example, a simple
substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, trip ...
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 two or more ciphertext symbols. For example, the plaintext alphabet could be written out in a grid, and every letter in the message replaced by its co-ordinates (see
Polybius square The Polybius square, also known as the Polybius checkerboard, is a device invented by the ancient Greeks Cleoxenus and Democleitus, and made famous by the historian and scholar Polybius. The device is used for fractionating plaintext characters s ...
and Straddling checkerboard). Another method of fractionation is to simply convert the message to
Morse code Morse code is a method used in telecommunication to encode text characters as standardized sequences of two different signal durations, called ''dots'' and ''dashes'', or ''dits'' and ''dahs''. Morse code is named after Samuel Morse, one of ...
, with a symbol for spaces as well as dots and dashes. James Lyons
"Fractionated Morse Cipher"
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 Diffusion is the net movement of anything (for example, atoms, ions, molecules, energy) generally from a region of higher concentration to a region of lower concentration. Diffusion is driven by a gradient in Gibbs free energy or chemical p ...
. Examples of ciphers that combine fractionation and transposition include the
bifid cipher In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion. It was invented around 1901 by Felix Delastelle. Operation First, a mixed alphabet Poly ...
, the
trifid cipher The trifid cipher is a classical cipher invented by Félix Delastelle and described in 1902. Extending the principles of Delastelle's earlier bifid cipher, it combines the techniques of fractionation and transposition to achieve a certain amount of ...
, the
ADFGVX cipher In cryptography, the ADFGVX cipher was a manually applied field cipher used by the Imperial German Army during World War I. It was used to transmit messages secretly using wireless telegraphy. ADFGVX was in fact an extension of an earlier cipher ca ...
and the
VIC cipher Vic (; es, Vic or Pancracio Celdrán (2004). Diccionario de topónimos españoles y sus gentilicios (5ª edición). Madrid: Espasa Calpe. p. 843. ISBN 978-84-670-3054-9. «Vic o Vich (viquense, vigitano, vigatán, ausense, ausetano, ausonense): ...
. 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 In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified cryptographic primitive, elementary components in the design of many cryptographic protocols and ...
s use more complex forms of transposition related to this simple idea.


See also

*
Substitution cipher In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters (the most common), pairs of letters, trip ...
*
Ban (unit) The hartley (symbol Hart), also called a ban, or a dit (short for decimal digit), is a logarithmic unit that measures information or entropy, based on base 10 logarithms and powers of 10. One hartley is the information content of an event if th ...
*
Topics in cryptography The following outline is provided as an overview of and topical guide to cryptography: Cryptography (or cryptology) – practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer scienc ...


Notes


References

*Kahn, David. The Codebreakers: The Story of Secret Writing. Rev Sub. Scribner, 1996. *Yardley, Herbert. The American Black Chamber. Bobbs-Merrill, 1931. {{Cryptography navbox , classical Classical ciphers Permutations