Mechanically, an Enigma machine consisted of a set of encryption drums or rotors. The rotors have contact points on each side, joined by wires. It’s convenient to think of these contact points as representing letters, with the wiring joining two letters of the alphabet. When an operator pressed a letter, an electrical current flowed between the contacts, lighting up the encrypted version of the letter.

For our paper Engima, we’ll consider a six letter alphabet: \(a, b, c, d, e, f\). A “side” view of a rotor might look like the following (the different line styles have no significance, and they are only used to make it easier to distinguish between connections):

Figure 5. Side view of a rotor. All diagrams in
this article were created by the author.

In the diagram in Figure 5, the left-side \(a\) is connected to the right-side \(b\); the left-side \(b\) is connected to to the right-side \(c\); and so on.

Before we can describe this mathematically, we need to make a decision: Since electrical current can flow along a wire in either direction, we must choose a direction, either left-to-right or right-to-left.  For example, if current is flowing from left to right, then the (left side) \(a\) is connected to the (right side) \(b\). Consequently, if the operator pressed \(a\), the current would light up \(b\), which would be the encrypted version.  We might write this as \(a \rightarrow b\).

We can compile all of these left-to-right encryptions in tabular form as
\[\left(\begin{array}{cccccc} a & b&c &d &e &f \\ \downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow \\b&c&f &e&d &a \end{array}\right)\]

Mathematically, we've taken the letters in the order \(a, b, c, d, e, f\), and rearranged them as \(b, c, f, e, d, a\). This is an example of what mathematicians call a permutation.

If we omit the down arrows and enclose everything in parentheses, we can represent our encryption in Cauchy two-line notation:
\[\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&c&f &e&d &a \end{array}\right)\]

Perhaps surprisingly to readers familiar with Stigler’s law of eponymy, Cauchy two-line notation is named after its inventor, Augustin-Louis Cauchy (1789–1857); you can read his original 1815 publication (en Français) here.

What if our current ran from right to left?  In that case, we can represent our permutation as \[\left(\begin{array}{cccccc} a & b&c &d &e &f \\ f&a&b &e&d &c \end{array}\right)\]

 

To explore the basics of rotor design and permutations further, continue to the Activities for Part 1.1 (Rotors).

Return to the overview of Part 1 (Enigma on Paper).

Skip to the overview of Part 1.2 (The Enigma Encryption).

 

 

1. Suppose a rotor has the wiring shown:

   

   1. Describe the permutation if the current is running from left to right.
   2. Describe the permutation if the current is running from right to left.
   3. What do you notice about the two permutations?
2. Draw the side view of a rotor whose right-to-left permutation is given. Then give the left-to-right permutation for the rotor.
   1. \(\left(\begin{array}{cccccc} a & b&c &d &e &f \\ d&f&b&a&c &e \end{array}\right)\)
   2. \(\left(\begin{array}{cccccc} a & b&c &d &e &f \\ c&e&d&a&f &b \end{array}\right)\)
3. Consider a permutation described as \(\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&e&d&c&f &a \end{array}\right)\).
   1. Explain why it is reasonable to say \(\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&e&d&c&f &a \end{array}\right)=\left(\begin{array}{cccccc} a & f&d &b &e &c \\ b&a&e&c&d &f \end{array}\right)\).
       

      Suggestion: “Things that do the same thing are the same thing.”
      We can view a permutation as a function, so the permutation on the left maps a → b, d → e, and so on;
      what does the permutation on the right do?

   2. Rewrite the permutation shown by completing the second row: \[\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&e&d&c&f &a \end{array}\right)=\left(\begin{array}{cccccc}  & & & & & \\ a&b&c&d&e &f \end{array}\right)\]
   3. Rewrite the permutation shown by completing the first row: \[\left(\begin{array}{cccccc} a & d&e &b &c &f \\ b&e&d&c&f &a \end{array}\right)=\left(\begin{array}{cccccc}  & & & & & \\ a&b&c&d&e &f \end{array}\right)\]
4. Consider the permutation \(\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&a&e&c&d&f \end{array}\right)\).
   1. Draw a rotor corresponding to this permutation. (Assume this permutation is for a left-to-right flow of current.)
   2. Find the right-to-left permutation.
   3. Find the first row of the permutation on the right: \[\left(\begin{array}{cccccc} a & b&c &d &e &f \\ b&a&e&c&d &f \end{array}\right)=\left(\begin{array}{cccccc}  & & & & & \\ a&b&c&d&e &f \end{array}\right)\]
   4. Compare the permutations you found in Activity 4b with Activity 4c. Does this suggest an easy way to find the right-to-left permutation from the left-to-right permutation?

 

