An Enigma Rotor Machine, as used by the Germans in World War Two
My MSc by research was entitled "The Application of Genetic Algorithms to Cryptanalysis" and was submitted in January 96. A postscript version of the whole thesis is available, called thesis.ps.gz (300k). My supervisors for the MSc were Professor Vic Rayward-Smith and Dr Geoff McKeown . The most interesting bit is described in a paper, icga111.ps (495 k), due to appear in ICGA 97.
The objective of this research was to examine the possible applications of genetic algorithms in cryptology, with the emphasis of the research being in the application of a genetic algorithm in the cryptanalysis of rotor machines with ciphertext only. The thesis covered three large subject matters: statistics, cryptography and genetic algorithms.
Cryptography is the science of conducting secure communication. Cryptanalysis is the study of recovering communications by those other than the intended reciever. Cryptology is the umbrella term for cryptography and cryptanalysis, although cryptography is often used to mean cryptology. Cryptography has attracted much interest in recent years. While historically, cryptography was thought of as of interest to hobbyists and spies only, the increasing need for the secure transmission of large quantities of information and the advances made in public key cryptography have made cryptography an attractive subject. Statistics forms the basis of much cryptanalysis, and is also important in testing cryptographic systems for possible weaknesses.
Rotor machines Rotor machines are cryptographic devices that became popular in the early part of this century. They formed the basis for most military and commercial cryptography until the late 1950s. The German Enigma, the Hebern machine and the Converter M-325, all described in [17], are variations on the basic machine we use.
The mechanisation of cryptography was seen as a great advance, and most at the time felt these new systems were practically unbreakable. A rotor is a small disk with electrical contacts on either side, one for every letter of the alphabet, which form a permutation on the set of all letters. A rotor machine is formed by concatinating rotors to form a new permutation. Rotors rotate after the enciperment of each letter to yield a new permutation (see picture below).
Most famous of all rotor machines was the enigma (pictured above). The enigma had three or four rotors and a reflector, whiched passed the signal back through the rotors. The enigma was famously broken by Alan Turing and the others at Bletchley Park. They had a huge advantage over our method of attack: they had a copy of the machine. We assumed no such advantage, and aimed to recover a copy of the machine and the plaintext.
A three rotor machine for an eight letter alphabet before and after the first rotor has moved once
In a nutshell, we derived a method of deciphering messages encrypted with a the rotor machine, utilising a Genetic Algorithm to search the keyspace with as little as 3800 letters of ciphertext. The GA was implemented on the X-GAmeter toolkit .
The previously best known technique of cryptanalysing rotor machines was implemented and found to be unable to cryptanalyse a three rotor machine with even very large amounts of ciphertext. So, as far as cracking unknown rotor machines without reflectors goes, we are the tops. Shame they haven't been used for 50 years. Cryptanalysis is a difficult field to advance in as the best modern systems rely on some pretty solid theory. If there is any lesson from my thesis relating to modern cryptography then its this: Look for transformations of the problem space which don't make the problem simpler in the traditional sense but may allow a heuristic a reasonable chance of success. Most modern techniques such as differential cryptanalysis look at the statistical properties of very large random samples of text, but if that sampling could be guided in some way then who knows? Note how confident I am of the success of finding these transformations by the fact that I switched subjects for my PhD .