August 7, 2009
The ADFGX cipher, and its later sibling the ADFGVX cipher, were field ciphers used by the German Army during the First World War. It is called ADFGX because those are the only letters that appear in the ciphertext, chosen to reduce operator error during Morse code transmission because they sound so different.
ADFGX is a fractionating transposition cipher invented by German Army Colonel Fritz Nebel in March 1918, and famously cryptanalyzed by French Army Lieutenant Georges Painvin in April 1918. The French version of the story is that Painvin broke the cipher in a single, sustained forty-eight hour session, reading a message that suggested where Ludendorff intended to attack, allowing the French to foil the attack and win the war; the German version differs, but the winners write the history.
ADFGX works in two phases. The first uses a 5×5 polybius square to represent the alphabet, with I and J combined:
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
The plaintext message is converted to ciphertext by noting the row and column headers where each character is located; for instance:
P R O G R A M M I N G P R A X I S
AX XD DF GA XD AF XA XA GD FX GA AX XD AF GX GD FG
Then, the partially-enciphered message is subject to columnar transposition; the original German version of the cipher added nulls at the end of short columns, but we will eschew this method in favor of the normal columnar transposition. Cryptographically, this is a rather strong method, especially in the days when cryptanalysis was done without aid of computers, because the two ciphertext characters that represent a single plaintext character are split, or fractionated, from one another. Using the transposition keyword TULIP, the transposition worked like this:
T U L I P
3 4 1 0 2
A X X D D
F G A X D
A F X A X
A G D F X
G A A X X
D A F G X
G D F G
Then the columns are read off in order: DXAFXGGXAXDAFFDDXXXXAFAAGDGXGFGAAD.
Decipherment is the inverse operation.
There are two keys, the polybius square and the transposition. German doctrine called for the square to be changed weekly and the transposition key to be changed daily, and use of the ADFGX cipher was restricted to high-level communications only. Painvin attacked the cipher by comparing multiple messages with identical beginnings, from which he was able to work out the transposition matrix (he kept swapping columns until a frequency count of digrams had the same shape as German-army plain-text), then he solved the remaining monoalphabetic substitution cipher on digrams by frequency analysis. Though the cipher is no longer secure, the combination of fractionated substitution and transposition is still used as the basis of some modern ciphers, including DES.
Your task is to implement encryption and decryption of the ADFGX cipher. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.
With this exercise, we return to the original arrangement in which the solution appears on the same day as the exercise. Delaying the solution makes the blog harder to maintain, and confuses readers who don't know where to write their comments. Solutions that appeared in the last few weeks have been merged with their corresponding exercises; in particular, the solution to Lenstra's Algorithm that was promised for today has been posted along with the original exercise.
Pages: 1 2