Return to the overview of Part 1.1 (Rotors).

Continue to the overview of Part 1.2 (The Enigma Encryption).

 

 

 

To encrypt a message, an Enigma operator typed it into a keyboard. When a key was pressed, an electrical signal would pass through a plugboard \(S\); through a sequence of rotors \(R_{1}\), \(R_{2}\), \(R_{3}\); then through a reflector \(Q\) that would send the signal back through the rotors in the reverse order, and then through the plugboard, lighting up the encrypted version of the letter. We can represent this process as encrypting the original plaintext letter \(p\) as the encrypted ciphertext letter \(c\).

Figure 6. Diagram of Enigma encryption process,
beginning with the plaintext letter \(p\) and ending with the ciphertext letter \(c\).

To create the paper Enigma, you’ll need to cut out a set of encryption rotors; a template appears here. For convenience and tractability, we’ll omit the plugboard and use just a single rotor and the reflector; we’ll also reduce our alphabet to six letters \(a\), \(b\), \(c\), \(d\), \(e\), \(f\). These omissions do not substantially alter the process used by the Poles to break Enigma.

Our paper Enigma will require two types of rotors: a “keyboard” rotor and a “reflector” rotor. To prepare a keyboard rotor, draw one-way arrows from one vertex to another. Each vertex should have a unique “outgoing” arrow and a unique “incoming” arrow. Figure 7 below shows some “forbidden” setups and one allowable one. (Note that while you can do a “return” path so that two vertices are connected to each other, it’s discouraged because it’s less interesting.)

Figure 7. Diagrams of various allowable and forbidden “keyboard” rotors.

The reflector rotor is constructed in almost the same way, but this time our arrows are bidirectional and simply join vertices. Again, every vertex must have one and only one connection. The primary problem faced and solved by the Poles was determining the internal wirings of the reflector and the rotor. For our examples, we’ll use the reflector and keyboard rotor in Figure 8.

Figure 8. Diagrams of sample reflector and keyboard rotors.

To make a paper Enigma, set the reflector rotor into the “Reflector” circle and the keyboard rotor into the “Keyboard” circle in the paper Enigma available here. It will help to pin the rotors down through the hole in the center. As a check to make sure you are ready to follow along with the examples below, your initial setup should look something like that shown in Figure 9 below (the dashed line has no significance and is only there to make the process easier to follow).

Figure 9. Initial setup of reflector and keyboard rotors.

In general, a letter will be encrypted by sending it through the keyboard rotor; then the reflector; and then “backwards” through the keyboard rotor.

For example, if we pressed \(a\), then:

• The keyboard rotor would send \(a\) to \(c\),
• The reflector rotor would send \(c\) to \(a\),
• The keyboard rotor would send \(a\) backwards to \(d\).

Thus this setup would encrypt \(a\) as \(d\).

Used this way, Enigma would have been a simple substitution cipher and would have been trivial to break. So the actual Enigma machine incorporated one more feature that vastly compounded the difficulty: every time a key was pressed, the keyboard rotor would advance one place.^[2] 

As an example, let’s encrypt the word \(cab\). When we press the first letter \(c\), the keyboard rotor will advance one place, which we’ll take to be a counterclockwise rotation. Thus the encryption of the first letter would use the setup shown in Figure 10.

Figure 10. Setup for encryption of first letter.

To encrypt the first letter (\(c\)), we’ll send it through the keyboard rotor, the reflector, then “backwards” through the keyboard rotor:

• The keyboard rotor sends \(c\) to \(f\),
• The reflector rotor sends \(f\) to \(e\),
• The keyboard rotor sends \(e\) backwards to \(d\).

So \(c\) is encrypted as \(d\).

Now for the second letter (\(a\)). Again, pressing the key advances the keyboard rotor one place, so the encryption will be based on the configuration in Figure 11.

Figure 11. Setup for encryption of second letter.

To encrypt the second letter of our message (\(a\)):

• The keyboard rotor sends \(a\) to \(b\),
• The reflector sends \(b\) to \(d\),
• The keyboard rotor sends \(d\) backwards to \(b\).

