The dictionary definition of the term enigma is as follows:

1. One that is puzzling, ambiguous, or inexplicable.
2. A perplexing speech or text; a riddle.

It is therefore unsurprising that when mechanical encryption machines (rotor machines) were invented in the wake of World War I to protect sensitive diplomatic, strategic and commercial information the encryption machines were known as Enigma machines.

The term Enigma machine most often refers to the set of machines used by the Germans throughout World War II for communication. The breaking of this cryptosystem was in many ways an inflection point for modern computing and cryptanalysis. The story of Enigma has been told in books and films (most notably The Imitation Game), many of which highlight the genius of Alan Turing and the team at Bletchley Park in England who are credited with breaking the code. However, much of the credit for breaking Enigma should go to Marian Rejewski and his team of Polish cryptanalysts. President Eisenhower stated that the breaking of the Enigma code shortened the second World War by two years and thereby saved millions of lives.

The fact that Enigma had been broken remained a secret for almost 30 years after the end of WWII, partly because the British had sold captured Enigma machines to former colonies and didn’t want them to know that the system had been broken.

The Story of Making and Breaking Enigma

Enigma machine for communication during WWII

Enigma machines were in use in Germany, Italy and Japan following their invention at the end of WWI. Their initial use in peace time was for commercial communications. The German military continued to develop their machines and had the most secure and complex encryption thanks to their plugboards.

Enigma machines consisted of a keyboard, a set of rotors, a plugboard (which acts as the internal wiring but may be changed as part of the encryption key), a reversing drum and a series of lamps corresponding to letters.

Enigma machine used during the World War in late 1930s; displayed at Museo scienza e tecnologia (national museum of science and technology), Milan, Italy

At the advent of WWII the military applications were apparent. Thanks to the encryption, messages coordinating strategy and conveying secret information could be sent in confidence. The security of the system is dependent on the secrecy of the initial set up of the rotors and plugboard. Each Enigma operator was given a codebook each month containing the daily settings to be used throughout the month. To avoid the problem that simply using the set up to then send messages would enable a character frequency analysis on the first couple of characters of each message on a given day, operators chose a message key for each message. This message key contained a sequence of three letters. The daily setting from the code book was then used to encrypt these three letters. The three letters were repeated due to the error-prone nature of radio communication. The rotors were then set to match up with the three letter message key and encryption began. This meant that the first six letters of a given message were the message key encrypted as per the code book and the rest the ciphertext. This structure of the message is what ultimately led to the ability to break Enigma.

Poland and the ‘Enigma double’

Contrary to the popularisation of the story the Enigma code in its original form was originally broken by the Polish cryptanalyst Marian Rejewski in 1932. His work was ultimately able to determine the message keys of the plugboard of the encryption machine through the use of the theory of permutations. However, he lacked vital design information necessary for full decryption. With help from materials attained by the French spy Hans-Thilo Schmidt which included a record of daily keys used for encryption, Rejewski and his team were ultimately able to build their own ‘Enigma double’. This enabled the Poles to read German messages until the Germans added complexity to their encryption in 1938 by designing two new rotors such so that three of five centrally designed rotors were chosen each day to place in the machines. This increased the number of possible encryption keys exponentially making the cryptosystem more secure and difficult to crack. The Polish could ultimately not fund the continued analysis of the system given the increased complexity.

Britain, cryptic crosswords and breaking Enigma

From this point the British and the French took up the cryptanalysis. Famously in the UK leading mathematicians were recruited for what was known as project ‘Ultra’ through the use of cryptic crossword puzzles. In 1941 the newspaper The Daily Telegraph was asked to produce a cryptic crossword specifically for recruitment to the cyptanalysis efforts at Bletchley Park.

At Bletchley Park, Alan Turing and his team designed a cryptanalytical bombe. This bombe built upon the previous work in Poland in designing mechanical cryptographic attack machines that churn through and test possible permutations of the encryption key to aid in finding a solution.

The invention and improved design of the bombe aided in cracking the Enigma code but ultimately it was the procedure that the Germans used for key exchange and encryption that lead to the code being broken. The first six letters of each message on a given day denoted the machine set up (the encryption key) and were repeated enabling analysis of the repeated characters to unveil useful information which enabled the keys to be found each day. If the Germans had used the Enigma machines properly, using a secure key exchange, the encryption would have been unbreakable. This ultimately highlights at the highest level the fact that the use of a mathematically secure cryptosystem is only as secure as its implementation.

The Cryptography

Number of possible private keys

