Enigma

As the first rays of the morning sun gently kissed the world awake, Hanne arose, rejuvenated and ready to seize the new day. She jumped out of bed and looked out her window, observing the castle's grounds in the soft light of daybreak. Towering emerald trees stretched across the terrain, crystal-clear streams meandered through the landscape, vibrant arrays of flowers adorned the earth, and winding paths wove through it all, beckoning exploration.

The early morning had also drawn an ensemble of creatures to partake in its peaceful embrace. Birds frolicked in the glistening streams, and insects danced among the blooming flowers. Hanne even spotted playful husky puppies and wolf cubs engaged in spirited brawls. She stood at her window for a while, taking in the beauty of the world around her.

Eventually, she was greeted by Alice, whose ruffled black hair immediately caught her attention. Hanne commented on Alice's hair, and in response, Alice pointed out that Hanne's blonde hair seemed to have undergone a similar transformation. They both chuckled, realising they bore the marks of a night spent in sweet slumber—their heads becoming one with their pillows.

Alice invited Hanne to join her in the kitchen, where Bob was making pancakes.

"Pancakes!" Hanne exclaimed, realising at that moment just how hungry she was. Or perhaps it was the mention of pancakes that induced the hunger in her. Either way, Hanne was excited to eat some pancakes!

The two made their way to the kitchen, where the warm, inviting aroma of freshly cooked pancakes filled the air. Hanne eagerly took her place at the table as Bob placed a golden stack before her. She poured syrup over the layers, watching it trickle down the sides, before she took her first bite. It was pure bliss. The pancakes were thick and fluffy, with a buttery richness that melted on her tongue. Hanne closed her eyes as she savoured the perfect harmony of warmth and sweetness.

Not long after, the plates were empty, and the comforting quiet of satisfaction settled in. The trio returned to their respective quarters to freshen up and eventually regrouped in Hanne's room. They lazed there for a while before finally resuming their cryptographic journey.

Alice: Okay, Hanne, I hope your cryptographic senses are tingling because we're going to explore some more fascinating developments in cryptography.

Hanne: My cryptographic senses are indeed tingling. Let's see what else the field of cryptography has to offer!

Alice: So, at this point, we'd like to introduce you to one of the most famous uses of cryptography—the Enigma machine. The Enigma machine was an electromechanical cipher machine invented in 1918 by Arthur Scherbius, a German electrical engineer. In fact, Scherbius developed several versions of the machine and marketed them all under the same name—"Enigma". The name came from the Greek word that means "to speak in riddles", and it perfectly captured the machine's mystery and complexity.

Hanne: Neat.

Alice: Initially, the Enigma machine was intended for commercial use—especially for banking and business communications—but around 1926, the German military, recognising its potential, adopted a version to secure their communications. Over the years, they continuously refined and enhanced the machine, eventually ending up with a military version of Enigma that was far more complex—and secure—than Scherbius' original design. Arthur Scherbius, however, died in 1929 in a horse carriage accident and never witnessed the many advancements made to his machine. He also did not live to see just how widely it would be used. The German military extensively used the Enigma machine to secure their communications leading up to and during World War II—which officially began in 1939. The Germans, as well as many of their adversaries, were convinced that Enigma was unbreakable.

Hanne: The unbreakable Enigma machine… fascinating! How does it work?

Alice: Essentially, the Enigma machine has a keyboard with 26 keys and a lampboard with 26 lamps, each corresponding to a letter of the alphabet. To encrypt, you press a letter of the plaintext on the keyboard, and the letter that lights up on the lampboard gives you the ciphertext. To decrypt, you do the reverse: press a letter of the ciphertext on the keyboard, and the letter that lights up on the lampboard gives you the plaintext.

Hanne: Huh! It seems so simple. Just press a key and note which lamp lights up.

Alice: Simple to use, yes, but incredibly difficult to break. That's the hallmark of a good cryptosystem. The real complexity—the real enigma of Enigma—lies in what happens between pressing a key and a lamp lighting up.

Hanne: Ohhh.

Alice: So, any guesses, Hanne, as to what happens between pressing a key and a lamp lighting up?

(Hanne thinks.)

