Enigma: a complexity titan – The Network Pages

In times of war, secure communication can be the difference between life and death, or even winning or losing a war. To be able to secretly communicate, a message containing sensitive information can first be altered in a way only the sender and receiver of the message know. This way, only those who know how the message has been altered can know the information inside the message.

More than 2000 years ago, Julius Caesar used cryptography to communicate in secret with his generals. For example, if he wanted to send the secret message

$\texttt{the network pages}$

he would substitute each letter in the message with the letter three places down in the alphabet. This way, $\texttt{a}$ becomes $\texttt{D}$ , $\texttt{b}$ becomes $\texttt{E}$ , etc. This is called encrypting the message.

The message now becomes

$\texttt{WKH QHWZRUN SDJHV}$ ,

which is meaningless for anyone coming across this message. The only way to decrypt this message, is to substitute each letter with the letter three places up in the alphabet. Now $\texttt{D}$ becomes $\texttt{a}$ , $\texttt{E}$ becomes $\texttt{b}$ etc., and now we get the original message back. This way of encrypting messages was named after Caesar and is now known as a Caesar cipher.

If this encrypted message somehow fell into the hands of the enemy, they wouldn’t be able to know the meaning of the message. They would know the meaning if they knew the way it was encrypted, or if a certain method of attack was devised. Almost 900 years after Caesar used the cipher to encrypt his messages, polymath Al-Kindi came up with a way to crack these messages. He noticed that in most languages, some letters occur more often than others. In English, for example, the letter $\texttt{e}$ occurs most often. About 12% of all letters used in an English text is the letter $\texttt{e}$ . That means that we can look for the letter that occurs most often in a secret message encrypted using a Caesar cipher, and hypothesize that the $\texttt{e}$ was probably encrypted as that letter. In our example where we encrypted $\texttt{the network pages}$ , we see that in the encrypted message

$\texttt{WKH QHWZRUN SDJHV}$ ,

the $\texttt{H}$ occurs most often. This means that the $\texttt{e}$ was probably encrypted as $\texttt{H}$ . We can use this method for some more common English letters, and decrypt the message this way without knowing exactly how it was encrypted.

Enigma

In 1914, during the First World War, the Netherlands had not been in a non-colonial war for over a century, and they wanted to remain neutral in the Great War that was unfolding. In the Dutch East Indies, the many islands had to be guarded by the Navy. One day, fuel stations were placed on some islands by the German Navy, without permission from the Dutch government. This resulted in British, French and Japanese war ships patrolling the area. This was all a violation of Dutch neutrality in the War, but the Dutch Navy was not allowed to attack these ships, since their navy consisted only of ten ships and it would be foolish to attack out of the blue. The Navy were only to attack with direct orders from the capital city of Batavia.

The only problem was that the communication between the Navy and Batavia was not secure, and could be easily intercepted and read by others. Two first sea lieutenants, Theo van Hengel and Rudolf Spengler, were tasked with creating a secure method of communication for the Dutch Navy. They came up with the idea of a rotor machine. The central idea in this machine, is that messages are encrypted using rotors as seen in Figure 1 below. If we type the letter $\texttt{b}$ at the keyboard on the left, the electrical signal travels through the rotor in the middle, and reaches the lamp $\texttt{A}$ , which turns on. We see that the rotor has now rotated 1/6th of a full revolution. If we press $\texttt{b}$ again, we see that the letter $\texttt{C}$ will turn on. This has the effect that two of the same letters in the original message will not be encrypted as the same letter in the secret message, unlike in the Caesar cipher. This makes the rotor machine a lot safer than the Caesar cipher.

Figure 1: A simple rotor system