So \(a\) is encrypted as \(b\).

Finally, for the third letter, our rotor shifts one place, as shown in Figure 12.

Figure 12. Setup for encryption of third letter.

Our encrpytion of \(b\) will be:

• The keyboard sends \(b\) to \(c\),
• The reflector sends \(c\) to \(a\),
• The keyboard sends \(a\) backwards to \(f\).

So \(b\) would be encrypted as \(f\). Thus the word \(cab\) would be encrypted as \(dbf\).

To explore the basics of rotor design and permutations further, continue to the Activities for Part 1.2 (Encryption).

Return to the overview of Part 1 (Enigma on Paper).

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

 

Suggestion: The encryption activities are easier if they are done as group activities, with one person calling out the keyboard encryptions and the other the reflector encryptions.

For activities 1–4 in this section, we continue with the example from the previous page, for which the "Initial Setup" was as follows:

1. Consider the initial setup shown above.
   1. Draw a rotor corresponding to the keyboard rotor.
   2. Explain why, when the current is moving right-to-left, we use the encryption \(a \rightarrow c\), but when the current is moving left-to-right, we use the backward encryption \(a \rightarrow d\).
2. Express, in Cauchy two-line notation, the permutation used for the first; second; and third letters in the encryption of the message \(cab\) that we completed on the previous page using the initial setup shown above.
3. Suppose we want to send the message \(cab \, bad\) using the initial setup shown above. Complete the encryption. Ignore the space, so that the \(b\) of \(bad\) will be the fourth letter that needs to be encrypted.
4. An encryption system is not useful unless the recipients can decrypt the messages. Suppose you receive the encrypted message \(dbf\).
   1. “Reset” the paper Enigma to the initial setup shown above. Then encrypt \(dbf\). What do you notice?
   2. Continue on with the rest of your encrypted version of the message \(cab \, bad\). What happens?
5. Notice that the initial placement of the rotors is arbitrary.  Suppose the initial setup of the rotors is as shown below:

    

   

   1. Encrypt the word \(cab\) using this initial setup.
   2. Express, in Cauchy two-line notation, the encryption used for the first; second; and third letters.
6. Now suppose your initial setup is:

    

   

   1. Use this initial setup to encrypt the message: \(faded \, cab\).
   2. Verify that using the same initial setup will decrypt the message correctly.
7. Explain why it is impossible for any rotor and reflector set to encrypt a letter as itself.

Return to the overview of Part 1.2 (The Enigma Encryption).

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

 

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).

 

 

1. Consider the following initial setting for an Enigma 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).

 

 

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:

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).

 

 

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:

   
   

   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).

 

 

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).

 

 

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).

 

 

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).

 

 

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

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).

 

 

To begin to unravel how having two different encryptions for the same letter helped the Allies break the full Enigma code, we start with our paper Enigma.

Since our paper Enigma has only one keyboard rotor, we only need to specify one initial position, so our message key would consist of a single letter. Suppose this unknown letter is \(\alpha\). This would be encrypted by \(E_{1}\) and again by \(E_{2}\); note that these encryptions would be based on the daily key. Other users would choose other message keys, but again encrypt them using the daily key, and we might accumulate a set of intercepted encrypted message keys, say \[\begin{array}{ccccc}cf            &ed       &da       &ae       &fb\end{array}.\]

Let's consider \(cf\). By assumption, this a repetition of our message key \(\alpha\); in other words, it is an encryption, using the daily key, of the “message” \(\alpha\alpha\), in which the first \(\alpha\) is encrypted using \(E_{1}\) and the second \(\alpha\) is encrypted using \(E_{2}\).

Since the first \(\alpha\) is encrypted as \(c\), we know that \(E_{1}(\alpha) = c\); and since \(E_{1}\) is a proper involution—and so it can be expressed as a product of transpositions—we know that \(E_{1}\) includes the transposition \((\alpha c )\). By the same reasoning, we know that \(E_{2}(\alpha) = f\), so \(E_{2}\) must contain the cycle \((\alpha f)\).

Now consider \(E_{2}E_{1}\). Since \(E_{1}\) contains the transposition \((\alpha c)\), and \(E_{2}\) contains the transposition \((\alpha f )\), it follows that \(E_{2}E_{1}(c) = f\).