Hanne: Well, I have a few ideas, but nothing concrete. At first, I was thinking that there might be wires directly connecting the keys to the lamps. For example, pressing 'A' would light up lamp 'R', and so on for the other letters. But this is just a simple substitution cipher, which frequency analysis can easily break. However, you mentioned that Enigma is an electromechanical cipher machine. I take the 'mechanical' part to mean that there are mechanisms in place which move things around. In other words, while there may be wires connecting the keys to the lamps, these connections are not fixed; they change every so often. If this is the case, it would mean that Enigma is a polyalphabetic cipher.

Alice: Brilliant, Hanne! Enigma is indeed a polyalphabetic cipher machine, and the connections between the keys and the lamps change every time a key is pressed.

Hanne: Wow! Every time a key is pressed… cool!

(Hanne thinks.)

Hanne: But how exactly do these connections change? It has got to be in a secure manner. We can't rely on using a repeated keyword or appending the plaintext to a keyword, as there are attacks that can compromise such systems.

Alice: Exactly. We need to ensure that what happens between pressing a key and a lamp lighting up does not leak any information. An adversary should not gain any insights from it. It needs to be a mystery—an enigma.

Hanne: Ooooh…

Alice: So, let's see what happens between pressing a key and a lamp lighting up. Having an understanding of a simple circuit will be helpful. A simple circuit consists of three main parts:

• A battery
• A load
• Conducting wires

The battery is the source of electricity, the load is something that uses electricity—a lamp, in the case of the Enigma machine—and the conducting wires allow electricity to flow from the battery to the load and back to the battery, completing the circuit.

Hanne: Right.

Alice: When the circuit is closed, meaning all the components are connected without gaps, electricity flows, and the lamp lights up. However, if there's a gap in the circuit, electricity cannot flow completely around it. In such a case, we say that the circuit is open—the lamp will not light up.

Hanne: Okay.

Alice: However, what we can do is place a switch where the gap in the circuit is. A switch is a device that is used to control the flow of electricity in a circuit. When the switch is open, the circuit is open, and when the switch is closed, the circuit is closed.

Hanne: Oh, I get it. In the Enigma machine, pressing a key controls the switch. When a key is held down, the switch is closed, and a lamp lights. When the key is released, the switch is open, and the lamp no longer lights.

Alice: Precisely. So, with that understanding of how a simple circuit works, let's now move on to the main components of the Enigma machine. To truly understand Enigma, you need to understand these four key components:

• The rotors
• The reflector
• The rotor mechanism
• The plugboard

We'll start with the rotors and the reflector. A rotor is a mechanical part that rotates in place. The Enigma machine has three rotors, usually identified by their positions—the leftmost, middle, and rightmost. When electricity enters the machine, it flows through the rightmost rotor first, then through the middle rotor, and finally through the leftmost rotor. From there, it reaches the reflector, which simply sends the electricity back through the three rotors from left to right.

Bob: Right. But to expand on that a bit, you can think of the Enigma machine as having 26 conducting wires, one for each letter of the alphabet. When a wire enters the rightmost rotor, it is connected to another wire, which changes the flow of electricity. In other words, the letter is changed at the rightmost rotor. The same happens at the middle and leftmost rotors. Then, after the leftmost rotor, the electricity flows to the reflector, where it is also changed before being reflected through the three rotors for three more changes. Altogether, this results in a total of seven changes of the letter.

Alice: Indeed. For example, let's say that we started on wire 'A'. A possible configuration might be that 'A' is changed to 'T' at the rightmost rotor, then 'T' to 'D' at the middle rotor, and then 'D' to 'K' at the leftmost rotor. It then enters the reflector on 'K', is changed to 'G', and is sent back through the three rotors to be changed again: 'G' to 'W' by the leftmost rotor, 'W' to 'M' by the middle rotor, and finally 'M' to 'R' by the rightmost rotor. So, 'A' enters this system, and after seven swaps, 'R' comes out.

Hanne: Wow!

Alice: And while all those swaps are taking place, there's also the rotor mechanism, which causes the rotors to rotate every time a key is pressed.

Bob: Well, just to clarify, it is only the rightmost rotor that rotates every time a key is pressed. The middle rotor rotates every time the rightmost rotor completes a full cycle, and the leftmost rotor rotates every time the middle rotor completes a full cycle—similar to how seconds, minutes, and hours work.

Alice: Right. And this rotation of the rotors basically means that the swaps would be different for two consecutive letters. So, pressing 'A' twice in a row would light up two different lamps.

Hanne: Interesting.

Alice: So, that's the rotors, the rotor mechanism, and the reflector. Now for the plugboard.

