The Enigma machine as a permutation

By thinking of the Enigma machine as a sequence of permutations, and applying the theory we have already met, we will now take the first steps to see how the Enigma machine was broken.

The Enigma machine as a series of permutations

To recap where we are: we can think of an Enigma machine as a series of permutations, one after the other. First you go through the plugboard, then through the three rotors, into the reflector, back through the three rotors, back through the plugboard again, and into the lampboard.

Let us think of the plugboard as being one permutation, and all the internal bits (the three rotors and the reflector) for the first keypress as being just one other permutation. So the first keypress of an Enigma machine can be thought of as being the plugboard’s permutation, followed by the “rotors on first keypress” permutation, followed by another plugboard permutation.

The plugboard doesn’t change on each key press, only the internal wiring, caused by the rotors rotating. So the encryption permutation for the second keypress can then be thought of as the plugboard’s permutation, followed by the internal “rotors on second keypress” permutation, followed by the plugboard permutation.

Since the message indicator was double-encrypted, we know that the first and fourth letters of the plaintext were the same letter. In our previous example, we had twice encrypted the message indicator QQQ to obtain MFK FXT.

But we also know that the machine decrypts as well as encrypts. So if Q is sent to M on the first keypress, then M would be sent to Q on the first keypress.

Putting all this together, we know that M is sent to F by the permutation that sends the first letter to the fourth letter. This can be represented as follows:

Next note that the “plugboard” permutation is its own inverse: the plugboard either switches pairs of letters, or leaves the input letter unchanged. Doing this operation twice always returns the same letter you started with (recall that this is known as the identity permutation). So we can rename the final two plugboard permutations as “inverse plugboard”:

But now we see that in the middle of the diagram we’re applying the plugboard permutation followed by its inverse, and so these cancel each other out! That is, we can simplify the diagram to the following:

Now let’s call the permutation that comes from the rotors on the first keypress, followed by the rotors on the fourth keypress, (mu); let’s also call the plugboard permutation (rho). Then the combined permutation above, that sends the letter M to the letter F, can be written as (rho^{-1}circ mu circ rho). This is just the conjugation of (mu) by (rho), as we saw earlier! In particular, it means that the cycle structure of the permutation sending M to F is the same as the cycle structure of (mu).

Finding the cycle structure of the “Double Enigma” machine

Many, many messages were sent during the same day (reports from the time suggest 250 messages per day was not unusual). In our running example, we’ve already seen one message in which the message indicator is encrypted to MFK FXT. Maybe another message sent that day has the encrypted message indicator FKS UPY. Thinking about the permutation that sends the first to the fourth letter, we see that F goes to U.

Maybe another indicator is UUT JYK. This tells us that U goes to J.

And finally, maybe another message has the indicator JYG MNQ, so J goes to M.

Note this completes our cycle. We have (Mto Fto Uto Jto M). This is a cycle of length 4.

We keep going until we have the complete cycle structure of the permutation that sends the first letter to the fourth letter. For this example, let us suppose it is two 7-cycles, two 4-cycles and four 1-cycles. That is, the cycle structure of (mu) in this example is ((7,7,4,4,1,1,1,1)).

The important thing to note is that anyone can listen in on the encrypted messages being broadcast; anyone is able to reconstruct the permutation’s cycle structure.