Note that \(E_{2}E_{1}\) is not an Enigma encryption, so we don't know if it can be written as a product of transpositions. What we do know is part of an orbit of \(E_{2}E_{1}\), namely \(c \rightarrow f\). This means the cycle decomposition of \(E_{2}E_{1}\) contains a cycle of the form \((\ldots cf\ldots)\).

By a similar argument, the intercepted message code \(ed\) means that \(E_{1}(\beta) = e\) and \(E_{2}(\beta) = d\), where \(\beta\) is the unknown message key; consequently, we know part of an orbit of \(E_{2}E_{1}\), \(e\rightarrow d\), so the cycle decomposition of \(E_{2}E_{1}\) contains a cycle of the form \((\ldots ed\ldots)\).

Now consider \(da\). This tells us part of an orbit of \(E_{2}E_{1}\), namely \(d\rightarrow a\). But we already know \(e \rightarrow d\), which means we can extend our orbit. The intercepted \(ae\) tells \(a\rightarrow e\), which closes the orbit: \[e\rightarrow d \rightarrow a\rightarrow e\] and gives us one cycle \((eda)\) in the cycle decomposition of \(E_{2}E_{1}\).

Likewise, the intercepted \(fb\) allows us to extend the other orbit to  \[c\rightarrow f \rightarrow a.\] Note that we are assuming a six-letter alphabet, so \(b\) must be mapped back to \(c\), giving us the cycle \((cfb)\); consequently, \(E_{2}E_{1} = (eda)(cfb)\).

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

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

Skip to the overview of Part 3.2 (Rejewski’s Theorems).

 

 

NOTE: In the following, we'll gradually scale our way up towards the full Enigma encryption on 26 letters.

1. Suppose \(E_{1}, E_{2} \) are two Enigma permutations, and \(E_{1} \) contains \((\alpha c) \) while \(E_{2} \) contains \((\alpha f) \). You should assume both contain a number of other transpositions as well.
   1. Prove: \(E_{2}E_{1} ( c) = f \). (In particular, why can we disregard the effect of the other transpositions in \(E_{2}, E_{1} \)?)
   2. Suppose \(E_{1}, E_{2} \) contained the same transposition \((\alpha\beta) \). Find \(E_{2}E_{1}(\alpha) \) and \(E_{2}E_{1}(\beta) \).
2. Suppose \(\sigma = (ab)(cd)(ef) \) and \(\tau = (ab)(cf)(de) \) are two permutations on six symbols.
   1. Find the product \(\sigma\tau \).
   2. Classify the cycles in the product \(\sigma\tau \). In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
   3.  \((ab) \) is in both \(\sigma \) and \(\tau \). What do you notice about \(a, b \) in the product \(\sigma\tau \)?
   4. The transposition \((cd) \) is in \(\sigma \). What do you notice about \(c, d \) in the product \(\sigma\tau \)?
   5. The transposition \((de) \) is in \(\tau \). What do you notice about \(d, e \) in the product \(\sigma\tau \)?
3. Suppose \(\alpha = (ab)(cd)(ef)(gh) \) and \(\beta = (ad)(bg)(ce)(fh) \) are two permutations on eight symbols.
   1. Find the product \(\alpha\beta \).
   2. Classify the cycles in the product \(\alpha\beta \). In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
   3. What do you notice about the elements of each transposition of \(\alpha \)?
4. Suppose \(\mu = (ab)(ce)(dj)(fg)(kl)(hi) \) and \(\nu = (aj)(cd)(db)(fk)(gl)(hi) \) are two permutations on twelve symbols.
   1. Find \(\mu\nu \).
   2. Classify the cycles in the product \(\mu\nu \).
   3. Suppose \((xy) \) is a transposition in exactly one of \(\mu \) or \(\nu \). What can you say about \(x, y \) in the product \(\mu\nu \)?
5. Note that all the preceding involutions are proper. Suppose \(\kappa = (ab)(cd)(ef) \) and \(\lambda = (ac)(be) \) are two permutations on six symbols.
   1. Find \(\kappa\lambda \).
   2. What happens with products of proper involutions that does not happen when one of the involutions is not proper?

Return to the overview of Part 3.1 (Cycle Decomposition).

