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.[1]
From Kahn's 'The CodeBreakers':
"It was no less clear to the Allies that Germany planned to launch a
climactic offensive in the spring. There were many signs—the new cipher itself was one. The question was: Where and
when would the actual blow fall? The German high command, recognizing the incalculable military value of surprise,
shrouded its plans in the tightest secrecy. Artillery was brought up in concealment; feints were flung out here
and there along the entire front to keep the Allies off balance; the ADFGVX cipher, which had reportedly been
chosen from among many candidates by a conference of German cipher specialists, constituted an element in this
overall security, as did the new Schliis-selheft. The Allies bent every effort and tapped every source of
information to find out the time and place of the real assault."[2]
Georges Painvin was the French cryptanalyst tasked with cracking the ADFGVX cipher. The intelligence he provided
was vital to the French war effort, particularly in saving Paris in 1918:
"At midnight on June 9 the
front from Montdidier to Compiegne erupted in a fierce, pelting
hurricane of high-explosive, shrapnel, and gas shells. For three hours
a German artillery concentration that averaged one gun for no more than
ten yards of front poured a continual stream of fire onto the French
positions—and Ludendorff's urgent demand for ammunition became
clear. But this time, for the first time since Ludendorff began his
stupendous series of triumphs, there was no surprise. Painvin's manna
had saved the French."[2]
The Algorithm
The 'key' for a ADFGVX cipher is a 'key
square' and a key word. e.g.
p h 0 q g 6 4 m e a 1 y l 2 n o f d x k r 3 c v s 5 z w 7 b j 9 u t i 8
The key square is a 6 by 6 square containing all the letters and the
numbers 0 - 9. The key word is any word e.g. GERMAN
Step 1. Build a table like the following with the key square. This is known as a polybius square.
A D F G V X A | p h 0 q g 6 D | 4 m e a 1 y F | l 2 n o f d G | x k r 3 c v V | s 5 z w 7 b X | j 9 u t i 8
Step 2. Encode the plaintext using this matrix, e.g. 'attack' -> 'DG XG XG DG GV GD'
The ciphertext is now twice as long as the original plaintext. Note
that so far, it is just a simple substitution cipher, and trivial to
break.
Step 3. Write the code word with the enciphered plaintext underneath e.g.
G E R M A N
D G X G X G
D G G V G D
Step 4. Sort the code word alphabetically, moving the columns as you go. (this is the fractionating step)
A E G M N R
X G D G G X
G G D V D G
Step 5. Read the final ciphertext off in columns. (this is the transposition step)
-> XG GG DD GV GD XG
Javascript Example
The keysquare in this example has been written on a single line. To convert to the cube shape,
simply write the first 6 characters on the first line, the second six characters on the second line etc.
Plaintext
keysquare =
keyword =
Ciphertext
Cryptanalysis
Cryptanalysis of the ADFGVX cipher is discussed in a paper called "Cryptanalysis of ADFGVX encipherment systems" in
Proceedings of CRYPTO 84 on Advances in cryptology. Unfotunately this paper is not available
to the public, however an extended abstract is available
here.
The steps in cryptanalysing this cipher are the following:
determine the length of the key word
try to rearrange the rows in the correct order
solve the substitution cipher normally
The naive brute force approach would be to cycle through all possible
key word lengths and column orderings for each key word length, and try
to solve the substitution step for each of the different
combinations, stopping when we find a good solution. This would take an
exceedingly long time however, as there are a lot of combinations of
key word length and column order that have to be tested. There are,
however, a few statistical tips and tricks we can employ to reduce our
workload. The first is the
Code
I have included here some C code that does encryption and decryption of
the ADFGVX cipher. It is only meant to show the working of the
algorithm, not be a final polished solution.
ADFGVX_encrypt.c ADFGVX_decrypt.c
There is also some code that utilises a markov model to automatically
solve a ADFGVX cipher. Note that very short ciphertexts may
not be
cryptanalysed properly. The longer the ciphertext the better, several
hundred characters ideal.
ADFGVX_crack.c
References
[1] Wikipedia
has a good description of the encryption/decryption process, history
and cryptanalysis of this algorithm
[2] Kahn, D (1973) The CodeBreakers. Macmillan: New York
Simon Singh's 'The Code Book' is an excellent introduction to ciphers
and codes, and includes a section on ADFGVX ciphers.
Singh, Simon (2000). The
Code Book: The Science of Secrecy from Ancient Egypt to Quantum
Cryptography. ISBN 0-385-49532-3.