The security of the Enigma cipher was dependent on the secrecy of the initial set up of the machine. There were 3 rotors chosen of a possible 5 and each rotor had 26 possible starting positions (one corresponding to each letter of the alphabet). The internal plugboard on the German military machine was also set up each day mapping various letters to one another internally. Decryption requires that the receiving party has their identical Enigma machine set up in the same way and this synchronization was organized through the use of a codebook issued to Enigma operators. At the start of each message was the message key which denoted how to set the rotors for decoding.

Given that there are 3 rotors chosen of 5 and their ordering matters this lead to 60 possible rotor set ups. Further, each rotor was set to a starting position out of the 26 letters giving a possible 26³ = 17,576 message keys. This ultimately led to a possible 17576 × 60 = 1,054,560 initial rotor setups.

In addition, there were 100,391,791,500 possible ways of setting up the internal plug board meaning that the total number of initial setups (i.e. private keys) is given by:

Note that 10¹⁷ is 100 quadrillion. The magnitude of this number of possible set ups is what gave the encryption its strength.

Encryption and decryption

During encryption when a key was pressed on the Enigma keyboard a lamp would light up denoting the letter of ciphertext to send. During decryption the letter of ciphertext was pressed on the keyboard and the decrypted plaintext letter would light up. The message was then sent by Morse code over radio channels.

The scrambling action of Enigma’s rotors is shown for two consecutive letters with the right-hand rotor moving one position between them.

After each key press the rotors would rotate thereby complicating the cryptosystem beyond a simple substitution cipher where each plaintext letter is always mapped to the same letter in ciphertext. Each rotor would rotate at a different rate permuting the initial setup consistently across machines throughout the day. Crucially this renders letter frequency analysis impotent against Enigma encryption.

How Enigma was broken

Engima was broken through analysis of the repeated message codes i.e. analysis of the first six letters of the messages only. Let us consider this with a simplified yet true to reality example taken from the textbook “Introduction to Cryptography with Coding Theory” by Wade Trappe and Laurence C. Washington.

Assume that three messages have been intercepted and the ciphertext of the first six letters of each message were: dmqvbn, vonpuy, and pcufmq respectively. It is known that each time this part of the ciphertext was encrypted using the daily set up alone since they then set the key for the encryption of the rest of the messages. The encryption of the first letter of each of these messages corresponds to a permutation of the letters A. After this letter the rotors rotate then changing the permutation of the letters to some other permutation B and so on and so forth to then get the set of permutations {A, B, C, D, E, F}. The strategy is now to look at the products that correspond to the encryption of the same letters of plaintext: AD, BE and CF.

When AD is written we suppose that permutation A was applied followed by the permutation D. For notation purposes we will also write the permutation that maps a to b as (ab) and the permutation that maps a to b and then to c as (abc).

Let us suppose that the first message key is xyz. Therefore xyzxyz encrypts to dmqvbn. We therefore know that permutation A maps x to d and permutation D maps x to v. We know more than this in fact due to the internal wiring of the machine this means that A interchanges x and d and D interchanges x and v. Hence the product of the permutations sends d to v (as A sends d to x and D sends x to v). This has enabled us to remove the unknown x.

The same analysis of the second intercepted text tells us that AD maps v to p and analysis of the third text tells us that AD maps p to f. This has enabled us to build the following understanding of the permutation AD.

We can continue this analysis for BE and CF.

With enough intercepted messages we can fully articulate the permutations AD, BE and CF and thereby attain the daily settings for Enigma and attain the message keys and thereby decrypt the messages. This information depends only on the plugboard and the rotor setup and not on the message key and therefore applied to all Enigma machines in use that day (since they follow the same codebook for setup). Clearly this only allows decryption after many messages have been sent but it allows decryption nonetheless.

The plugboard adds another permutation to the encryption. However this permutation does not affect the ‘shape’ of the permutations AD, BE and CF. This means that the lengths of the cycles of letters they induce (e.g. a to b to c would be a cycle of length 3) do not change under the permutations of the plugboard. This enabled Rejewski and his colleagues in Poland to note all 105,456 initial rotor settings along with the set of cycle lengths the initial rotor settings imply. This enabled the possible rotor settings for the day to be narrowed down rapidly by finding the cycle lengths of the day’s messages via an extended version of the analysis described in the previous paragraph. The remaining set of substitutions was then often small enough for an exhaustive search for the initial setting to be found quickly a process which the invention of bombes mechanized.

Conclusion

The story of the Enigma machines and the breaking of their encryption gives historical reference for the importance to cryptography. It is a clear example where lives were depending on the skill of specialized mathematicians. The ultimate lesson to be learned is that a cryptosystem is often only as secure as its implementation and that in cryptography repetition can ruin everything. The Enigma machines also manifest a practical mechanical operation of cryptography which has aided mathematicians in visualizing and thinking through the application and magnitude of their analysis of permutations and combinations.