The Theorem that Won the War: Part 2.4 – The Message Key

Because of the reflector, all Enigma encryptions are a special type of permutation known as a proper involution. An involution is a permutation that is the product of disjoint transpositions; and a proper involution has no fixed points (in other words, every letter is switched to something else). This proved to be Enigma's fatal flaw.

To understand why, we'll need to introduce one final operational detail. What's important to understand is that even if we have the actual rotors used for an encryption, we'd still need one more piece of information to decrypt a message: the initial position of the rotors. This leads to the cryptographic problem known as the key exchange problem (KEP).
Strictly speaking, we need to know the initial positions of the reflector and the keyboard rotors, though we'll focus on the keyboard rotor and assume our reflector is always set in the same position. Our keyboard rotor can be put in any one of six possibilities, three of which are

Figure 15. Three of the six possible initial positions for the keyboard rotor.

We'll describe the orientation by giving the letter of origin for the dashed connection (so the three configurations above would correspond to \(c\), \(d\), and \(e\)). Each of these initial orientations corresponds to a different \(N\), and consequently a different encryption \(E_{n}\) for the \(n\)th letter of the message.

To send a message, we'd choose a random letter, say \(a\). We'd set our keyboard rotor in the \(a\) position (so \(a\) is the origin of the dashed connection), as shown in Figure 16.

Figure 16. Initial setup with keyboard rotor set in the \(a\) position.

If the first letter of our message is \(d\), then when we pressed \(d\), the keyboard rotor would turn one place, as shown in Figure 17.

Figure 17. Position of keyboard rotor after advancing one place.

Then \(d\) would be encrypted:

• By the keyboard permutation \( d\rightarrow a\),
• By the reflector permutation \( a\rightarrow e\),
• By the keyboard permutation \( e\rightarrow b\). (Remember on the return trip we use the inverse of the keyboard permutation.)

So \( d\rightarrow b\), which is sent to the recipient.

The problem is that the recipient can't decrypt \(b\) without knowing the initial position of the rotor! This is the Enigma KEP: we must somehow convey, to the recipient, the initial setting of the keyboard rotor.

To solve this problem, the Germans proceeded as follows:

• All Enigma operators had a “daily key,” which you can imagine as being the default key and rotor setup. (There were several different rotors available, so the daily key also specified which rotors would be used).
• To send a message, the operator would choose a random “message key,” which corresponds to the initial settings of the rotors that will be used to encrypt the actual message. Since the real Enigma machine had three rotors, the message key would be a three letter sequence.
• The message key would be encrypted using the daily key and sent to the recipient.
• The recipient would decrypt them (again using the daily key), which told them how to set their machine to be able to decrypt the incoming message.

In theory, if the Allies got ahold of the book of daily keys, they could read any Enigma message. In practice, the Nazis kept the code books very secure; the different services used different code books; and they were changed monthly, so this information was not readily available.

As an example using our paper Enigma, suppose the daily key specified the rotor and reflector setup shown in Figure 18.

Figure 18. Rotor and reflector setup for an example of message key encryption.

We'd send the message key \(a\) using this initial configuration. The recipient would receive the encrypted letter (which turns out to be \(f\)); they could then decrypt it to obtain the message key \(a\). They would then set their Enigma machine to the correct configuration to decrypt the incoming message.

To explore these ideas further, continue to the Activities for Part 2.4 (The Message Key).

Return to the overview of Part 2 (The Algebra of Enigma).

Skip to the overview of Part 3 (Breaking Enigma).