## Section4World War I Era Ciphers

We will discuss two ciphers important to World War I. Many other types of cipher techniques were used as well, but both of these had significant impacts on the outcome of the war.

The ADFGX cipher was a field cipher used by the German Army on the Western Front during World War I. ADFGVX was a later extension of this cipher. This cipher was invented by Lieutenant Fritz Nebel (1891–1977) and introduced in March 1918, shortly before a last major push by the German Army in WWI. Hard work by French cryptanalysts, especially George Painvin, allowed the decryption of some of these messages. This allowed the allied troops to determine where the Germans were preparing to attack and relocate enough troops to defeat the attack. The ADFGX/ADFGVX cipher applies two different types of cipher techniques. It first encrypts the message using a modified Polybius square (the numbers 1-5 are replaced with letters A,D,F,G,X or the numbers 1-6 are replaces with letters A,D,F,G,V,X). These letters were chosen because they are easy to distinguish in Morse code, see Figure 2.12. After the plaintext message is encrypted with a Polybius square, it is then encrypted with a keyword rectangular transposition cipher. Remember a Polybius square encrypts every letter in the plaintext with two numbers/letters. Applying the columnar transposition cipher after this step, separated those two letters, and is referred to as a fractionating transposition cipher. Separating the two parts of each plaintext letter makes it very hard to identify individual letters and to use statistical techniques, such as frequency analysis to identify the underlying plaintext. The cipher was designed to be easy to implement in the field, but had a fairly strong level of security for the time period.

Encrypt a portion of the message RUSH MUNITIONS STOP EVEN BY DAY IF NOT SEEN. (This is the translation of a German message sent on June 3, 1918.) Use the Polybius square below, which has a random arrangement of letters, and the keyword PARIS for the transposition cipher.

 A D F G X A c o x f m D k a z n w F g d s i h G t q e p v X r u b l y

We'll encrypt just the message: RUSH MUNITIONS.

1. Step 1: Apply the Polybius square to the message. This gives:

XA XD FF FX AX XD DG FG GA FG AD DG FF

After removing spaces we have: XAXDFFFXAXXDDGFGGAFGADDGFF

2. Step 2: Apply the columnar transpositition cipher with the keyword PARIS. Enter letters horizontally in a grid with five columns. In this case, filler letters were not used so not all of the columns will have the same length.

 P A R I S 3 1 4 2 5 $\;$ X A X D F F F X A X X D D G F G G A F G A D D G F F

Then read off vertically down the columns in the order given by the keyword.

This gives the final cipher message: AFDGDDAGFGXFXGAFXXDADFXFGF

Decrypt the message GGDDGXGFFAFAFX that was encrypted with an ADFGX cipher and keyword CODEBREAKER for the Polybius square and keyword TWO for the transposition cipher.

1. Step 1: Decrypt the transposition cipher with the keyword TWO. We need to figure out how many letters to place into each column. There are 14 letters in the ciphertext GGDDGXGFFAFAFX. In order to arrange 14 letters into three columns we need five letters in the first two columns and four letters in the third column.

 T W O 2 3 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14
We now arrange the letters of the ciphertext vertically into the columns based on the keyword. So we start with the third column but note that it only has 4 letters in that column.
 T W O 2 3 1 G G D D
Then we fill in the first column, but it will have five letters.
 T W O 2 3 1 G G X G G D F D F
Then we fill in the second column, and it will also have five letters.
 T W O 2 3 1 G A G X F G G A D F F D F X
We read off the letters horizontally, in groups of two, to get ready for the Polybius cipher.

GA GX FG GA DF FD FX

2. Step 2: Apply the Polybius cipher with keyword CODEBREAKER to decrypt GA GX FG GA DF FD FX. We must eliminate all repeated letters, this leaves us with the keyword CODEBRAK.

 A D F G X A c o d e b D r a k f g F h i l m n G p q s t u X v w x y z

Applying the square to GA GX FG GA DF FD FX gives us the message PUMPKIN.

###### Activity4.1.

Decrypt the two messages below that was encrypted with an ADFGX cipher and keyword GEORGE PAINVIN for the Polybius square and keyword LAST for the transposition cipher.

What similarities do you notice in the two cipher texts? What is the cause of that in the underlying plain text? How does this relate to the length of the keyword for the transposition cipher?

Using similar messages to uncover the transposition cipher without knowing the keyword. Suppose we intercept the following two ADFGX ciphertexts but don't know either keys. What can we do to decrypt the messages?

