Code ADFGVX, example

The replacement matrix replaces each plaintext character with a pair of ADFGVX characters. The matrix must contain each AZ character and each character from 0 to 9 only once. The FGX is built on a combination of the basic replacement, crushing, and permutation operations. This code was introduced in 1918 by Fritz Nebel, a liaison officer who served in the headquarters of the German army. This system got its name due to the fact that its encryption contained only the letters A, D, F, G and X. Later the letter V was added, and the cipher became known as the ADFGVX cipher.

The ADFGVX cipher is one of the most famous ciphers of the First World War, which was used by the German army on the western front. The special feature of the cipher is that it is built on the combination of the basic operations of replacement and rearrangement. The part of the cipher that corresponds to the replacement is based on Polybius square.

Story

Towards the end of World War I, while most of the countries in the world used either a replacement cipher or a permutation cipher, Germany began to use the new encryption system ADFGX, which combined the features of both. This system received its name due to the fact that its cipher data contained only the letters “A”, “D”, “F”, “G” and “X”. These letters were not chosen randomly. If they are represented as dots and dashes of Morse code, then they will differ significantly from each other. Thus, the choice of these letters minimizes the risk of errors during telegraph transmission. In fact, it was the square of Polybius, which fit the Latin alphabet in a certain order. This cipher was developed by the liaison officer Colonel Fritz Nebel, who served in the headquarters of the German army, and was commissioned in March 1918. ^[one]

The messages encrypted with this cipher were first intercepted by the French. The work on the "disclosure" of this cipher was entrusted to the cryptanalyst Lieutenant Georges Paynevin.

In June 1918, in order to complicate the cipher, the Germans added the letter “V”, thereby increasing the encryption grid to 36 characters. This allowed the inclusion of numbers from 0 to 9 in the plaintext and the letters I and J were encrypted differently. The cipher extension significantly reduced the size of messages containing a large number of digits. The cipher became known as ADFGVX. ^[one]

The success of the German fighting, as in any other, was based on the element of surprise. Therefore, to ensure the secrecy of the message was needed cipher with the highest resistance. The Germans believed that the ADFGX and ADFGVX ciphers were unbreakable. However, on June 2, 1918, as a result of the painstaking work, French officer Georges Paynvin deciphered the cipher, where the goals of the future German offensive were defined. The success of Paynvina allowed the French to thwart the attack and stop the advance of the Germans. ^[2]

Description of ADFGX cipher

The encryption process begins with drawing a 5 × 5 grid, each cell of which is filled with 25 letters of the Latin alphabet (I and J are encrypted in the same way). Each row and grid column is specified in one of 5 letters: “A”, “D”, “F”, “G”, and “X”. The grid is filled in a random order, so the recipient must know the location of each element in order to decrypt it.

Step One - Replace

Consider the encryption process on the example of a small message: “attack at dawn”. In the first step, each character of the message is replaced with a couple of letters denoting the line and column of the corresponding character in the grid. For example, A will be replaced by FF, and B - by GA.

So far, we have used only a simple substitution, and frequency analysis would be enough to unravel the message.

Step Two - Permutation

In the second step, a permutation is applied, which significantly complicates the cryptanalysis. Rearrangement is carried out depending on the keyword, which should be known to the recipient. Let, in our example, such a word be “BATTLE”. The permutation process is as follows. First, a new grid is created, in the top line of which letters of the keyword are written. Then, under this word, the encrypted text received in the first step is written line by line.

Further, the letters of the keyword are rearranged in alphabetical order along with their corresponding grid columns.

After which the letters of each column are written alternately from top to bottom. The resulting sequence of letters forms the final form of the ciphertext. ^{[1] [3]}

The final form of the ciphertext: FFFFFFFFGFDDXGDAXDXGG XGX

In this form, the ciphertext will then be transmitted using Morse code.

Description of ADFGVX cipher

The cipher is based on 6 letters: "A", "D", "F", "G", "V" and "X". Similar to the ADFGX cipher, a 6x6 size table is drawn and is randomly filled with 26 letters and 10 digits. The arrangement of the elements in the table is part of the key.

Step One - Replace

Replacement is carried out similarly to ADFGX cipher. Let the message be transmitted: “attack will begin in 11 am”.

Step Two - Permutation

A new table is created with the keyword in the top row. As a key, take the word "SECRET". Longer keywords or phrases are commonly used.

By analogy with the ADFGX cipher, the columns of the table are sorted alphabetically. ^[one]

After which the columns are written in turn in one line, forming the cipher text.

The final form of the ciphertext: GXFGFFDFFADDFAGFXDFAD XVFAFGFDDXXVFAXVDAGAX

To restore the original text, you must perform the actions opposite to encryption. With a keyword, the sequence of columns can be brought to the original order. Knowing the location of the characters in the source table, you can decipher the text. ^[four]

Cryptanalysis

Cryptanalysis of the ADFGX cipher was conducted by the lieutenant of the French army Georges Penven, who broke it in early June 1918. His solution method was based on finding messages with a standard beginning, which were encrypted in a similar way, forming similar patterns in the ciphertext, which corresponded to the name of the columns in the permutation table. To achieve this step, a significant statistical analysis was required, which was a very difficult task, because everything was done manually. This approach was effective only when a large number of messages were intercepted.

However, this was not the only method Penven used to break the ADFGX cipher. He also used duplicate fragments of ciphertext to obtain information about the probable length of the key used. ^[five]

Since only 5 letters were used in the encrypted text, it became clear that the encryption was carried out according to a chess pattern. The first step was to eliminate the obvious assumption. He made a frequency analysis of pairs of letters to make sure that this is not an easy replacement using Polybius square. The result gave a random distribution of pairs, from which Penwen concluded that the letters were replaced and mixed.

Now he assumed that the cipher is the result of a permutation of the columns in which the replaced chess letters were written. Paynvin was able to come up with a subtle move to narrow down the possibilities for rearranging the order of the columns. The replacement in the cipher, as described above, was carried out on the basis of a grid with the letters "A", "D", "F", "G" and "X" along the columns and the same letters along the lines. He knew that each letter was matched with 2, giving the position in the grid. This meant that after the replacement, but before the permutation, the letters denoting a column would stand in even positions, and the line in odd ones. Now, remember that the replacement result is written line by line to each other, forming columns. If the number of such columns was even, then they will consist either of letters specifying the columns or specifying the rows. This method allowed Penwen to preliminarily determine which columns were even and which ones were odd. He could then combine even and odd columns into pairs and perform frequency analysis for pairs of letters to see if they were the result of replacing the plaintext symbol. After finding the correct pairs, Penwen performed frequency analysis to identify replaced letters. It remained only to recognize the principle of transposition. After he defined the permutation scheme for one message, he could crack any other message with the same transposition key. ^[6]

Finally, in April 1918, Penven managed to decipher some messages. These days, the Germans sent a large number of encryption. By the end of May, given the rather large flow of messages, he could crack the cipher programs every day.

On June 1, 1918, the letter "V" suddenly began to appear in the encrypted messages. The Germans changed the cipher. Penven did not know whether a new letter was simply added to extend the existing system or whether they completely changed the encryption scheme, destroying all the hard work of a French officer. Penven continued to work, relying on the simplest assumption that the new cipher is an extension of the old one. And as he studied the encrypted texts, Paynwin became increasingly convinced of the correctness of his hypothesis. Having adapted his work on ADFGX to the ADFGVX cipher, in the evening of June 2, he guessed the code refined by the Germans.