Bob: The plugboard is located at the front of the Enigma machine and has 26 sockets, each corresponding to a letter of the alphabet. There are wires with prongs at each end that can be plugged into these sockets to connect pairs of letters, and these connections simply change the wire that electricity flows in. For example, if socket 'A' is connected to socket 'R', then electricity entering the plugboard on wire 'A' will exit the plugboard on wire 'R', and vice versa. For the most part, the Germans used 10 wires to connect the sockets in the plugboard, which meant that 6 sockets remained unplugged. These empty sockets simply did not change the flow of electricity. So, if socket 'B' was unplugged, electricity entering the plugboard on wire 'B' would also exit the plugboard on wire 'B'. Nice and easy.

Hanne: I see.

Bob: And the plugboard is used twice in the encryption process—once before the rotors and once after. So… the magic that happens between pressing a key and a lamp lighting up goes something like this:

• You press a key, which closes the circuit.
• Electricity flows from the battery along the wire corresponding to the key that was pressed.
• It enters the plugboard, where it may or may not get changed.
• It goes through the three rotors, then the reflector, then back through the three rotors again for a total of seven changes. The rotors also rotate during this process.
• It enters the plugboard again, where it may or may not get changed.
• It flows through the lamp corresponding to the wire that electricity is currently in and then back to the battery, closing the circuit.
• The lamp lights up, giving us our ciphertext!

Hanne: Wow—wee! I had no idea that so much happened between pressing a key and a lamp lighting up. Amazing.

Bob: It certainly is.

Alice: And while we're glad that you can appreciate the complexity of the Enigma machine from our explanation, we believe that a visual demonstration is needed to truly grasp how it works. Therefore, we encourage you to make use of the many great resources online to strengthen your understanding. In particular, we highly recommend the YouTube video on Enigma by the animator Jared Owen. Specifically, his YouTube channel is called Jared Owen, and the video is titled "How did the Enigma Machine work?". It's one of the best visual explanations of the Enigma machine out there.

Hanne: Okay. I'll check it out.

Alice: Lovely.

(Hanne thinks.)

Hanne: Alrighty. So, I understand how encryption works in the Enigma machine, but… I don't fully understand decryption. You mentioned that to decrypt, we press the letters of the ciphertext on the keyboard, and the letters that light up on the lampboard would give us the plaintext. However, if the rotors rotate every time a key is pressed, wouldn't the letter mappings change? How could it be that simply pressing the letters of the ciphertext on the keyboard gives us the plaintext?

Bob: Ah, good observation, Hanne. Simply pressing the letters of the ciphertext on the keyboard would not give us the plaintext—at least, not without first correctly configuring the Enigma machine. It turns out that to decrypt a message in the Enigma machine, we first need to set the machine to the same starting configuration that was used for encryption. Only then would inputting the ciphertext produce the plaintext. This is because, even though the letter mappings change every time a key is pressed, these changes are the same for a given starting configuration.

Hanne: Oh… okay. So, assuming the starting configuration of Enigma is the same, inputting plaintext gives ciphertext, and inputting ciphertext gives plaintext.

Bob: Exactly.

Hanne: And this means the starting configuration of the Enigma machine is essentially the key.

Bob: That's right. And as to what exactly the starting configuration of the Enigma machine entails, there are three main components:

• The plugboard connections
• The rotor settings
• The wheel order

The plugboard connections refer to how the sockets are connected in the plugboard. The rotor settings refer to the starting positions of the rotors, which is a number between 1 and 26 for each rotor. And the wheel order refers to the order of the rotors.

Alice: Right. Just a note on the wheel order: Although we said that the rotors in Enigma are usually identified by their positions—leftmost, middle, and rightmost—you should think of these more as the identification of the slots that the rotors are placed in, rather than the rotors themselves. It turns out that, in the Enigma machine, the rotors can be removed and rearranged. And the ways that these rotors can be arranged in the slots are known as the wheel order.

Hanne: I see.

Alice: And with 3 rotors and 3 slots to place them in, I'm sure that you can figure out the total number of possible wheel orders.

Hanne: Certainly.

Bob: Now, once the starting configuration of Enigma is set, the plugboard connections and wheel order remain the same as we enter our message. It is only the rotor settings which change every time a key is pressed.

Hanne: Right. So… I wonder—how many possible starting configurations are there? What is the size of the keyspace in Enigma?

