The Theorem that Won the War: Part 2 – The Algebra of Enigma

Author(s): 
Jeff Suzuki (Brooklyn College)

 

In an invited address at a 1941 meeting of the American Mathematical Society, the American mathematician Abraham Adrian Albert (1905–1972) famously noted that

It would not be an exaggeration to state that abstract cryptography is identical with abstract mathematics.

In fact, around the same time that Hardy reveled in the “uselessness” of higher mathematics, Albert and Olive Clio Hazlett (1890–1974), both of whom published pioneering work in abstract algebra, began working with the U.S. Army on the problem of breaking coded military communications.

Photograph of American mathematicians Abraham Adrian Albert.   Photograph of American mathematician Olive Clio Hazlett.
Figure 13.  American mathematicians Abraham Adrian Albert and Olive Clio Hazlett.
Left: Convergence Portrait Gallery; Right: Wikimedia Commons, Creative Commons Attribution-Share Alike 4.0.

At this point, we'll thus need to introduce some abstract algebra. If you haven't taken abstract algebra yet, don't worry: we'll introduce the important ideas as we go along.

We will again do this in several parts, pausing to look at some specific activities along the way.

 

The Theorem that Won the War: Part 2.1 – Compositions

Author(s): 
Jeff Suzuki (Brooklyn College)

 

Mathematically, we can describe a cryptographic system as a function \(f\) from the set of all possible “plaintext” messages \(\mathcal{P}\) to the set of all possible “ciphertext” messages \(\mathcal{C}\).

Consider a permutation like \[
\sigma =
\begin{pmatrix}
a &b &c &d&e&f\\
f &c &b&e &a &d
\end{pmatrix} .\] One way to interpret \(\sigma\) is as a function on the letters \(a\) through \(f\). If you imagine that a function “does something” to an input to produce an output, then we might write the action of \(\sigma\) as:
\begin{align*}\sigma(a) &= f\\
\sigma(b) &= c\\
\sigma(c) &= b\\
 &\vdots
\end{align*}

Another important idea, which also has an analog in functions: given any permutation \(\sigma\), the inverse permutation, written \(\sigma^{-1}\), “undoes” the permutation and sends everything back to where it started. As is often the case in life, it's easier to know where you've come from than where you're going; finding the inverse function is a matter of determining where you started to end up at a given place. Thus if we look at our permutation, we find
\begin{align*}
\sigma^{-1}(a) &= e\\
\sigma^{-1}(b) &= c\\
\sigma^{-1}(c) &= b
\end{align*}
and so on. Converting this back to Cauchy two-line notation allows us to write
\[
\sigma^{-1} =
\begin{pmatrix}
a &b &c&d &e &f\\
e&c &b &f&d &a
\end{pmatrix}.
\]

Now consider another permutation like
\[
\tau =
\begin{pmatrix}
a &b &c&d &e &f\\
c & d&a&b &f &e\\
\end{pmatrix}.
\]
From other math courses, you know that if you have two functions \(f(x), g(x)\), then as long as the range of \(g\) is in the domain of \(f\), you can find their composition \(f[g(x)]\), where we first apply \(g\) to an input \(x\), then apply \(f\) to the output we get. Note that while we write the composition as \(f \circ g\), we apply \(g\) first, then apply \(f\): in other words, we work “backwards.”

We can do exactly the same thing with permutations, with two minor changes. First, we must indicate the composition of functions \(f, g\) as \(f\circ g\), since \(fg\) has a different meaning. But with permutations, the only possible meaning of \(\tau\sigma\) is to apply \(\sigma\) to an input, then apply \(\tau\) to the output we get after applying \(\sigma\). Second, we speak of the composition of functions, but the product of two (or more) permutations.

To write \(\tau\sigma\), we “follow the input:”

  • \(\sigma(a) = f\), and \(\tau(f) = e\), so \(\tau\sigma(a) = e\),
  • \(\sigma(b) = c\), and \(\tau(c) = a\), so \(\tau\sigma(b) = a\),
  • \(\sigma(c) = b\), and \(\tau(b) = e\), so \(\tau\sigma(c) = d\),
  • \(\sigma(d) = e\), and \(\tau(e) = f\), so \(\tau\sigma(d) = f\),
  • \(\sigma(e) = a\), and \(\tau(a) = c\), so \(\tau\sigma(e) = c\),
  • \(\sigma(f) = d\), and \(\tau(d) = b\), so \(\tau\sigma(f) = b\).

