AutoKey or le chiffre indéchiffrable

An autokey cipher is one where the message is somehow incorporated into the key - the key changes ‘on the fly’ as the message is transmitted.

The cipher that bears the name of Vigenère is not the strongest which he developed, Vigenère also invented an autokey cipher based on the same grid.

Let’s remind ourselves of the Vigenère tableau:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P S
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

If we wish to use this with as the basis for an autokey cipher, seeded with the key ’samwise’, then we will use the first seven letters of the message to form the next seven letters of the key.

To encode the message ‘One Ring to bring them all and in the darkness bind them’ we would use the following key:

 Plaintext : ONERI NGTOB RINGT HEMAL LANDI NTHED ARKNE SSBIN DTHEM
       Key : SAMWI SEONE RINGT OBRIN GTHEM ALLAN DINTH EDARK NESSB
Ciphertext : GNQNT FKHBF IQAMM VFDIY RTUHU NESEQ DZXGL WVBZX QXZWN

Note how the patterns used to decipher the cipher called Vigènere are washed out even further.

To decode the cipher we just work at this in reverse:

       Key : SAMWISE  ,->  ONERING  '-> TOBRING ...
Ciphertext : GNQNTFK  '    HBFIQAM  '   MVFDIYR ..
 Plaintext : ONERING -'    TOBRING -'  ......

This cipher was hailed as le chiffre indéchiffrable, and was not broken for another 200 odd years. Indeed, the ‘indecipherable’ claim reportedly was made by ‘Scientific American’ as late as 1917.

The way in to the cipher lies from the fact that there is redundancy there, once part of the message is obtained, one can work to tease out the message elsewhere.

The easiest route into the cipher is that it susceptible to a known plaintext attack. For example, if standard salutations are used (e.g. Dear *****), then this may be used to obtain the first few letters of the key, and the message can be expanded from there. Similarly, if the message is likely to be about certain topics, words can be guessed this can be used to facilitate a known plaintext attack.

The trouble with this particular method of autokeying is that one can get synchronisation errors. Namely one slip, and the rest of the ciphertext becomes garbled. It is possible to work back to the source of the error and correct it, but this might be tedious - and difficult in an automatic setting. Modern equivalents only depend on the preceding X bytes of a message, and so after a certain time errors work themselves out of the stream. These are ’self synchronising’.

There are certain similarities between the above discussion and the workings of the WW2 ‘Lorenz’ machine - watch for that article in the future!