ADFGVX cipher
Encyclopedia
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 modified Polybius square
with a single columnar transposition. The cipher is named after the six possible letters used in the ciphertext: A, D, F, G, V and X. These letters were chosen deliberately because they sound very different from each other when transmitted via Morse code
. The intention was to reduce the possibility of operator error. Nebel designed the cipher to provide an army on the move with encryption more convenient than trench code
s but still secure. In fact, the Germans believed the ADFGVX cipher was unbreakable.
message, "Attack at once". First, a secret mixed alphabet
is filled into a 5 × 5 Polybius square
, like so:
i and j have been combined, to make the alphabet fit into a 5 × 5 grid.
Using this square, the message is converted to fractionated form:
a t t a c k a t o n c e
AF AD AD AF GF DX AF AD DF FX GF XF
Next, the fractionated message is subject to a columnar transposition. We write out the message in rows under a transposition key (here, "CARGO"):
C A R G O
_________
A F A D A
D A F G F
D X A F A
D D F F X
G F X F X
Next, we sort the letters alphabetically in the transposition key (changing CARGO to ACGOR), rearranging the columns beneath the letters along with the letters themselves:
A C G O R
_________
F A D A A
A D G F F
X D F A A
D D F X F
F G F X X
Then it is read off in columns, in keyword order, yielding the ciphertext
:
FAXDF ADDDG DGFFF AFAXX AFAFX
In practice, the transposition keys were about two dozen characters long. Long messages sent in the ADFGX cipher were broken into sets of messages of different and irregular lengths, thus making it invulnerable to multiple anagramming. Both the transposition keys and fractionation keys were changed daily.
s from 0 to 9. This mainly had the effect of considerably shortening messages which contained a large number of figures.
by French
Army Lieutenant
Georges Painvin
. The work was exceptionally difficult by the standards of classical cryptography, and Painvin became physically ill during it. His method of solution relied on finding messages with stereotyped beginnings, which would fractionate the same, then form similar patterns in the positions in the ciphertext that had corresponded to column headings in the transposition table. (Considerable statistical analysis was required after this step had been reached — all done by hand.) This meant it was only effective during times of very high traffic — but, fortunately for the cryptanalysts, that was also when the most important messages were sent.
However, that was not the only trick Painvin used to crack the ADFGX cipher. Due to the way the message was enciphered, he knew that each column consisted entirely of either letter coordinates taken from the top of the Polybius Square, or from the left of the Square, but not a mixture of the two. He also knew that after substitution, but before transposition, the columns would alternately consist entirely of "top" and "side" letters. One of the characteristics of frequency analysis of letters is that while the distributions of individual letters may vary widely from the norm, the law of averages
dictates that groups of letters vary less. With the ADFGX cipher, each "side" letter or "top" letter is associated with five plaintext letters. In the example above, the "side" letter "D" is associated with the plaintext letters "d h o z k", while the "top" letter "D" is associated with the plaintext letters "t h f j r". Since these two groups of five letters have different cumulative frequency distributions, then a frequency analysis of the "D" letter in columns consisting of "side" letters will have a distinctively different result from those of the "D" letter in columns consisting of "top" letters. This trick allowed Painvin to tentatively identify which columns consisted of "side" letters and which columns consisted of "top" letters. He could then pair them up and perform a frequency analysis on the pairings to see if they were noise, or real pairings that corresponded to plaintext letters. Once he had the proper pairings, he could then use frequency analysis to figure out the actual plaintext letters. The result was still transposed, but at that point all he had to do was unscramble a simple transposition. Once he determined the transposition scheme for one message, he would then be able to crack any other message enciphered with the same transposition key.
Painvin broke the ADFGX cipher in April 1918, a few weeks after the Germans launched their Spring Offensive
. As a direct result, the French army discovered where Ludendorff
intended to attack. The French concentrated their forces at that point and stopped the Spring Offensive.
The ADFGX and ADFGVX ciphers are now regarded as insecure.
Note: the claim that Painvin's breaking of the ADFGX cipher stopped the German Spring Offensive
of 1918, while frequently made, is disputed by some. In his 2002 review of Sophie de Lastours' book on this subject, La France gagne la guerre des codes secrets 1914-1918, in the Journal of Intelligence History, (Journal of Intelligence History: volume 2, Number 2, Winter 2002) Hilmar-Detlef Brückner states:
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the ADFGVX cipher was a field cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
used by the German
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
Army
Army
An army An army An army (from Latin arma "arms, weapons" via Old French armée, "armed" (feminine), in the broadest sense, is the land-based military of a nation or state. It may also include other branches of the military such as the air force via means of aviation corps...
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...
. 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
Transposition cipher
In cryptography, a transposition cipher is a method of encryption by which the positions held by units of plaintext 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...
which combined a modified 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...
with a single columnar transposition. The cipher is named after the six possible letters used in the ciphertext: A, D, F, G, V and X. These letters were chosen deliberately because they sound very different from each other when transmitted via 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...
. The intention was to reduce the possibility of operator error. Nebel designed the cipher to provide an army on the move with encryption more convenient than trench code
Trench code
In cryptography, trench codes were codes used for secrecy by field armies in World War I. A reasonably-designed code is generally more difficult to crack than a classical cipher, but of course suffers from the difficulty of preparing, distributing, and protecting codebooks.However, by the middle of...
s but still secure. In fact, the Germans believed the ADFGVX cipher was unbreakable.
Operation of ADFGX
Suppose we need to send the plaintextPlaintext
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....
message, "Attack at once". First, a secret mixed alphabet
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...
is filled into a 5 × 5 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...
, like so:
| A | D | F | G | X | |
|---|---|---|---|---|---|
| A | b | t | a | l | p |
| D | d | h | o | z | k |
| F | q | f | v | s | n |
| G | g | j | c | u | x |
| X | m | r | e | w | y |
i and j have been combined, to make the alphabet fit into a 5 × 5 grid.
Using this square, the message is converted to fractionated form:
a t t a c k a t o n c e
AF AD AD AF GF DX AF AD DF FX GF XF
Next, the fractionated message is subject to a columnar transposition. We write out the message in rows under a transposition key (here, "CARGO"):
C A R G O
_________
A F A D A
D A F G F
D X A F A
D D F F X
G F X F X
Next, we sort the letters alphabetically in the transposition key (changing CARGO to ACGOR), rearranging the columns beneath the letters along with the letters themselves:
A C G O R
_________
F A D A A
A D G F F
X D F A A
D D F X F
F G F X X
Then it is read off in columns, in keyword order, yielding 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...
:
FAXDF ADDDG DGFFF AFAXX AFAFX
In practice, the transposition keys were about two dozen characters long. Long messages sent in the ADFGX cipher were broken into sets of messages of different and irregular lengths, thus making it invulnerable to multiple anagramming. Both the transposition keys and fractionation keys were changed daily.
ADFGVX
In June 1918, an additional letter, V, was added to the cipher. This expanded the grid to 6 × 6, allowing 36 characters to be used. This allowed the full alphabet (instead of combining I and J), plus the digitNumerical digit
A digit is a symbol used in combinations to represent numbers in positional numeral systems. The name "digit" comes from the fact that the 10 digits of the hands correspond to the 10 symbols of the common base 10 number system, i.e...
s from 0 to 9. This mainly had the effect of considerably shortening messages which contained a large number of figures.
Cryptanalysis
ADFGVX was cryptanalysedCryptanalysis
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 French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
Army Lieutenant
Lieutenant
A lieutenant is a junior commissioned officer in many nations' armed forces. Typically, the rank of lieutenant in naval usage, while still a junior officer rank, is senior to the army rank...
Georges Painvin
Georges Painvin
Georges Jean Painvin was a French cryptanalyst during the First World War. His most notable achievement was the breaking of the ADFGVX cipher in June 1918.Before the First World War, Painvin taught paleontology and geology...
. The work was exceptionally difficult by the standards of classical cryptography, and Painvin became physically ill during it. His method of solution relied on finding messages with stereotyped beginnings, which would fractionate the same, then form similar patterns in the positions in the ciphertext that had corresponded to column headings in the transposition table. (Considerable statistical analysis was required after this step had been reached — all done by hand.) This meant it was only effective during times of very high traffic — but, fortunately for the cryptanalysts, that was also when the most important messages were sent.
However, that was not the only trick Painvin used to crack the ADFGX cipher. Due to the way the message was enciphered, he knew that each column consisted entirely of either letter coordinates taken from the top of the Polybius Square, or from the left of the Square, but not a mixture of the two. He also knew that after substitution, but before transposition, the columns would alternately consist entirely of "top" and "side" letters. One of the characteristics of frequency analysis of letters is that while the distributions of individual letters may vary widely from the norm, the law of averages
Law of averages
The law of averages is a lay term used to express a belief that outcomes of a random event will "even out" within a small sample.As invoked in everyday life, the "law" usually reflects bad statistics or wishful thinking rather than any mathematical principle...
dictates that groups of letters vary less. With the ADFGX cipher, each "side" letter or "top" letter is associated with five plaintext letters. In the example above, the "side" letter "D" is associated with the plaintext letters "d h o z k", while the "top" letter "D" is associated with the plaintext letters "t h f j r". Since these two groups of five letters have different cumulative frequency distributions, then a frequency analysis of the "D" letter in columns consisting of "side" letters will have a distinctively different result from those of the "D" letter in columns consisting of "top" letters. This trick allowed Painvin to tentatively identify which columns consisted of "side" letters and which columns consisted of "top" letters. He could then pair them up and perform a frequency analysis on the pairings to see if they were noise, or real pairings that corresponded to plaintext letters. Once he had the proper pairings, he could then use frequency analysis to figure out the actual plaintext letters. The result was still transposed, but at that point all he had to do was unscramble a simple transposition. Once he determined the transposition scheme for one message, he would then be able to crack any other message enciphered with the same transposition key.
Painvin broke the ADFGX cipher in April 1918, a few weeks after the Germans launched their Spring Offensive
Spring Offensive
The 1918 Spring Offensive or Kaiserschlacht , also known as the Ludendorff Offensive, was a series of German attacks along the Western Front during World War I, beginning on 21 March 1918, which marked the deepest advances by either side since 1914...
. As a direct result, the French army discovered where Ludendorff
Erich Ludendorff
Erich Friedrich Wilhelm Ludendorff was a German general, victor of Liège and of the Battle of Tannenberg...
intended to attack. The French concentrated their forces at that point and stopped the Spring Offensive.
The ADFGX and ADFGVX ciphers are now regarded as insecure.
Note: the claim that Painvin's breaking of the ADFGX cipher stopped the German Spring Offensive
Spring Offensive
The 1918 Spring Offensive or Kaiserschlacht , also known as the Ludendorff Offensive, was a series of German attacks along the Western Front during World War I, beginning on 21 March 1918, which marked the deepest advances by either side since 1914...
of 1918, while frequently made, is disputed by some. In his 2002 review of Sophie de Lastours' book on this subject, La France gagne la guerre des codes secrets 1914-1918, in the Journal of Intelligence History, (Journal of Intelligence History: volume 2, Number 2, Winter 2002) Hilmar-Detlef Brückner states:
Regrettably, Sophie de Lastours subscribes to the traditional French view that the solving of a German ADFGVX-telegram by Painvin at the beginning of June 1918 was decisive for the Allied victory in the First World War because it gave timely warning of a forthcoming German offensive meant to reach Paris and to inflict a critical defeat on the Allies. However, it has been known for many years, that the German Gneisenau attack of 11 June was staged to induce the French High Command to rush in reserves from the area up north, where the Germans intended to attack later on.
To achieve this, its aim had to be grossly exaggerated. This the German High Command did by spreading rumors that the attack was heading for Paris and beyond; disinformation proved effective then - and apparently still does. But the German offensive was not successful because the French had a sufficient number of reserves at hand to stop the assault and did not need to bring in additional reinforcements.
Moreover, it is usually overlooked that the basic version of the ADFGVX cipher had been particularly created for the German spring offensive in 1918, meant to deal the Allies a devastating blow. It was hoped that the cipher ADFGX would protect German communications against Allied cryptographers during the assault and this is what it indeed did.
Telegrams in ADFGX appeared for the first time on 5 March, the German attack started on 21 March. When Painvin presented his first solution of the code on 5 April, the German offensive had already petered out.