Thus we can express
\[\tau\sigma =
\begin{pmatrix}
a &b &c&d &e &f\\
e &a &d&f &c &b\\
\end{pmatrix}.
\]

This gives us another way to express an Enigma encryption:

  • Apply the permutation \(N_{k}\) associated with the \(k\)th rotor position
  • Apply the permutation \(Q\) associated with the rotor,
  • Apply the inverse permutation \(N_{k}^{-1}\) (the “backward” path through the rotor)

Thus the encryption of the \(k\)th letter of an Enigma message can be expressed as \(N_{k}^{-1}QN_{k}\).

To explore the basics of products and inverses further, continue to the Activities for Part 2.1 (Compositions).

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

Skip to the overview of Part 2.2 (Conjugates).

 

The Theorem that Won the War: Activities for Part 2.1 (Compositions)

Author(s): 
Jeff Suzuki (Brooklyn College)

 

  1. Consider the following initial setting for an Enigma encryption:

     

    Diagram of initial setup of reflector and keyboard rotors for some exercises on Enigma machine encryption.

    1. Find \(Q\), the permutation corresponding to the reflector rotor.
    2. Find \(N_{1}\) and \(N_{1}^{-1}\), the permutations corresponding to the keyboard rotor for the first letter of a message.
    3. Find \(E_{1}\), the permutation corresponding to the encryption of the first letter.
    4. Verify \(E_{1} = N_{1}^{-1} QN_{1}\).

Return to the overview of Part 2.1 (Compositions).

Continue to the overview of Part 2.2 (Conjugates).

 

The Theorem that Won the War: Part 2.2 – Conjugates

Author(s): 
Jeff Suzuki (Brooklyn College)

 

In abstract algebra, we introduce the conjugate: \(a, b\) are conjugates in a group \(G\) if there is some element \(g\) where \(a = gbg^{-1}\); equivalently \(g^{-1}ag = b\). While the value of the conjugate is eventually made clear, there's no obvious reason to consider it. The Enigma encryption system offers a natural way to introduce the conjugate; we've already seen that the encryption of the \(k\)th letter can be described using \(N_{k}^{-1}QN_{k}\), so all Enigma encryptions are conjugates of the rotor permutation.

From the preceding, the \(k\)th letter of an Enigma message would be encrypted using the permutation \(E_{k} = N_{k}^{-1} Q N_{k}\). Since \(Q\) doesn't change, and given any permutation \(N_{k}\) we can find its inverse \(N_{k}^{-1}\), let's focus on the keyboard rotor permutation \(N_{k}\).

Let's consider the encryption of the first letter by the keyboard rotor. Suppose our initial setup is as shown below, and the first letter is encrypted by turning the rotor one place:

Diagram showing initial rotor position and its position for first letter encryption.
Figure 14. Rotor positions associated with permutations \(N\) and \(N_1\).

The permutation corresponding to this initial position is \[N = \begin{pmatrix} a    &b    &c    &d    &e    &f\\ c    &e    &d    &a    &f    &b \end{pmatrix}.\]Meanwhile, the permutation corresponding to the first letter encryption is \[N_{1} =\begin{pmatrix} a    &b    &c    &d    &e    &f\\ c    &d    &f    &e    &b    &a \end{pmatrix}. \]Now remember the wiring of the rotor is fixed, so we should suspect there is a way of computing \(N_{1}\) from \(N\). To that end, notice that the actual path used to encrypt the first letter (\(c\) in our example) is the connection between \(b\) and \(e\) in the initial setup.

This suggests another way of looking at the permutation giving the first letter encryption. To encrypt the first letter \(c\) using the initial setup \(N\):

  • Send \(c\) back one place to \(b\),
  • Use \(N\) to encrypt \(b\) as \(e\),
  • Sent \(e\) forward one place to \(f\).

Consequently, we can express \[N_{1} = PNP^{-1}\] where \(P\) is the permutation that shifts letters one place forward and \(P^{-1}\) shifts letters one place backwards. In other words, \(N_{1}\) is conjugate to \(N\).

By a similar argument, our second letter will be encrypted using \(N_{2} = P^{2} N P^{-2}\) and in general the \(k\)th letter will be encrypted using the permutation \(P^{k} N P^{-k}\). Thus all our rotor permutations are conjugates to the original permutation \(N\).

