Autokey cipher

An autokey cipher, or self-synchronizing stream cipher, is a cipher which incorporates the message into the key. There are two forms of autokey cipher: key autokey and text autokey ciphers. A key-autokey cipher uses previous members of the keystream to determine the next element in the key stream. A text-autokey uses the previous message text to determine the next element in the keystream.

Several cryptographers in history proposed the idea of an autokey cipher, as a way to increase the security of a short key. The first autokey system that was not trivial to break was invented by Vigenère. Vigenère started with a tabula recta, a square with 26 copies of the alphabet, the first line starting with 'A', the next line starting with 'B', etc., like this:

 |ABCDEFGHIJKLMNOPQRSTUVWXYZ
-+-------------------------- 
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ 
B|BCDEFGHIJKLMNOPQRSTUVWXYZA 
C|CDEFGHIJKLMNOPQRSTUVWXYZAB 
D|DEFGHIJKLMNOPQRSTUVWXYZABC 
E|EFGHIJKLMNOPQRSTUVWXYZABCD 
F|FGHIJKLMNOPQRSTUVWXYZABCDE 
G|GHIJKLMNOPQRSTUVWXYZABCDEF 
H|HIJKLMNOPQRSTUVWXYZABCDEFG 
I|IJKLMNOPQRSTUVWXYZABCDEFGH 
J|JKLMNOPQRSTUVWXYZABCDEFGHI 
K|KLMNOPQRSTUVWXYZABCDEFGHIJ 
L|LMNOPQRSTUVWXYZABCDEFGHIJK 
M|MNOPQRSTUVWXYZABCDEFGHIJKL 
N|NOPQRSTUVWXYZABCDEFGHIJKLM 
O|OPQRSTUVWXYZABCDEFGHIJKLMN 
P|PQRSTUVWXYZABCDEFGHIJKLMNO 
Q|QRSTUVWXYZABCDEFGHIJKLMNOP 
R|RSTUVWXYZABCDEFGHIJKLMNOPQ 
S|STUVWXYZABCDEFGHIJKLMNOPQR 
T|TUVWXYZABCDEFGHIJKLMNOPQRS 
U|UVWXYZABCDEFGHIJKLMNOPQRST 
V|VWXYZABCDEFGHIJKLMNOPQRSTU 
W|WXYZABCDEFGHIJKLMNOPQRSTUV 
X|XYZABCDEFGHIJKLMNOPQRSTUVW 
Y|YZABCDEFGHIJKLMNOPQRSTUVWX 
Z|ZABCDEFGHIJKLMNOPQRSTUVWXY 

In order to encrypt a letter, one locates the line starting with the letter to be encrypted, and the column beginning with the next letter of the key. The letter where the line and column cross is the ciphertext letter.

Vigenère's innovation was in the way the key was generated. He started with a keyword, and appended the message to it. So if the keyword were "QUEENLY", and the message were "ATTACK AT DAWN", the key would be "QUEENLYATTACKATDAWN". Encoding would proceed like this:

   Message: ATTACK AT DAWN
       Key: QUEENL YA TTAC
Ciphertext: QNXEPV YT WTWP

The ciphertext message would therefore be "QNXE PVYT WTWP", using four-letter groups.

This text-autokey cipher was hailed as "le chiffre indéchiffrable", and was indeed undecipherable for over 200 years, until Charles Babbage discovered the means of breaking the cipher.

Modern autokey ciphers use very different encryption methods, but they follow the same approach of using either key bytes or plaintext bytes to generate more key bytes. Most modern stream ciphers are based on pseudorandom number generators: the key is used to initialize the generator, and either key bytes or plaintext bytes are fed back into the generator to produce more bytes.

They are said to be "self-synchronizing", because the next key byte usually depends only on the previous N bytes of the message. If a byte in the message is lost or corrupted, therefore, the key-stream will also be corrupted--but only until N bytes have been processed. At that point the keystream goes back to normal, and the rest of the message will decrypt correctly.