Alan M. Turing: Solving the mystery inside the riddle wrapped by the Enigma

During World War II, the Germans encrypted their messages using a machine called the Enigma, which used a combination of code wheels and wiring to generate a constantly changing cypher.

The Allies obtained Enigma machines and analyzed them to determine how the cypher was generated and how to break the cypher.  The British effort was housed at Bletchley Park.

Alan M. Turing had worked on the question of whether there are mathematical functions that cannot be computed; as part of this research, he described an abstract machine that could compute any function that could be described as a sequence of simple arithmetic operations.  He also had studien cryptograpy.  This led him to join Bletchley Park and work on the project to break the Enigma cypher.

Poland had obtained an Enigma machine and used it to build a preliminary version of a codebreaking machine that was called the Bomba.  Turing improved on this machine (now called the Bombe) and designed machines to crack the encryption on more complex versions of the Enigma.  He also developed some approaches that were used to manually determine the mechanism for a more sophisticated encryption machine which transmitted messages by radio.  These methods were used by Tommy Flowers in building the Colossus, one of the first large-scale special-purpose computers.

The Enigma used three rotors out of a collection of 5 or, in some machines, 4 rotors out of a collection of 7.  Each rotor contained a different arrangement of the alphabet. the first rotor advanced after each letter was encrypted, and the other rotors advanced after the previous rotor had advanced some number of steps that was different for each position of each rotor. Each encryption was symmetric (if one letter was encrypted as another, the second letter would be encrypted as the first) and no letter was encrypted as itself.  The symmetric encryption allowed the same settings to be used in encrypting and decrypting, and reduced the size of the list of daily settings that had to be distributed to the Enigma operators.  It also made determining the setting easier for the codebreakers:  any rearrangement that was not symmetric or encrypted a letter as itself could be excluded.

The more sophicated encryption machine (called Tunny by the British -- what an American would call Tuna) encrypted Baudot coded messages (a predecessor of the ASCII representation of characters) using bit computations.  The Tunny used 12 code wheels to produce a one-time pad (a random encryption key that was the length of the message to be encrypted), but because it was generated by a mechanism, it was not truly random.  Retransmitted messages, repeated phrases, and computing the frequency of matching letters in matching positions of messages encrypted using the same machine or using the same setting entry from a codebook were used to eliminate potential settings.

Images and information about the Bletchley Park codebreaking activities can be found at the Bletchley Park Museum website http://www.bletchleypark.org.uk/.  A paper model of the Enigma code wheel mechanism is available at http://mckoss.com/Crypto/Enigma.htm.  A more complete simulation is available at http://wiki.franklinheath.co.uk/index.php/Enigma/Paper_Enigma.