If we just use this one rotor to encrypt our messages, it will still not be very safe. The cipher in Figure 1 is technically a cipher called the Vigenère cipher, which was already cracked in the 19th century by Charles Babbage. To make the rotor machine safer, van Hengel and Spengler added more rotors to their machine, a representation of which can be seen in Figure 2 below. The rotors here don’t move at the same time though. The rotor on the left only turns when the rotor on the right has completed a full rotation. This compares to the handles on a clock, where the minute handle only moves when the second handle has completed a full rotation. Every rotor has a different place where this happens, which is called the turnover. Van Hengel and Spengler’s machine used three rotors in total, and was therefore considered very safe.

Figure 2: A system with two rotors.

They weren’t the only ones with this idea, though. Four others came up with the same idea of a rotor machine, probably independent from each other. In 1917, Edward Hugh Hebern had the same idea in the United States, and patented his idea there. In Europe, Arvid Gerhard Damm and the Dutchman Hugo Alexander Koch patented their versions in 1919. However, the first to patent a rotor machine in Europe was Arthur Scherbius in 1918. Van Hengel and Spengler’s machine was never put into production, since they couldn’t agree with the Navy on the rights of the patent. Scherbius’ version of the rotor machine became a commercial success, unlike the other patented machines. Scherbius named his machine Enigma.

Figure 3: The Ciphering machine invented by Arthur Schrebius. Picture taken from Schrebius pattent application in 1923.

A slightly altered version of Enigma was sold to the German military, who bought more than 30.000 machines which were used all the way until the end of the Second World War in 1945.

Figure 4: An Enigma machine. Courtesy of Andy Hollingworth Archive and Simon Singh.

Enigma didn’t consist of just the three rotors. A very important part of Enigma was the reflector. This reflector connects the ends of the last rotor with each other, and is fixed in place. The addition of the reflector makes the Enigma a great deal more useful. We see that when we press the letter $\texttt{b}$ the lamp $\texttt{D}$ turns on. Moreover, if we had pressed the letter $\texttt{d}$ , the lamp $\texttt{B}$ would’ve turned on. This means that if we have a message which was encrypted on an Enigma machine, we can get the original message back, as long as we know what the setting of the machine was when the message was typed in originally.

Figure 5: Rotor system with reflector.

The starting position of the machine when the message is typed can be regarded as the key of the message, with which it can be decrypted. The reflector also adds another important property of the Enigma machine. Since the reflector always connects the ends of two letters, a letter typed in on the Enigma machine never encrypts to itself. This seems a minor flaw, but it will play a big role when cracking Enigma later on.

The fact that the setting of the Enigma machine is the key for a message means that we can increase the security of Enigma by adding more starting positions. This is exactly what Scherbius realized, and did. The rotors in the machine were not fixed, but could be interchanged with each other. The number of starting positions of the three rotors then increased to 3! = 6. In later versions of Enigma, there were actually more rotors developed that could be used. In total, you could choose 3 rotors out of $n$ total rotors in $\frac{n!}{(n - 3)!}$ ways. The order of the rotors was called the Walzenlage. The difference between the rotors was not only the internal setting: the turnover changes as well. Remember that each rotor had a fixed spot that would indicate the turnover, i.e. when a full rotation is achieved!

Every individual rotor also had 26 starting positions which could be used. One for every letter of the alphabet that was written on the outside of the rotors. This means that part of the key was the three letters on the top side of the three rotors which could be seen through a cut-out on the Enigma machine. This part of the key was called the Grundstellung.

Figure 6: The three numbers on the top correspond to the initial setting of the rotors, this is the Grundstellung. Courtesy of Simon Singh.

The internal wiring of the rotors could also be changed, this is called the Ringstellung. The Ringstellung is almost identical to the Grundstellung, but the main difference is that the Grundstellung doesn’t change the place of the turnover, but the Ringstellung does. In the picture below, an exploded view of a rotor can bee seen. Here, the Grundstellung is the same as rotating the entire rotor, where the Ringstellung is just rotating the blue core part in the middle.

Figure 7: An exploded view of a rotor. Created by Wapcaplet for Wikipedia.

