The Theorem that Won the War: 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).