We notice some similarities in these ciphers and assume they have some overlap in underlying plaintext that we can use to guess the length of the keyword. Since the messages have different lengths we assume that there should not be the same number of letters in each column but that there should be the same number of columns in both cases. We also see a lot of repeated text in both ciphertexts that we can line up as below.

 A F G F A X A F G G D D A G G G A X G D F D A D A F A G A F G F A D D X D G A D G D D A G X D A F G F X G D F D A D A A A F D F

From this we guess that the keyword has three letters since there are three repeated groups of letters. We guess that the letters in the first five or six rows correspond to the same beginning plaintext. Since the largest group of repeating letters is in the third group we assume this should correspond to the first column. Then we have to decide if the first group should be in the second or third column. This takes some work, but we can calculate statistics on which two letter groups would best match the frequency distribution of the underlying language and then use frequency analysis to find the Polybius square. We won't go through all of those details but in this case the first group of letters makes the most sense in the third column and we get the following two messages after decrypting the transposition cipher.

Message 1

 3 2 1 G G A D D F F D G D A F A G A D G X A G A F A F A X G G

Message 2

 3 2 1 G G A D D F F D G D A F A G A D X D A D D A A X A F D F G G D F A F X D

The messages can now be decrypted using a Polybius cipher with keyword GEORGE PAINVIN.

ADFVX messages were first brought to French Army Lieutenant Georges Painvin, an excellent cryptanalyst in the Bureau du Chiffre soon after they sprang into use in March of 1918. The presence of only five letters immediately suggested a Polybius cipher, but all attempts to decrypt them as a simple substitution cipher failed. He then guessed that it was combined with a transposition cipher. Few messages were intercepted, however, and Painvin initially had no success in breaking the system. On March 21, 1918 the German army began a major offensive on the Allied line at the Somme. The British and French troops were taken by surprise and the German army gained significant ground. The only advantage of the German attack was that it greatly increased the amount of messages sent using this system. On April 4, 2018 Painvin discovered two messages which had a lot of overlap in the messages as in Table 2.39.

CHI 104: ADXDD XGFFD DAXAGD GDGXD GXDFG ...

This allowed him to guess a keyword of length 20 and then he had to examine multiple options for how the keyword transposed the columns. But he was able to combine the information from these two messages with a total of 18 intercepts for the day (all using the same key) to test which arrangements would produce statistics that were compatible with a substitution cipher. Once he had figured out the order of the letters in the keyword, he could use frequency analysis applied to all 18 messages from the day to produce the Polybius square. Actually, it was much more complicated than this. (Considerable statistical analysis was required after that step had been reached, all done by hand.) It took many weeks of work to finally decrypt the messages. For a while, Painvin, was able to break messages with identical beginnings or endings. It was only effective during times of very high traffic, but that was also when the most important messages were sent. A general solution was not discovered for the cipher until after the end of the war. However, at the beginning of June the cipher messages suddenly included a sixth letter, V. It was easy to guess that the Germans had switched to a larger Polybius square, but unknown if that larger square included digits, or other ways of writing commonly occurring letters. However, he was able to apply similar techniques (and a lot of hard work!) to find the arrangement of columns

6 16 7 5 17 2 14 10 15 9 13 1 21 12 4 8 19 3 11 20 18

and a Polybius square of

 A D F G V X A c o 8 x f 4 D m k 3 a z 9 F n w l 0 j d G 5 s i y h u V p 1 v b 6 r X e q 7 t 2 g

The plaintext message read: 14 ID XX Gen Kdo ersucht vordere Linie sofort drahten XX Gen Kdo 7. This translates to 14th Infantry Division: HW requests front line [situation] by telegraph. HQ 7th. This helped the French army to verify that the German were preparing for another major advance, but they didn't know where. A later ADFGVX cipher on June 3 was decrypted (and translated) to read RUSH MUNITIONS STOP EVEN BY DAY IF NOT SEEN. Direction finding techniques identified this as a message from the German High Command and that the addressee was the 18th Army's general staff in Remaugies. This gave the French army insight into where the German General, Erich Ludendorff, intended to attack. The French concentrated their forces at that point, which has been claimed to have stopped the Spring Offensive.

###### Activity4.2.
1. Decrypt the message ADAFAXGXDDGGFGGGFG that was encrypted with an ADFGX cipher and keyword BULLDOGS for the Polybius square and keyword UOR for the transposition cipher.

2. Decrypt the message FXGDGDFDDAFDDGDXDAFD that was encrypted with an ADFGX cipher and keyword BULLDOGS for the Polybius square and keyword LUNCH for the transposition cipher.

3. Both of the messages below start with the words “WEATHER IS” and use the same Polybius keyword “October Twenty Seven” but use the same, but unknown transposition key. Decrypt the messages.