In 1926, codebreakers in Room 40 of the Admiralty Old Building, Whitehall—the codebreaking centre of Britain at that time—were monitoring German communications after the first world war, when they started receiving baffling encrypted messages. This was the first time the British encountered messages enciphered by an electromechanical encryption machine first invented in 1918 by the German electrical engineer Arthur Scherbius. He originally marketed them for commercial purposes, such as encrypting communications between banks, but without much success. After some modifications and rebranding, in 1926 (shortly before his death in 1929) he finally found an interested client—the German navy. He called his machine Enigma.
The Enigma cipher would of course become one of the most infamous ciphers in the history of cryptography. We all know stories about Enigma and the people who made a great combined effort to break it during the second world war. But this is an Enigma story you might not have heard. This is the story of how the original Enigma was actually deciphered in Poland in 1932—before the outbreak of the second world war, and long before the celebrated work of Alan Turing, his Bombe, and Bletchley Park.
The Enigma machine
An early Enigma machine: three rotors beneath a cover at the top, each with a window to see their position. Below is the lightboard then keyboard, and finally a top-down view of the plugboard. Below the main image is a face-on view of the plugboard. The reflector is internal, and a detailed view of a rotor can be seen later in the article.
An Enigma machine in the late 1920s consisted of a keyboard, a lightboard, and several scrambling elements: three rotors, a reflector, and a plugboard. A rotor looks like a cog with 26 electrical contacts on each side, so that each contact is labelled by a letter of the alphabet (or on some models a number 01–26). Each rotor contains 26 internal wires connecting electrical contacts on one side to those on the other side—connecting each letter to a different letter, essentially performing a permutation of the alphabet. On the plugboard, Enigma operators choose six pairs of letters to be connected by cables to switch around electric current, while the reflector can be thought of as a second plugboard with a fixed pairing-up of all 26 letters.
Before an Enigma operator starts encrypting a message, they need to configure the machine by choosing some initial settings. First they choose the six pairs connected on the plugboard. Then they decide in which of the six possible orders they put the three rotors. And finally they rotate the rotors manually to some specific positions—there is a small window above the rotors so that exactly one letter label can be seen on each rotor. For example, the rotor position may be ABC, meaning the left rotor has A showing through its window, the middle rotor has B, and the right rotor has C (or equivalently on some models: 01–02–03).
A schematic of how an Enigma machine works is shown below. Once it is set up, every time the Enigma operator presses a key on the keyboard, an electric current is sent from that key to the corresponding socket on the plugboard. It may be switched to a different socket, or may be left unchanged, depending on the plugboard settings. Next, the current flows through each of the rotors from right to left, each one changing the letter as it goes. The current then enters the reflector and one more switch is made before being bounced back. It then travels again through the wirings of rotors and plugboard in reverse order by a different route, finally reaching the lightboard where it lights up a letter, indicating the letter which enciphers the original input.
A simplified diagram of the wiring of an Enigma machine for an alphabet with just six letters, and two plugboard cables: A–E and B–C. In this configuration a B is enciphered via B$\mapsto$C$\mapsto$A$\mapsto$B$\mapsto$A$\mapsto$D$\mapsto$C$\mapsto$D$\mapsto$F$\mapsto$F to F. Symmetrically, an F is enciphered as a B.
What about decrypting a received message? Decryption can be done easily since the Enigma cipher is symmetric, meaning that under the same machine settings, when you type in the ciphertext, the machine outputs the plaintext.
Quintillions of combinations
Arthur Scherbius (1878-1929)
Scherbius’ design offered great security for two reasons. The three rotors, as you may suspect, are able to rotate. The right rotor rotates by one letter each time the machine performs an encryption. The middle rotor rotates by one letter each time the right rotor finishes a whole rotation (ie every 26 letters), and similarly the left rotor rotates by one letter each time the middle rotor finishes a whole rotation (every $26^2 = 676$ letters). When the rotors rotate, so do their internal wirings, so the same letter will be encrypted to a different letter each time its key is pressed. This protects the encryption from methods like frequency analysis, which defeat substitution ciphers.
Secondly, the number of possible initial settings was far too high for brute force attack. There were $3! = 6$ different rotor orders, and $26^3 = \text{17,576}$ different initial rotor positions. Also, the number of plugboard connections was $\begin{pmatrix}{26}\\{12}\end{pmatrix} \times 11!! = \text{100,391,791,500}$ (since first you must choose 12 of the 26 letters to be paired up; then the first letter has 11 choices for its pair, the next letter has 9 remaining choices for its pair, and so on, giving $11!! = 11\times 9\times\cdots\times3\times1$ ways to pair up the 12 letters). This gives a total of 10,586,916,760,000,000 different initial settings—a 17-digit number!
Scherbius had hoped that his cipher machines would be lapped up by banks and other civilian organisations, but they did not appreciate the machines’ cryptographic strength and could not see the need for them. Finally, in 1925, the German navy saw Enigma’s value, and Scherbius’ company started mass-producing them. They were then used in military and government organisations from 1926 onwards.
An encounter with Enigma
Despite hearing about this mysterious new cipher, French and British leaders were unconcerned and did not attempt to break it, having just won the first world war. Through espionage, the French obtained two important documents about the Enigma: the German procedures for using the machines and the basic structure of the machines (ie the scrambling elements and how they worked together), but crucially the documents did not include the internal wirings. The French codebreakers found it difficult to deduce the internal wirings inside the three rotors, and did not attempt to build a replica Enigma machine. Instead, they handed the documents to the Polish government.
Poland, however, feared German invasion at any time, which provided a powerful motivation to break the cipher. If they could read the German military’s communications, they would be in a much better position. The Polish cipher office invited twenty mathematicians from the University of Poznań in western Poland to a cryptography course. They selected the three most gifted—Marian Rejewski, Henryk Zygalski and Jerzy Różycki—and recruited them into the cipher office. Because the university was located in territory which had been ruled by Germany until 1918, all three codebreakers were fluent in German.
From left to right: Henryk Zygalski, Jerzy Różycki, and Marian Rejewski (1932).
To help break the cipher, they first built replicas of the Enigma machines. Using information from the documents recovered by French spies, along with many intercepted German messages, Rejewski was able to do what the French could not—calculate the internal wirings of the three rotors.
The Polish breakthrough
The documents obtained by French spies detailed the procedure used by the German military for sending messages. The Enigma operators had a booklet that dictated the plugboard connections, rotor orders as well as the day rotor setting, each of which were different every day. They set their machines up according to the booklet, chose a message rotor setting of their own (say CHA) and typed in the message rotor setting of their choice twice, CHACHA. This is called an indicator. They then rotate the rotors to their chosen message setting, typed in the actual message, and sent it—in particular the day rotor setting specified by the booklet was only used for the first six letters of each message. Messages were then received and read in a similar way.
Knowing that repetition always leads to patterns, Rejewski exploited the fact that the first six letters of each message were two versions of the same triplet of letters. For example, if a message was intercepted beginning with the six letters AWESLD, then A and S were related because they were the encryptions of the same letter. Thousands of messages were intercepted every day which allowed Rejewski to construct a table like this to show how the letters were related:
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 —1st letters
S A B Q W E T Y U I O J P D F G R H K L Z X C V M N —4th letters
Understanding Enigma with permutation groups
For expert readers who know a little of the theory of permutation groups, this viewpoint goes a long way to help understanding how Enigma machines work. Each scrambling element gives a permutation of the alphabet, so, writing $\mu$ for the permutation corresponding to the wiring in the reflector, $\rho_1$ for the combined effect of the rotors in their initial settings, and $\pi$ for the the plugboard, an Enigma machine applies the permutation \[\pi^{-1}\rho_1^{-1}\mu\rho_1\pi=(\rho_1\pi)^{-1}\mu(\rho_1\pi).\] Notice this is a conjugate of $\mu$. Since $\mu$ is a product of 13 disjoint transpositions (see the wiring diagram above) it is (a) a derangement—no letter is unpermuted, and (b) of order 2. Any conjugate of $\mu$ also has these properties which is why an Enigma machine (a) never enciphers a letter to itself, and (b) is a symmetric cipher. If $\rho_4$ is the permutation for the rotors after they have clicked forward three positions, the permutation computed from the 1st and 4th letters of the the indicators is \[ (\pi^{-1}\rho_4^{-1}\mu\rho_4\pi)(\pi^{-1}\rho_1^{-1}\mu\rho_1\pi)^{-1}=\pi^{-1}(\rho_4^{-1}\mu\rho_4\rho_1^{-1}\mu^{-1}\rho_1)\pi. \] This is conjugate to a permutation which does not contain the plugboard permutation $\pi$, and so its cycle decomposition does not depend on the plugboard settings.
This can be thought of as a permutation of the 26 letters, and can be written using cycle notation: (A S K O F E W C B)(D Q R H Y M P G T L J I U Z N)(V X), where the first cycle (for example) means that A is sent to S which is sent to K and so on until B is sent back to A. The three Polish codebreakers would then record $(3; 2,9,15)$, meaning 3 cycles of lengths 2, 9 and 15. Different day rotor settings would lead to different numbers and lengths of cycles.
One great advantage of the cycles was that if the plugboard cables were moved, but all the rotor settings left the same, the cycle decomposition data would be the same. This allowed Rejewski, Zygalski, and Różycki to consider the effects of the rotors alone, without the plugboard. We saw already that the total number of possible rotor settings, including both rotor order and rotor position, was $3! \times {26}^{3} = \text{105,456}$—much less than that scary 10,586,916,760,000,000 we had before!
Next the Polish codebreakers catalogued all 105,456 settings with the patterns they produced (the number of cycles and their lengths). It took them about a year to complete the catalogue by hand, which included the cycles formed from the first and fourth letters, as well as those formed from the second and fifth, third and sixth letters. After that, they could find out the day rotor setting by simply checking the catalogues—there were about 2,400 different cycle patterns, so on average each pattern corresponded to $44$ different settings, a manageable number. Rejewski had already used a method similar to this when he deduced the internal wirings of the rotors.
But what about the plugboard settings? This was easy to work out once they had the correct rotor settings: remove all cables from the plugboard first, then type in some intercepted messages. Something which almost makes sense would be produced, for example MUTEN GORMEN. It’s not hard to realise that if every G and M in that phrase is switched around, it would become GUTEN MORGEN, the German for ‘good morning’. So they would deduce that G and M were connected on the plugboard. In this way, the other connections could also be found. Now the Polish codebreakers could find out the rotor order, rotor positions, and plugboard connections on any given day, and so could read German messages easily.
The Bomba
Enigma rotor with an exploded view of its components, including the alphabet (or number) ring which could rotate relative to the wiring and then be locked in place.
In 1938, the Enigma’s operating procedures were changed: all operators still used the same rotor order, and plugboard settings on a given day. However, instead of setting the machines to a day rotor setting specified in a cipher book, the Enigma operators choose their own day rotor setting first and sent it unencrypted at the beginning of a message. They then rotated the rotors to their chosen day setting, typed in their chosen message rotor setting twice, and then rotated the rotors to the message setting, and typed in the message and sent it. The catalogues of cycle lengths relied on all operators using the same day rotor settings to encrypt the message rotor settings, so this change made all the cryptographer’s hard work redundant.
You may wonder what the big problem was—if the day rotor settings were sent unencrypted and the plugboard settings were easy to deduce once the rotor settings were known, hadn’t the German military shot themselves in the foot? Sadly not, because each rotor was actually made of two components. A core which contained the internal wirings; and an alphabet (or number) ring containing all the letters of the alphabet which labelled the electrical connections. This ring could rotate around the core essentially allowing each rotor to have 26 different wirings. All operators used the same so-called ring settings, that is the relative positions of rotor cores and alphabet rings were the same for all the Enigma machines on a given day. But this meant that knowing that the first rotor was in position F, say, didn’t tell Polish codebreakers anything about the position of the wiring in the core of that rotor.
Part of a key sheet used to configure Enigma machines each day, used later than 1938 when the German military made their procedures even more complicated. Each row from left to right gives the date, rotor order (three rotors chosen from five), ring settings, plugboard settings (ten pairs), and four day rotor settings.
Now the aim was to try to deduce the ring settings. To do this they exploited a rare phenomenon. Remember that the six-letter indicator, sent at the start of each message indicating the message rotor settings, was the same three letters encrypted twice using the chosen day rotor settings. Normally an Enigma machine will not encrypt a letter to the same letter twice in a row because the first rotor will have moved forward only a few times. This is clear from the description of how Enigma encrypts letters given above. In particular this applies to the first and fourth, second and fifth, or third and sixth letters of the indicator. But very occasionally this does happen, and an encrypted indicator like AERAPO will turn up. How is this possible? The only way is if at some point the first rotor caused the second rotor to tick over in between the first and fourth letters, and the wirings just happened to produce this pattern.
Because this is so unlikely, when it does happen, it puts a lot of restrictions on the possible ring settings for the day. To be able to deduce the ring settings the codebreakers needed three of these rare indicators, for example AERAPO, WUFTUG, LICMBC. Now they just needed to find a rotor order and ring settings capable of producing this result. This was impractical to do by hand, so Rejewski invented an electromechanical machine called the Bomba. A Bomba consisted of six replica Enigma machines without their plugboards—two for each indicator—which could quickly cycle through all possible ring settings. Each Bomba machine checks one possible rotor order, so they used six Bomba machines running simultaneously to try all combinations as efficiently as possible.
Once they had found ring settings capable of producing each of the unusual indicators for that day, the codebreakers narrowed down the list by checking which settings were capable of producing all three indicators simultaneously. Then all they needed was to plug in ciphertext and use the same technique as before to deduce the plugboard settings.
Enigma strikes back
Statue in Poznań, Poland, commemorating the work of Rejewski, Zygalski, and Różycki. Image: Pnapora, CC BY-SA 3.0.
Things changed at the beginning of 1939, however, when two more rotors were added. Instead of having three rotors, Enigma operators could choose any three out of the five rotors available, which gave them 60 possible rotor orders instead of six. In addition, ten cables were used to connect letters on the plugboard, rather than the six used previously, which made it a lot harder to use the old method to determine the connections even if the correct rotor settings were known. (Later models even featured eight choices of rotor, up to three choices of reflector wiring, middle rotors which moved forward twice during each full rotation of the right rotor, and extra scrambling elements. Moreover, each branch of the German government and other Axis powers used different models, setups, and procedures.) Clearly, more Bomba machines would be needed to test so many more rotor orders efficiently, however, the Polish did not have the resources to do this.
As Germany withdrew from its non-aggression treaty with Poland in April 1939, it seemed inevitable that Poland would soon be invaded. Instead of destroying the Bomba machines and other secrets about Enigma decryption, the Polish cipher office arranged a meeting with French and British codebreakers in July, sending Enigma replicas and Bomba blueprints over to France and Britain, in hopes that the allies could build on their work.
Famously, Alan Turing and many others at Bletchley Park would go on to use this information throughout the second world war to break each successively stronger version of Enigma employed by the German military. Turing’s design for a new electromechanical decryption machine was heavily influenced by the Polish Bomba and was called the Bombe in its honour. Although the contribution by Polish mathematicians remained unknown for decades after the war, their work was declassified towards the end of last century and people started to recognise their great achievements. In front of the Imperial Castle in Poznań, a bronze prism monument was dedicated to them, with the three faces bearing their names—Marian Rejewski, Henryk Zygalski, and Jerzy Różycki.
More from Chalkdust
That’s a Moiré
Donovan Young interferes in wave patterns
On the cover: Vhat? Vhere? Venn
Madeleine Hall takes a brief dive into the world’s favourite set-relationship-representation diagram.
Handbook of equations
Forgotten how to draw a log graph? No need to panic – here's a handy guide!
In conversation with Dominique Sleet
Ellen Jolley learns how to run a maths outreach programme
An odd card trick
Michael Wendl dissects some variants of the magic separation, a self-working card trick.
Correction: Who is the best England manager?
Paddy provides a much anticipated update to the most important use of statistical analysis in the last two years