To further increase the amount of possible starting positions, Scherbius added a feature to the military version of Enigma that wasn’t available on the commercial version. Just before the signal of a button press travels through the rotors, it goes through the plugboard. On this plugboard, the signal of two letters could be swapped via a cable on the front of the machine. The signal of a button press now goes through the plugboard first, then through the rotors, gets reflected back into the rotors and back through the plugboard which then illuminates a lamp. This is called the Steckerbrett. In early versions of Enigma, only six cables were used. Later, during the war, 10 or 11 cables were used. Using 10 cables increases the amount of starting possibilities by $1,5 \cdot 10^{14}$ , thus making Enigma much more secure.

Figure 8: On the Steckerbrett the signal of two letters could be swapped via a cable on the front of the machine. Courtesy of Simon Singh.

Click here for more details on the mathematics of the Steckerbrett

Let's see how many configurations of the plugboard with $k$ cables are possible. First we have to consider in how many ways we can choose $k$ pairs of letters. Well, this is just

$26\times25 \times24 \times ... \times (26 - 2k + 1),$

since we have $26\times25$ possibilities for the first pair, $24\times23$ for the second pair, and so on. Finally, we have $(26 - 2k +2) \times (26 - 2k +1)$ possibilities for the last pair, since a total of $26-2k$ letters are not connected on the plugboard at all. We can write this as a total of $\frac{26!}{(26 - 2k)!}$ possibilities.

There is, however, a problem with this answer. Let’s say we have a cable connecting letters $\texttt{a}$ and $\texttt{b}$ , that would be the same as connecting $\texttt{b}$ and $\texttt{a}$ . This means we’re counting the total number of possibilities double for each cable. To account for this, we divide the previous answer by $2^k$ .

We’re not finished yet, though. Let’s say we have plugged up the plugboard with two cables: the first cable connects $\texttt{a}$ and $\texttt{b}$ , and the second cable connects $\texttt{c}$ and $\texttt{d}$ . Well, that would be the same configuration as if the first cable connects $\texttt{c}$ and $\texttt{d}$ and the second connects $\texttt{a}$ and $\texttt{b}$ . In other words, the order of the cables does not matter. To account for this, we divide by the number of ways we can arrange $k$ cables, which is $k$ !. All in all the total number of possibilities to connect a plugboard with $k$ cables is equal to:

$SB_k = \frac{26!}{(26-2k)!2^kk!}.$

We can now calculate for $0 \leq k \leq 13$ in how many ways we can configure the plugboard:

We see that if we use a total of $k = 11$ cables, the total number of plugboard configurations is the highest, i.e. the safest option to use. This is interesting, since up until 1938, the Germans used six cables. Seven or eight cables were used after 1938, and it was not until 1943 that the Germans finally used the safest option of ten cables.

This top secret key changed every day, and was distributed to all operators of Enigma on sheets of paper which were to be destroyed at the end of the day. The first message of the day would be the weather forecast at 6 in the morning. This meant that if you wanted to crack the daily key, you only had 18 hours to do so.

The machine Enigma

All in all, to communicate a secret message encrypt through an Enigma machine we need a secret key consisting of:
1. The order of the rotors (Walzenlage).
2. The starting position of the rotors (Grundstellung).
3. The internal setting of the rotors (Ringstellung).
4. The setting of the plugboard (Steckerbrett).

Cracking Enigma

Almost all German communication was encrypted with Enigma, so if the Allies were to crack Enigma, it would be a huge step towards victory.

In 1933, before the Second World War even started, Polish mathematician Marian Rejewski reconstructed the internal wiring of Enigma and the rotors, using only intercepted German messages. With this knowledge he continued developing a method for reliably cracking intercepted Enigma messages, influencing the direction of the war before it even started. The Polish secret service passed this information to the French and the British. When the Germans made Enigma more secure and complex in 1940, Rejewski’s methods didn’t work anymore, so another method had to be developed.

