The ADFGVX cipher is one of the most famous ciphers of World War I , which was used by the German army on the western front. The feature of the cipher is that it is built on a combination of basic replacement and permutation operations. The part of the cipher corresponding to the replacement is based on the Polybius square .
Content
- 1 History
- 2 Description of ADFGX cipher
- 2.1 Step One - Replace
- 2.2 Step Two - Reshuffle
- 3 Description of ADFGVX cipher
- 3.1 Step One - Replace
- 3.2 Step Two - Reorder
- 4 Cryptanalysis
- 5 notes
- 6 Literature
History
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 using the new ADFGX encryption system, which combined the features of both. This system got its name due to the fact that its cryptograms contained only the letters "A", "D", "F", "G" and "X". These letters were not chosen randomly. If they are represented in the form of dots and dashes by the Morse code , then they will differ significantly from each other. Thus, the selection of these letters minimizes the risk of errors during telegraphic transmission. In fact, it was Polybius square, which fit the Latin alphabet in a certain order. This code was developed by a communications officer Colonel Fritz Nebel, who served in the headquarters of the German army, and was put into effect in March 1918. [one]
Messages encrypted with this cipher were the first to be intercepted by the French. Work on the "disclosure" of this cipher was entrusted to the cryptanalyst Lt. Georges Painwin .
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 digits from 0 to 9 in plaintext and the letters I and J began to be encrypted differently. The extension of the cipher significantly reduced the size of messages containing a large number of digits. The cipher became known as ADFGVX. [one]
The key to success of the German military operations, as in other matters, as well as any others, was based on the factor of surprise . Therefore, to ensure the secrecy of the message, a cipher with the highest strength was needed. The Germans believed that the ADFGX and ADFGVX ciphers were unbreakable. However, on June 2, 1918, as a result of painstaking work, the French officer Georges Painwin deciphered the cryptogram where the goals of the future German offensive were determined. Paywin's success 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 identically). Each row and column of the grid is specified by one of 5 letters: “A”, “D”, “F”, “G” and “X”. The grid is filled in random order, so the recipient must know the location of each element in order to decrypt.
| A | D | F | G | X | |
|---|---|---|---|---|---|
| A | F | N | H | E | Q |
| D | R | D | Z | O | C |
| F | I / J | S | A | G | U |
| G | B | V | K | P | W |
| X | X | M | Y | T | L |
Step One - Replacement
Consider the encryption process using the example of a small message: “attack at dawn”. In the first step, each character of the message is replaced by a couple of letters that indicate the row and column of the corresponding character in the grid. For example, A will be replaced by FF, and B by GA.
| Message: | attack at dawn | |||||||||||
| Clear text: | a | t | t | a | c | k | a | t | d | a | w | n |
| Ciphertext in the first step: | Ff | Xg | Xg | Ff | Dx | Gf | Ff | Xg | DD | Ff | Gx | AD |
So far, we have used only a simple replacement, and a frequency analysis would be enough to unravel the message.
Step Two - Relocation
At the second step, permutation is applied, which greatly complicates 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 upper line of which the letters of the keyword are written. Then, under this word, the encrypted text obtained in the first step is recorded line by line.
| B | A | T | T | L | E |
|---|---|---|---|---|---|
| F | F | X | G | X | G |
| F | F | D | X | G | F |
| F | F | X | G | D | D |
| F | F | G | X | A | D |
Next, the letters of the keyword are rearranged in alphabetical order along with their corresponding grid columns.
| A | B | E | L | T | T |
|---|---|---|---|---|---|
| F | F | G | X | X | G |
| F | F | F | G | D | X |
| F | F | D | D | X | G |
| F | F | D | A | G | X |
Then the letters of each column are written alternately from top to bottom. The resulting sequence of letters forms the final ciphertext. [1] [3]
Final ciphertext view: FFFFFFFFGFDDXXDAXDXGG XGX
In this form, the ciphertext will then be transmitted using the Morse code.
Description of ADFGVX cipher
The code is based on 6 letters: “A”, “D”, “F”, “G”, “V” and “X”. Similarly to the ADFGX cipher, a 6x6 table is drawn and randomly filled with 26 letters and 10 digits. The arrangement of elements in the table is part of the key.
| A | D | F | G | V | X | |
|---|---|---|---|---|---|---|
| A | one | J | R | four | H | D |
| D | E | 2 | A | V | 9 | M |
| F | 8 | P | I | N | K | Z |
| G | B | Y | U | F | 6 | T |
| V | 5 | G | X | S | 3 | O |
| X | W | L | Q | 7 | C | 0 |
Step One - Replacement
Replacement is carried out similarly to the ADFGX cipher. Let the message be transmitted: “attack will begin in 11 am”.
| Message: | attack will begin in 11 am | ||||||||||||||||||||
| Clear text: | a | t | t | a | c | k | w | i | l | l | b | e | g | i | n | i | n | one | one | a | m |
| Ciphertext in the first step: | Df | Gx | Gx | Df | XV | Fv | Xa | Ff | Xd | Xd | GA | DA | Vd | Ff | Fg | Ff | Fg | AA | AA | Df | Dx |
Step Two - Relocation
A new table is created with the keyword in the top row. As the key, take the word "SECRET". Usually longer keywords or phrases are used.
| S | E | C | R | E | T |
|---|---|---|---|---|---|
| D | F | G | X | G | X |
| D | F | X | V | F | V |
| X | A | F | F | X | D |
| X | D | G | A | D | A |
| V | D | F | F | F | G |
| F | F | F | G | A | A |
| A | A | D | F | D | X |
By analogy with the ADFGX cipher, table columns are sorted alphabetically. [one]
| C | E | E | R | S | T |
|---|---|---|---|---|---|
| G | F | G | X | D | X |
| X | F | F | V | D | V |
| F | A | X | F | X | D |
| G | D | D | A | X | A |
| F | D | F | F | V | G |
| F | F | A | G | F | A |
| D | A | D | F | A | X |
Then the columns are written in turn on one line, forming encrypted text.
Final type of ciphertext: GXFGFFDFFADDFAGFXDFAD XVFAFGFDDXXVFAXVDAGAX
To restore the source text, you must perform the opposite of encryption. With a keyword, a sequence of columns can be restored to its original order. Knowing the location of the characters in the source table, you can decrypt the text. [four]
Cryptanalysis
Cryptanalysis of the ADFGX cipher was carried out by the French Army lieutenant Georges Penven , who had cracked it by early June 1918. His solution method was based on the search for messages with a standard beginning, which were encrypted in a similar way, forming similar models in encrypted text, 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 intercepting a large number of messages.
However, this was not the only technique Penven used to crack the ADFGX cipher. He also used repeating pieces of ciphertext to obtain information about the likely length of the key used. [5]
Since only 5 letters were used in the encrypted text, it became clear that the encryption was carried out according to a chess scheme. The first step was to eliminate the obvious assumption. He performed a frequency analysis of pairs of letters to make sure that this is not a simple substitution using the Polybius square. The result gave a random distribution of pairs, from which Penven concluded that the letters were replaced and mixed.
Now he suggested that the cipher is the result of a permutation of the columns in which the letters replaced by the chess scheme were written. Painwin was able to come up with a subtle move to narrow down the possibilities for rearranging the order of the columns. Replacement in the cipher, as described above, was carried out on the basis of the grid with the letters "A", "D", "F", "G" and "X" along the columns and the same letters along the rows. He knew that each letter was assigned 2 corresponding to the position in the grid. This meant that after the replacement, but before the permutation, the letters denoting the column will be in even positions, and the line in odd positions. Now remember that the result of the replacement is written line by line under each other, forming columns. If the number of such columns was even, then they will consist of either letters defining the columns, or - defining the rows. This method allowed Penven to preliminarily determine which columns were even and which columns were odd. Then he could combine the even and odd columns into pairs and perform frequency analysis for pairs of letters to see if they are the result of replacing the plaintext character. After finding the right pairs, Penven performed a frequency analysis to identify the replaced letters. It only remained to recognize the principle of transposition. After he determined the permutation scheme for one message, he could crack any other message with the same transposition key. [6]
Finally, in April 1918, Penwen managed to decrypt some messages. The Germans sent a large number of ciphers these days. By the end of May, given the rather large flow of messages, he could break into cryptograms every day.
On June 1, 1918, the letter “V” suddenly appeared in encrypted messages. The Germans changed the code. Penvin did not know if a new letter was simply added to expand the existing system or whether they completely changed the encryption scheme, destroying all the hard work of the French officer. Penven continued his work, relying on the simplest assumption that the new cipher is an extension of the old. And with the study of ciphertexts, Painwin became increasingly convinced of the correctness of his hypothesis. Adapting his work on ADFGX to the ADFGVX cipher, in the evening of June 2, he unraveled the German-improved code.
Notes
- ↑ 1 2 3 4 Richard E. Klima, Neil P. Sigmon. Cryptology: Classical and Modern with Maplets (Eng.) // CRC Press. - 2012 .-- June 1. - S. 55-57 . - ISBN 978-1-4398-7241-3 .
- ↑ John F. Dooley. A Brief History of Cryptology and Cryptographi Algorithms // Springer Science & Business Media. - 2013 .-- September 2. - S. 57 . - ISBN 978-3-319-01628-3 .
- ↑ Chris Christensen. ADFGVX Cipher - S. 4-8 .
- ↑ Simon Singh. Book of Ciphers: The Secret History of Ciphers and their Decryption // AST: Astrel. - 2009. - July 1. - S. 416-417 . - ISBN 978-5-271-14453-0 .
- ↑ Codes & Codebreakers In World War 1. [1]
- ↑ Secret History: The Story of Cryptology. (English) // CRC Press. - 2013 .-- March 2. - S. 191-207 . - ISBN 978-1-4665-6186-1 .
Literature
- General Solution of the ADFGVX Cipher System, J. Rives Childs, Aegean Park Press, ISBN 0-89412-284-3
- David Kahn. The Codebreakers: The Story of Secret Writing // New York: Macmillan. - 1967. - S. 340-347 .
- Rob Curley Cryptography: Cracking Codes (Eng.) // Britanncia Educational Publishing. - 2013 .-- June 1. - S. 28-30, 54-56 . - ISBN 978-1-62275-036-8 .
- Craig P. Bauer. Secret History: The Story of Cryptology. - CRC Press, 2013 .-- P. 188-207. - 575 p. - ISBN 978-1-4665-6187-8 .