Continue to the overview of Part 3.2 (Rejewski's Theorems).

 

 

In the activities for Part 3.1, you might have noticed some intriguing patterns when proper involutions are multiplied:

• The product of proper involutions consists of pairs of cycles of equal length,
• If \((xy)\) is in both involutions, then \(x, y\) appear as 1-cycles in the product of the involutions,
• If \((xy)\) is in exactly one of a pair of proper involutions, then \(x, y\) appear in different cycles of the same length in the product of the involutions.

These patterns are in fact real, for Rejewski proved:

Rejewski’s Theorem.The product of two proper involutions on the same elements can be expressed as a product of pairs of cycles of the same length.

We'll omit the proof here, though it can be found in Rejewski’s paper [Rejewski 1980].

Mathematicians tend to honor theoretical results: hence “Rejewski’s Theorem”. However, this theorem played little role in breaking Enigma, as it simply provides a theoretical guarantee for an observed fact. One is reminded of Hardy’s claim that pure mathematics is useless—the abstract algebra tells us nothing we didn’t already know.

The theorem that actually broke Enigma is an (unnamed) consequence of Rejewski’s Theorem; Rejewski called it a corollary, though its proof is a little more involved than one would expect from a corollary. As with the main theorem, the proof can be found in [Rejewski 1980]. We’ll take the opportunity to give it a name worthy of its significance and call it:

The Enigma Theorem. Let \(\sigma, \tau\) be proper involutions on the same elements. If a transposition \((xy)\) appears in exactly one of the involutions, \(x, y\) will be in different cycles of the same length in the product \(\sigma\tau\); and if \((xy)\) appears in both, \(x, y\) will appear as a 1-cycle in the product.

Consequently, any transposition in exactly one of the \(\sigma, \tau\) must have its elements split between two equal-length cycles in the product.

For example, suppose \(E_{1}, E_{2}\) are proper involutions on our six-letter alphabet, and our intercepted message keys allow us to determine \(E_{2}E_{1} = (afe)(bdc)\). The Enigma theorem permits us to rule out certain possibilities for our encryptions. For example, neither \(E_{1}\) nor \(E_{2}\) can be \((af)(bd)(ce)\), because if either included the transposition \((af)\), then \(a\), \(f\) would be split among different cycles in the product \(E_{2}E_{1}\), instead of being in the same cycle.

There are in fact 15 possible proper involutions on six elements, and so 15 possibilities for each of \(E_{1}\) and \(E_{2}\), and 225 possibilities for the pair of involutions. However, knowing \(E_{2}E_{1} = (afe)(bdc)\) means that \(E_{1}\) and \(E_{2}\) must be one of

\[\begin{array}{cccccc}P             &=               (ab)(fd)(ec)         &Q         &=               (ab)(fc)(ed)         &R         &=               (ad)(fb)(ec)\\S   &=               (ad)(fc)(eb)         &T          &=               (ac)(fb)(ed)         &U         &=               (ac)(fd)(eb)\end{array}\]

Moreover, by the Enigma Theorem, we know that no transposition appears in both. Thus certain choices can be excluded: For example, \(E_{1} = P\) and \(E_{2} = R\) is ruled out, because both contain \((ec)\). In this way, our 225 possibilities for \(E_{1}\) and \(E_{2}\) reduce to just twelve:

• \(E_{1} = P\) and \(E_{2} = S\), or the reverse,
• \(E_{1} = P\) and \(E_{2} = T\), or the reverse,
• \(E_{1} = Q\) and \(E_{2} = R\), or the reverse,
• \(E_{1} = Q\) and \(E_{2} = U\), or the reverse,
• \(E_{1} = R\) and \(E_{2} = U\), or the reverse,
• \(E_{1} = S\) and \(E_{2} = T\), or the reverse.

At this point, we can use trial-and-error (some trial-and-error is necessary in any cryptographic problem); we find \(RQ = (afe)(bdc)\), so \(E_{2} = R\), \(E_{1} = Q\).

To explore these ideas further, continue to the Activities for Part 3.2 (Rejewski’s Theorems).

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

Skip to the overview of Part 3.3 (Breaking the Full Enigma).

 

 

1. Verify the Enigma Theorem for the products of proper involutions in the activities for Part 3.1.
   (That is, for the products \(\sigma\tau \), \(\alpha\beta \), \(\mu\nu \), and \(\kappa\lambda \) in activities 2, 3, 4, and 5 of Part 3.2, respectively.)
2. Let \(E_{1}\), \(E_{2}\) be proper involution on six elements, where \(E_{2}E_{1} = (ade)(bcf)\).
   1. Find the possibilities for the involutions \(E_{1}\), \(E_{2}\).
   2. Find \(E_{1}\), \(E_{2}\).

Return to the overview of Part 3.2 (Rejewski's Theorems.

Continue to the overview of Part 3.3 (Breaking the Full Enigma).

 

 

Now let's turn to the full Enigma system. With three rotors, the message key would consist of three letters. Let the unknown letters be \(\alpha\), \(\beta\), \(\gamma\). Using the daily key, these would be encrypted and sent twice. Suppose Allied codebreakers listened in, and found that \(\alpha\beta\gamma\ \alpha\beta\gamma\), encrypted using the daily code, was \(xkr \, bjs\).

Because we know that this is a three-letter sequence sent twice, then \(x\) and \(b\) are different Enigma encryptions of the same (unknown) letter \(\alpha\). Since \(x\) was the first letter of the message, this tells us

\[E_{1}(\alpha)=x\]

Since \(E_{1}(\alpha) = x\), it follows that cycle decomposition of \(E_{1}\) contains the transposition \((\alpha x)\).

Similarly \(b\), the fourth letter of the message, was encrypted using \(E_{4}\), so we know

\[E_{4}(\alpha)=b\]

and so the cycle decomposition of \(E_{4}\) contains the transposition \((\alpha b)\). Consequently, \(E_{4}E_{1}(x) = b\), so \(E_{4}E_{1}\) must include some cycle \((\ldots xb \ldots)\).

If we could obtain enough messages (and the British generally could), we can extend this cycle. For example, suppose we had another encrypted message key \(bha \, ttr\). Again, the first and third letters are the encryptions of the same plaintext, so this tells us \(E_{4}E_{1}(b) = t\), which allows us to extend our orbit; consequently, \(E_{4}E_{1}\) contains a cycle \(\ldots xbt \ldots\).

As a more detailed example, suppose we intercepted the following encrypted message keys:

\[\begin{array}{ccccc}jju\, ltl   &  \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,     &vxk\, ujs   &    \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,   &edi\, mvd &       &cvk\, nas\\ iro\, afc &     \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,    &urq\, wfo  &      \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,      &wgj\, iug           &      \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,        &sfb \,fbj \end{array}\]

The first intercept \(jju\, ltl\) tells us \(E_{4}E_{1}(j) = l\). This tells us \(E_{4}E_{1}\) includes a cycle \((\ldots jl \ldots)\). Unfortunately, no other intercept has \(l\) in the first position, nor \(j\) in the fourth, so we can't extend our knowledge of the cycle.

The second intercept is \(vxk\, ujs\). This tells us \(E_{4}E_{1}(v) = u\). Notice the sixth intercept is \(urq\, wfo\), which tells us \(E_{4}E_{1}(u) = w\).

The seventh intercept is \(wgj\, iug\), which tells us \(E_{4}E_{1}(w) = i\). Then the fifth intercept \(iro\, afc\) tells us \(E_{4}E_{1}(i) = a\). Put together, we see that \(E_{4}E_{1}\) must contain a cycle \((\ldots vuwia \ldots)\).

In this way, while we don't know the permutations \(E_{4}\) or \(E_{1}\) separately, we can recover cycles in their product \(E_{4}E_{1}\). In a similar way, by looking at the second and fifth letters of each message key, we can begin to recover the cycle decomposition of \(E_{5}E_{2}\); and the third and sixth letters of the message keys will allow us to begin to recover the cycle decomposition of \(E_{6}E_{3}\). In general, the Allies were able to intercept enough encrypted message keys to recover the full cycle decomposition of these products; the Enigma Theorem could then be used to limit the possibilities for the \(E_{i}\)s.

For example, suppose we find \(E_{4}E_{1}\) has cycle decomposition

\[E_{4}E_{1} = (xjlr)(pmhk)(aut)(ocd)(sfe)(yvg)(b)(i)(n)(q)(w)(z),\]

where we could again omit the 1-cycles, but we include them for clarity.

Consider the two 4-cycles. The Enigma Theorem guarantees the transpositions that make up \(E_{1}\) and \(E_{4}\) consist of one of \(x\), \(j\), \(l\), \(r\) with one of \(p\), \(m\), \(h\), \(k\): for example, \((xk)\). Thus, while there are 22 ´ 21 ´ 20 ´ 19 = 175,560 possible transpositions \((x\alpha)\), \((j\beta)\), \((l\gamma)\), \((r \delta)\), the Enigma theorem reduces this down to 24 possibilities. We can then use trial-and-error to determine the actual transpositions in \(E_{4}\) and \(E_{1}\). This last part was handled by the first electromechanical computers: first by the Polish bomba kryptologiczna (“cryptologic bomb” in Polish), and later by Turing's “bombe”. In this way, the Poles, and later the Bletchley Park group, were able to determine the internal wirings of the Enigma rotors and subsequently decrypt most German military communications.

Figure 20. Wartime photograph of a Bletchley Park Bombe, 1945.
Photographer unknown. Wikimedia Commons, public domain.

It’s worth pointing out that this analysis is only possible because of the reflector. Because of the reflector, all Enigma permutations are proper involutions. Sigint efforts gave the Allies knowledge of products of Enigma permutations, and the Enigma Theorem allowed those permutations to be “factored” into the individual Enigma permutations.

To explore these ideas further, continue to the Activities for Part 3.3 (Breaking the Full Enigma).

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

Skip to the Conclusion.

 

 

 

Note:  If you want to produce your own Enigma encryptions, there are several online Enigma emulators, such as this one.

1. Suppose the following message keys are intercepted:\[\begin{array}{lllllll}rsw \,\,\,\,     sia               & \,\,\,\,\,\,\,\,\,\,&pos \,\,\,\, eyc               &\,\,\,\,\,\,\,\,\,\,&zlo \,\,\,\,qks               &\,\,\,\,\,\,\,\,\,\,&qju \,\,\,\,fdv   \\   wyn \,\,\,bci &&ylo \,\,\,\,dks        &&vll \,\,\,\,okm    &&mwn \,mxi\\ktz \,\,\,\,ygl    \,&&llx \,\,\,\,pkz      &&iaf \,\,\,vqp         &&hln \,\,\,\,hki  \\  ohb \,\,\,zwt &&nwl\, gxm     &&blw \,\,\,jka       &&dll\,\,\,\,ckm\\all \,\,\,\,\,wkm   &&xln \,\,aki       &&uwl \,\,uxm     &&gll \,\,\,\,\,kkm\\eln \,\,\,rki       &&slk \,\,\,lkr             &&flx \,\,\,ikz               &&cle \,\,\,\,\,nkk\\pln \,\,\,eki    &&jlb \,\,\,xkt       &&spq \,\,\,lax        &&rry \,\,\,\,slb\end{array}\]
   1. Find as much of the cycle decomposition of \(E_{4}E_{1}\) as possible.
   2. Find as much of the cycle decomposition of \(E_{5}E_{2}\) as possible.
   3. Find as much of the cycle decomposition of \(E_{6}E_{3}\) as possible.
2. Suppose \(E_{4}\) and \(E_{1}\) are proper involutions. Prove the following.
   1. If both contain a transposition \((\alpha\beta)\), then \(\alpha, \beta\) will not appear in any cycle in the product \(E_{4}E_{1}\).
   2. If \(E_{1}\) contains the transposition \((\alpha\beta)\) and \(E_{4}\) contains the transposition \((\alpha\gamma)\), then \(E_{4}E_{1}\) contains a cycle that includes \((\ldots \beta\gamma \ldots)\).
3. Most histories of cryptography claim that the allied decryption efforts were easier because Enigma operators didn't use randomly chosen letters, but rather used sequences that were easy to type.
   1. Suppose all operators used the message code \(aaa\, aaa\). If this was the message code used by all operators, would it be harder or easier to recover \(E_{4}E_{1}\), and subsequently the Enigma encryptions \(E_{4}\) and \(E_{1}\)?  Why/why not?
   2. What if instead of random letter sequences, operators chose three letter words?  Use the Enigma emulator to encrypt repeated three letter words as message codes. Would this practice make it easier or harder to recover the Enigma encryptions?  Why/why not?
4. Some histories of cryptography claim that the Germans ended their messages with “Heil Hitler!” This isn’t true, but suppose it was. Would the use of such a standard closing message make it easier to break Enigma? Why/why not?  Suggestion: The first “H” would be encrypted using \(E_{k}\) for some value \(k\) that depended on the message length. Could this be used to recover \(E_{k}\)?

Return to the overview of Part 3.3 (Breaking the Full Enigma).

Continue to the Conclusion.