The British then continued the effort to crack Enigma with a big team of linguists, mathematicians and engineers on Bletchley Park. A team of mathematicians led by legendary mathematician Alan Turing built a machine to cleverly check all possible message keys. This machine was called the Bombe, and can be regarded as the first ever computer (or at least the prototype for the first computer).

The way Rejewski first cracked Enigma relied on small mistakes made by the Germans. This included laziness from the operators of Enigma, who would often use predictable keys where random three-letter keys were needed. The German procedure for operating Enigma also required this key to be deciphered twice, which turned out to be a major flaw in the Enigma code. Rejewski cracked Enigma with only these bits of information, which is known as a ciphertext-only attack, since only the ciphertext was known the Rejewski.

When Rejewski’s method was not usable anymore, Turing and his team set out to create a new method. Their plan was to pursue a known-plaintext attack. For this attack to work, a part of the original message was needed. This might seem like an impossible thing to know, but in reality it’s quite easy to guess the contents of certain messages. Every morning at 6 AM, the weather forecast would be broadcasted. German procedure also required to send out a message if everything was okay. All these messages would always have the same layout, so the contents could be guessed with some confidence. This guess of a part of the message is called a crib. Some examples of often occurring cribs are:

$\texttt{KEINEXBESONDERENXVORKOMMISSE}$ (nothing to report)
$\texttt{KEINEXBESONDERENXEREIGNISSE}$ (no special events)
$\texttt{WETTERVORHERSAGEXBISKAYA}$ (weatherforecast for the Bay of Biscay)
$\texttt{ABSTIMMSPRUCHYYRESTXOHNEXSINN}$ (message to calibrate frequency, rest is meaningless)

To encrypt a message using Turing’s method, let’s assume we intercepted a message which was sent at 6 AM, close to the Bay of Biscay. We don’t yet know what part of the ciphertext corresponds to the crib, but we can guess:

$\texttt{QFZWRWIVTYRESXBFOGKUHQBAISEZ}$
$\texttt{WETTERVORHERSAGEBISKAYA.....}$

Now we use the fact that a letter cannot be encrypted to itself. In this case we see that the $\texttt{S}$ is encrypted to itself, so the crib is not in the right place:

$\texttt{QFZWRWIVTYRE}$ S $\texttt{XBFOGKUHQBAISEZ}$
$\texttt{WETTERVORHER}$ S $\texttt{AGEBISKAYA.....}$

We now move the crib one letter to the right, and check for self-encrypted letters again. In this case we see more self-encrypted letters:

$\texttt{QFZWRWI}$ V $\texttt{TYR}$ E $\texttt{SXBFOGKUHQB}$ A $\texttt{ISEZ}$
$\texttt{.WETTER}$ V $\texttt{ORH}$ E $\texttt{RSAGEBISKAY}$ A $\texttt{....}$

We keep sliding right until we cannot see any self-encrypted letters anymore.

$\texttt{QFZWRWIVTYRESXBFOGKUHQBAISEZ}$
$\texttt{....WETTERVORHERSAGEBISKAYA.}$

The next step in the cracking process is turning this crib into a graph, called a menu. We construct a graph where the vertices are the letters of the alphabet. We connect two edges if they’re above each other in our constructed crib. For example, if we are certain about the following message

$\texttt{1234567}$
$\texttt{JTGEFPG}$
$\texttt{ROMMELF}$

we can construct the following menu:

Alan Turing realised he could do some deductions about the plugboard using this menu (see drop-down menu). These deductions can get quite tedious if you have to do all of them by hand, so to not get bored, Turing wanted a machine to do the thinking for him. He and his team built the Bombe, an enormous machine which simply did all of these deductions itself. Instead of having to think about what button to press on the Enigma machine, and keeping track of all the assumptions made, the Bombe could check for a correct setting in a fraction of a second.

