Pages

Monday, November 25, 2013

Code 53 : ADFGVX Cipher

ADFGVX Cipher

Background

ADFGX and the successor ADFGVX were developed by the German intelligence officer Fritz Nebel (* 1891; † 1967). ADFGX was used for the first time at the 5th of March in 1918 during World War I. Only a few months later, on the 1st of June, an extended version of this cipher called ADFGVX was used. A group of German cryptologists considered this cipher to be unbreakable. Since the German troops were close to Paris, it was crucial for the allied forces to break this cipher and get intelligence about the next movements of the German troops. On the 2nd of June, the French crypt analyst Geoges Painvin managed to break the encoding for a German radio message. A little later he managed to decrypt a message which revealed the position of the German troops. This was arguably one of the most important reasons why the German attack failed.The transmitted messages of the Germans were only composed of the characters A, D, F, G, V and X. These characters have been chosen because they are easily distinguishable in the Morse alphabet.2

Principle

The encoding procedure according to ADFGVX consists of two phases. For the first phase (substitution), the Polybius cipher is used. A matrix with 6 rows and columns is formed. Each character from the alphabet A-Z has to be written down in this matrix as well as the numbers 0-9. The predecessor substitution ADFGX used a matrix with only 5 rows and columns. In addition to that, the encoding procedure according to ADFGX is analogous to ADFGVX, which will be explained below.
Such a matrix could look like this:

ADFGVX
AJE5CL1
DD347A2
FXNS0UP
GMFKZ89
VI6QVWB
XTGYORH

For the message "GEHEIMNACHRICHT" the character G will be substituted according to the matrix shown above to XD. (row X and column D). The E is replaced by AD (row A and column D) and the H by XX (row X and column X). After substituting all characters we get: "XD AD XX AD VA GA FD DV AG XX XV VA AG XX XA".
Transposition is used for the second phase of encoding. The matrix is read in row by row and read out column by column. Also, an arbitrary keyword has to be chosen. Let’s assume the key would be "MYKEY".
M    Y    K    E    Y
X    D    A    D    X
X    A    D    V    A
G    A    F    D    D
V    A    G    X    X
X    V    V    A    A
G    X    X    X    A


For the last step, the columns are swapped. This happens by sorting the keyword alphabetically.
The result would be this matrix:
E    K    M    Y    Y
D    A    X    D    X
V    D    X    A    A
D    F    G    A    D
X    G    V    A    X
A    V    X    V    A
X    X    G    X    A


The character M of the keyword has been header of the first column before swapping.
Now it has become column 3.
The character Y of the keyword has been header of the second column before swapping.
Now it has become column 4.
The character K of the keyword has been header of the third column before swapping.
Now it has become column 2.
In result the original columns have been swapped to the positions (3-4-2-1-5).
To get the ciphertext, the matrix has to be read out column by column from the top to the bottom. The final ciphertext would be: "DV DX AX AD FG VX XX GV XG DA AA VX XA DX AA".

Security

To decode an ADFGVX cipher, the structure of the substitution matrix has to be known as well as the key for the transposition. However, the result of the substitution step is only a monoalphabetic substitution of the characters, which is not very secure. The transposition procedure is mainly responsible for the security of the cipher and an attacker has to find out how this procedure works.
The first phase of encoding results in a monoalphabetic substitution. Without the second phase this cipher would not be more secure than the Caesar cipher.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.