Bob: Ooooh… well, that's a fun question. Let's find out! We'll start with the wheel order. With three rotors and three slots to place them in, how many possibilities are there for the wheel order?

Hanne: Three factorial! We can place any of the three rotors in the first slot, any of the remaining two rotors in the second slot, and then the final rotor in the last slot. This gives:

\[3 \times 2 \times 1 = 6\]

possible wheel orders.

Bob: Excellent! Next, the rotor settings. Each rotor can be set to a number between 1 and 26. So, how many possible rotor settings are there?

Hanne: Well, there will be 26 possibilities for the leftmost rotor, 26 possibilities for the middle rotor, and 26 possibilities for the rightmost rotor. This gives:

\[26 \times 26 \times 26 = 17{,}576\]

possible rotor settings.

Bob: Lovely. And observe that these are the possible rotor settings for a given wheel order.

Hanne: Right. And since we found that there are 6 possible wheel orders, we calculate:

\[17{,}576 \times 6 = 105{,}456\]

to get the total number of possible configurations for the rotors.

Bob: Precisely.

Alice: Now, before we move on to the plugboard, recall that we said that the German military began using the Enigma machine around 1926 and extensively used it leading up to and during World War II, which started in 1939. We also mentioned that they made improvements to the Enigma machine over the years.

Hanne: Yep.

Alice: Well, one of these improvements was the addition of two more rotors to choose from. That is, for the wheel order, instead of having three rotors and three slots to place them in, there were five rotors and three slots to place them in.

Hanne: Okay. So, this would give:

\[5 \times 4 \times 3 = 60\]

possible wheel orders.

Alice: Exactly. And multiplying this by the number of rotor settings gives:

\[17{,}576 \times 60 = 1{,}054{,}560\]

total rotor configurations. This is just to highlight how simple changes, like adding two more rotors to choose from, can drastically increase the number of possible starting configurations of the Enigma machine. In this case, we went from 105,456 to 1,054,560 total rotor configurations.

Hanne: Impressive.

Alice: For most of World War II, the Germans used five rotors in Enigma, so we'll use the result for the five-rotor case—the 1,054,560 possible rotor configurations—in our calculations. And when we find the number of possible configurations for the plugboard, we will multiply it by 1,054,560 to get the total number of possible starting configurations for the Enigma machine.

Hanne: Got it.

Alice: Splendid.

Bob: So, let's talk about the plugboard. The plugboard has 26 letters and 10 wires—each with two ends. We want to figure out the number of ways to connect the letters using these wires, assuming that all 10 wires are used every time. How many possible configurations are there for the plugboard?

(Hanne thinks… for a while.)

Hanne: Hmm. I can't find an efficient way to count the total possible configurations of the plugboard.

Bob: Fair enough. It is a challenging task. Let's simplify it. Imagine that there were only 4 letters and 2 wires. In this case, how many possible configurations would there be?

(Hanne thinks.)

Hanne: In this case, there would be 3 possible configurations:

Bob: Perfect. To keep things concise, we can list the four letters such that the first two represent those connected by wire 1, and the last two, those connected by wire 2. Using this notation, the three possible configurations are ABCD, ACBD, and ADBC.

Hanne: I'll allow it.

Alice: Now, two important points worth noting. Firstly, we are only interested in the different connections between letters, not which wire provides the connection. In other words, the order of the wires does not matter. So, we consider ABCD and CDAB to be the same configuration.

Hanne: Okay. In ABCD, wire 1 connects A and B, while wire 2 connects C and D. In CDAB, wire 1 connects C and D, while wire 2 connects A and B. However, in both cases, there is a connection between A and B as well as between C and D. And since we are only interested in different connections, we consider ABCD and CDAB to be the same configuration.

Alice: Spot on. The second point worth noting is that we are not interested in which end of a wire is connected to a letter, only that there is a connection between two letters. So, for example, we consider ABCD and BACD to be the same configuration. That is, supposing that each wire has two ends labelled 'end 1' and 'end 2', connecting end 1 to A and end 2 to B is equivalent to connecting end 1 to B and end 2 to A.

Hanne: Understood.

Alice: Wonderful.

Bob: So, Hanne, here is an emerging expression that I am noticing. You will be able to spot expressions like these with some more experience in counting problems. For now, though, you might be a little puzzled as to how I got it.

Hanne: Okay. I'm ready for it. Bring it on, Bob.