On the back of the Bombe, a menu could simply be plugged in, and depending on the length of the crib, multiple rotor orders could be tested at the same time. After some running time, the Bombe would stop, indicating a possible solution to that day’s code. While running, the Bombe stopped multiple times, giving multiple options for possible Enigma settings. It is nothing more than a mathematical certainty that this happens, not a fault of the Bombe. These extra settings all have to be checked by hand, with a special machine. To limit the time this takes, one of two things can be done. Either a longer crib can be used, or a crib can be used which results in more cycles in the menu. Notice that both of these increase the chance of a contradiction.

In general, the aim was to get four or less possible settings in total. Alternatively, a different message with a different crib could be tried for greater chances. In 1940, the Bombe could find the correct setting in about an hour, at which point, messages could be deciphered for the rest of the day. After the war, Turing went on to do more research in the field of computing and essentially built the first programmable computer, for which the Bombe was a prototype.

Click here for more details on how the Bombe could provide possible settings

From this menu we can deduce some properties of the plugboard, and hopefully determine all the settings. For this, we first have to introduce some notation to make our life easier. Every time a letter is pressed on an Enigma machine, the internals of the machine change. We write $\pi_1$ for the permutation that encrypts the first letter, $\pi_2$ the permutation that encrypts the second letter, etc. We also write a star after a permutation if we want to describe the setting of the machine $\pi_i$ without the plugboard. For example, the permutation $\pi_1^*$ describes the permutation that decrypts the first letter of a message, but with the plugboard removed.

To do deductions about the setting of the plugboard, we have to guess the setting of the rest of the machine. This seems like a big guess, but we will see later on that this won’t be an issue. We now hypothesize that $\texttt{G}$ and $\texttt{A}$ are connected on the plugboard.

We can see in the menu that $\texttt{G}$ is connected to $\texttt{M}$ . We now try to deduce to what letter $\texttt{M}$ is connected. All of the previous can be summarized in the following:

From this, we can see that if we set up an Enigma machine with setting $\pi_3$ (the one we just guessed earlier), but omit the plugboard, we can simply press $\texttt{A}$ to see what letter $\texttt{M}$ is connected to on the plugboard. Let’s say, for example, that we find out that $\texttt{M}$ is connected to $\texttt{P}$ on the plugboard. Since $\texttt{M}$ and $\texttt{E}$ are connected on the menu, we can repeat the same procedure, but with $\pi_4$ instead of $\pi_3$ . This way, we can deduce to what letter $\texttt{E}$ is connected on the plugboard. We can now deduce for all the letters in the cycle to what letter they’re connected on the plugboard. Now we can also deduce to what letter $\texttt{F}$ is connected on the plugboard, and in particular, we can deduce again to what letter $\texttt{G}$ is connected, as a sort of check.

It turns out that, more often than not, this gives a contradiction in the plugboard settings, like a letter that is connected to two letters at the same time, which is not possible. This means we have found a contradiction in our original hypothesis, which means $\texttt{G}$ is not connected to $\texttt{A}$ on the plugboard.

Now we can test another hypothesis, for example: $\texttt{G}$ is connected to $\texttt{B}$ on the plugboard. After that, we may test the hypothesis that $\texttt{G}$ is connected to $\texttt{C}$ and so on. Most of these hypotheses will end up in a contradiction, but some may seem valid. This does not necessarily mean we have found the right plugboard setting, since we also guessed the rest of the Enigma settings at the start of the process. This means we also have to check all possible settings, which may take quite some time by hand.

Enigma was cracked and the Allies could read all but some communication of the Germans. This was especially useful in Operation Fortitude, a plot to let the Germans think the D-Day landings would take place in Calais, when in fact the landings would take place in Normandy. This was only possible due to the intelligence gained from cracking Enigma. We will never know what course the war would have taken if Enigma was never cracked. Some say it shortened the war by two years, saving millions of lives. There is no doubt though that cracking Enigma was one of the most crucial pieces in the Allied victory, and maybe it even was the most important mathematics ever done.