The Theorem that Won the War: Part 2.1 – Compositions

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