Bob: We found that in the case with 4 letters and 2 wires, there were 3 possible configurations: ABCD, ACBD, and ADBC.

Hanne: Right.

Bob: Well, observe that:

\[\frac{4!}{2! \times 2^{2}} = \frac{24}{2 \times 4} = \frac{24}{8} = 3\]

Hanne: Ummm…

Bob: Let's break it down. We have 4 letters and \(4!\) ways to arrange them. We also have 2 wires to connect the letters. However, we are only interested in the different connections between letters, not which wire provides the connection—that is, the order of the wires does not matter. How many ways are there to arrange 2 wires?

Hanne: That would be \(2!\).

Bob: Exactly. So, we divide \(4!\) by \(2!\) in order not to count the different orderings of the wires. Additionally, we are not interested in which end of a wire is connected to a letter. In other words, for each pair of letters connected by a wire, say "AB", there is another pair that we are not interested in—"BA". Since we only want to consider one of these options, we divide the two options by two to get one of them. We do this for each wire. There are 2 in this case, so we divide by 2, twice, or by two to the power of two—\(2^{2}\). That is how we get the expression:

\[\frac{4!}{2! \times 2^{2}} = 3\]

Hanne: Ah, that makes a bit more sense now.

Bob: Great. So, give this problem a go: How many ways are there to arrange 13 wires to connect 26 letters in a plugboard?

(Hanne thinks.)

Hanne: With 13 wires and 26 letters, there will be:

\[\frac{26!}{13! \times 2^{13}}\]

total configurations. There are \(26!\) ways to arrange 26 letters. However, we are not interested in the order of the wires. There are 13 wires, so we divide by the number of ways to arrange 13 wires—\(13!\). We are also not interested in which end of a wire is connected to a letter, so we divide by 2 for each wire. And since there are 13 wires, we divide by \(2^{13}\).

Bob: Excellent. Now, recall that for the Enigma machine, we have 10 wires to connect 26 letters in the plugboard. For this case, there will be one additional term in the denominator. Can you guess why this might be?

Hanne: Well, in the first two examples, with 2 wires to connect 4 letters and 13 wires to connect 26 letters, all the letters will be connected by an end of a wire. However, with 10 wires to connect 26 letters, there will always be 6 letters that will not be connected. Maybe the additional term in the denominator is related to these 6 letters.

Bob: Outstanding! There will be 6 letters remaining and \(6!\) ways to arrange these 6 letters. But we are not interested in how these 6 letters are arranged since they are not connected to anything. So, we divide by \(6!\).

Hanne: Makes sense.

Bob: So, one last example: How many ways are there to arrange 5 wires to connect 12 letters in a plugboard?

(Hanne thinks.)

Hanne: With 5 wires and 12 letters, there will be

\[\frac{12!}{5! \times 2^{5} \times 2!}\]

possible configurations.

Bob: Brilliant. And finally, in the Enigma machine, how many ways are there to arrange 10 wires to connect 26 letters in the plugboard?

Hanne: In the Enigma machine, there are

\[\frac{26!}{10! \times 2^{10} \times 6!} = 150{,}738{,}274{,}937{,}250\]

total possible configurations for the plugboard.

Bob: Sensational.

Alice: And recall that to find the total possible starting configurations for the Enigma machine, we multiply the plugboard configurations by the rotor configurations. This gives:

\[\begin{aligned} 150{,}738{,}274{,}937{,}250 \times 1{,}054{,}560 &= 158{,}962{,}555{,}217{,}826{,}360{,}000 \\ &\approx 1.59 \times 10^{20} \end{aligned}\]

total possible starting configurations for the Enigma machine!

Bob: And to spell it out, that is 158 quintillion, 962 quadrillion, 555 trillion, 217 billion, 826 million, and 360 thousand possibilities.

Hanne: Wow! I could have taken a nap in the time it took you to say that.

Bob: That's right, Hanne—naps are important. They increase the span of your life. Spell it backwards, and you'll see.

Hanne: Incredible!

Alice: So, this is the Enigma machine. It has a large keyspace. It is not vulnerable to frequency analysis. There is no repeated keyword or plaintext appended to a keyword. Can you spot any weaknesses in it?

(Hanne thinks.)

Hanne: Nope.

Alice: Indeed. It is a secure cipher machine. It is an unbreakable cipher machine. But then again, everything is unbreakable… until someone breaks it.