To complete our mathematical description of the paper Enigma, we need to incorporate the effects of the reflector. Remember, in the physical Enigma the reflector sends the electrical signal back through all the rotors. Thus we might describe the mathematical process as follows:

  • The \(k\)th letter is encrypted using the rotor permutation \(P^{k} N P^{-k}\),
  • The reflector permutation \(Q\) is applied,
  • A “backwards” encryption \((P^{k}NP^{-k})^{-1} = P^{k}N^{-1}P^{-k}\) is applied.

Thus the \(k\)th letter of our paper Enigma is encrypted using \[E_{k} = P^{k} N^{-1}P^{-k} Q P^{k} N P^{-k}\]

Finally, the actual Enigma employs an additional plugboard, corresponding to some permutation \(S\), so the actual Enigma permutations can be described as \(S^{-1}P^{k} N^{-1}P^{-k} Q P^{k} N P^{-k}S\) (though again, for our purposes, we'll ignore the plugboard).

To explore these ideas further, continue to the Activities for Part 2.2 (Conjugates).

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

Skip to the overview of Part 2.3 (Cycle Notation).

 

The Theorem that Won the War: Activities for Part 2.2 (Conjugates)

Author(s): 
Jeff Suzuki (Brooklyn College)

 

  1. Find \(P\), the permutation that shifts letters one place forward (so \(a \rightarrow b\), \(b \rightarrow c\), and so on).  Also find \(P^{-1}\).
  2. Prove:  \((P^{k}NP^{-k})^{-1} = P^{k}N^{-1}P^{-k}\).
  3. Consider the following initial setup for an Enigma encryption:


    Diagram of initial setup of reflector and keyboard rotors for some exercises on Enigma machine encryption.

    1. Find \(Q\), the permutation corresponding to the reflector.
    2. Find \(N\), the permutation corresponding to the initial setup of the keyboard rotor. Also find \(N^{-1}\).
    3. Find the permutation \(P\) that shifts each letter one place forward (so \(a \rightarrow b\), \(b \rightarrow c\), and so on).
    4. Find the inverse permutation \(P^{-1}\).
    5. Compute \(PNP^{-1}\).
    6. Compute \(PN^{-1}P^{-1}\).
    7. Find \(E_{1}\), the permutation that will be used to encrypt the first letter.
    8. Verify \(E_{1} = PN^{-1}P^{-1} Q PNP^{-1}\).  (Remember, in our paper Enigma we're ignoring the permutation \(S\) associated with the plugboard.)
    9. Find \(E_{2}\) and \(E_{3}\).
  4. The following explains the significance of the reflector. Using the reflector and keyboard setup shown above, answer the following.
    1. Consider an Enigma-type machine that omitted a rotor, so the \(k\)th letter of a message would use the permutation \(H_{k} = P^{k}NP^{-k}\).  Find \(H_{1}\) and \(H_{1}^{-1}\).
    2. Show that by including the reflector \(Q\), the \(k\)th letter of an Enigma message would use the permutation \(E_{k} = H_{k}^{-1}QH_{k}\).
    3. Find \(E_{1}\) and \(E_{1}^{-1}\).
    4. Why does the reflector make the Enigma encryption easier to use?

Return to the overview of Part 2.2 (Conjugates).

Continue to the overview of Part 2.3 (Cycle Notation).

 

The Theorem that Won the War: Part 2.3 – Cycle Notation

Author(s): 
Jeff Suzuki (Brooklyn College)

 

To proceed, it will be convenient to introduce a second way to represent permutations, known as cycle notation. In a permutation like \[N = \begin{pmatrix}a&b&c &d &e&f\\c&e&d&a&f&b\end{pmatrix},\] the letter \(a\) is sent to \(c\), the letter \(b\) is sent to \(e\), and so on; Cauchy two-line notation is essentially a description of the permutation in tabular form.

But now consider what would happen if we repeatedly applied \(N\). From \(a\) we would be sent to \(c\); from \(c\) we would be sent to \(d\); and from \(d\) we would be sent back to \(a\), at which point we would cycle through \(c, d, a, c\), and so on endlessly. This gives us the orbit \[a \rightarrow c \rightarrow d \rightarrow a \rightarrow \ldots\], which we represent using cycle notation as \((acd)\). Since this cycle has three elements, it is called (unsurprisingly) a 3-cycle. Note that our permutation sends \(d\) to \(a\), so that when reading the cycle notation, the last letter is sent to the first letter.

What if we'd started with \(c\)? Then our orbit would be \[c\rightarrow d \rightarrow a \rightarrow c \rightarrow \ldots \] and our cycle would be \((cda)\). But “things that do the same thing are the same thing,” so the cycle \((acd)\) sends \(a \rightarrow c\), \(c \rightarrow d\), and \(d\rightarrow a\), while the cycle \((cda)\) sends \(c \rightarrow d\), \(d \rightarrow a\), and \(a \rightarrow c\). So \((acd)\) and \((cda)\) do the same things to \(a, c\), and \(d\), we regard them as being the same cycle.

Note that \(N\) also permutes the elements \(b, e, f\). To account for these, we select one and find its orbit; thus the orbit of b will be \[b \rightarrow e \rightarrow f \rightarrow b \rightarrow\ldots\] giving us another cycle \((bef)\). Since all letters have now been acounted for, we can write the cycle decomposition of our permutation \(N\),\[N =(acd)(bef).\]Note that our two cycles have no elements in common; in general any permutation can be written as a product of disjoint cycles. One useful theorem about disjoint cycles:

Theorem. Disjoint cycles commute.

In other words, if we have two cycles with no elements in common, the order we apply them doesn't matter. Thus \[(acd)(bef) = (acd)(bef).\]

One special type of cycle is called a transposition: this is a cycle with two elements, and it corresponds to a permutation where two elements are switched. For example\[M = \begin{pmatrix} a    &b    &c    &d    &e    &f\\f    &c    &d    &e    &b    &a \end{pmatrix} \] breaks into the transposition \((af)\) and the 4-cycle \((bcde)\), while \[N = \begin{pmatrix} a    &b    &c    &d    &e    &f\\e    &d    &f    &b    &a    &c \end{pmatrix} \] breaks into three transpositions \((ae)\), \((bd)\), and \((cf)\).

We note that it's possible for a permutation to include a 1-cycle:\[\begin{pmatrix} a    &b    &c    &d    &e    &f\\c    &d    &b    &f    &e    &a\end{pmatrix}.\] It's customary to omit the 1-cycles in the cycle decomposition, so we would write the cycle decomposition of \(P\) as \((acbdf)\) instead of \((acbdf)(e)\).

To explore these ideas further, continue to the Activities for Part 2.3 (Cycle Notation).

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

Skip to the overview of Part 2.4 (The Message Key).

 

The Theorem that Won the War: Activities for Part 2.3 (Cycle Notation)

Author(s): 
Jeff Suzuki (Brooklyn College)

 

  1. Find the cycle decomposition for the given permutations.
     
    1. \(A =\begin{pmatrix}a    &b    &c    &d    &e    &f\\e    &c    &d    &f    &a    &b\end{pmatrix}\)
    2. \(B =\begin{pmatrix}a    &b    &c    &d    &e    &f\\f    &b    &a    &e    &d    &c\end{pmatrix}\)
    3. \(C =\begin{pmatrix}a    &b    &c    &d    &e    &f\\c    &f    &a    &e    &d    &b\end{pmatrix}\)
  2. Find the cycle decompositions for the Enigma encryptions you found in exercise 3 of Part 2.2 (Conjugates).
  3. Find \(\sigma\tau\) for the given \(\sigma, \tau\).
     
    1. \(\sigma = (ac)(bf)(de)\), \(\tau = (af)(de)(bc)\)
    2. \(\sigma = (ad)(be)(cf)\), \(\tau = (bf)(de)(ac)\)

Return to the overview of Part 2.3 (Cycle Notation).

Continue to the overview of Part 2.4 (The Message Key).

 

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

Author(s): 
Jeff Suzuki (Brooklyn College)

 

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

Diagram showing three possibilities for the initial position of the keyboard rotor in an Enigma coding example..
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.

Diagram showing keyboard rotor set in the a position in an Enigma coding example.
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.

Diagram showing keyboard rotor after advancement of one place in an Enigma coding example.
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.

Diagram showing rotor and reflector setup for an example of message key encryption.
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).

 

The Theorem that Won the War: Activities for Part 2.4 (The Message Key)

Author(s): 
Jeff Suzuki (Brooklyn College)

 

For the activities in this section, we continue with the reflector and keyboard rotor from the final example on the previous page:

Diagram of reflector and keyboard rotor for the Enigma machine.

  1. Use the reflector and keyboard rotor above to encrypt the message \(fade\):
    1. If the message key is \(a\).
    2. If the message key is \(f\).
  2. Suppose a message is received:  \(edc\).  Assume the reflector and keyboard rotors are those shown above, but that the message key was not received.  There are six possible initial settings for the keyboard rotor.  Find all six possible decryptions.

Return to the overview of Part 2.4 (The Message Key).

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