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