Work by the Poles to break the Enigma codes
During the 1930’s, Polish mathematicians worked to determine the inner wiring of the rotors without having the rotors themselves. The names of some of these mathematicians were Marian Rejewski, Henryk Zygalski and Jerzy Rozycki.
Here, in a nutshell, is the mathematical reasoning that was done to deduce the wiring of the rotors. This description is based on the article, "Mathematical Solution of the Enigma Cipher", by Marian Rejewski, which was published in the January 1982 issue of Cryptologia ANCHOR, along with the appendix of The Enigma War, by Jozef Garlinski (ISBN: 0-684-15866-3).
We begin by assigning letters to define certain permutations. For instance, let S represent the permutation of the plugboard. So, S would be the product of a number of transpositions. We can then assign letters to five other permutations:
N = wiring of the fast rotor M = wiring of the medium rotor
L = wiring of the slow rotor R = wiring of the reflector
P = (a b c d e f g h i j k l m n o p q r s t u v w x y z)
So P is the permutation that rotates the letters one position. The goal of the following calculations is to determine N. Keep in mind that we don’t know a priori what the wirings are, but we can use letters to represent them, anyway.
We define some new permutations that are based on the six permutations above.
Q = M L R L-1 M-1
U = N P-1 Q P N-1
V = N P-2 Q P2 N-1
W = N P-3 Q P3 N-1
X = N P-4 Q P4 N-1
Y = N P-5 Q P5 N-1
Z = N P-6 Q P6 N-1
H = N P N-1
Then we define six more permutations based on all the permutations mentioned so far.
A = S (P N P-1) Q (P N-1 P-1) S-1 = S P U P-1 S-1
B = S (P2 N P-2) Q (P2 N-1 P-2) S-1 = S P2 V P-2 S-1
C = S (P3 N P-3) Q (P3 N-1 P-3) S-1 = S P3 W P-3 S-1
D = S (P4 N P-4) Q (P4 N-1 P-4) S-1 = S P4 X P-4 S-1
E = S (P5 N P-5) Q (P5 N-1 P-5) S-1 = S P5 Y P-5 S-1
F = S (P6 N P-6) Q (P6 N-1 P-6) S-1 = S P6 Z P-6 S-1
By studying the "openings" of various coded messages, the Poles were able to deduce the formulas for A, B, C, D, E, and F. Then, through espionage, they were able to find out the formula for S for a given day. (This is a key point. A little outside information was needed to effectively complete these calculations.) Once they knew the formulas for these seven permutations, they could figure out the formulas for U, V, W,and X through the following equations:
U = P-1 S-1 A S P
V = P-2 S-1 B S P2
W = P-3 S-1 C S P3
X = P-4 S-1 D S P4
Once they knew the formulas for these four permutations, they could then form UV, VW, and WX . This was useful because the following three equations are true.
UV = N P-1 (Q P-1 Q P) P N-1
VW = N P-2 (Q P-1 Q P) P2 N-1 = H-1 UV H
WX = N P-3 (Q P-1 Q P) P3 N-1 = H-1 VW H
From the last two equations, the Poles could deduce the formula for H. (Note: this is not easy, but it is doable in part due to a theorem that states that if P and Q are permutations, then Q and PQP-1 have the same cycle structure.) Then, in the same manner, since H = N P N-1, the Poles could deduce the formula for N. An example is below.
Since the Germans switched around which rotor was the fast rotor, over time, the Poles were able to discover the wirings for all of the rotors. As the Germans invaded Poland in 1939, the Polish mathematicians turned over this information to the astonished British. The British then had their own work to do to effectively break Enigma.
An Example
First, by studying "openings" and through espionage, let’s imagine that the Poles were able to come up with the following formulas:
A = (a s)(b r)(c w)(d i)(e v)(f h)(g n)(j o)(k l)(m y)(p t)(q x)(u z)
B = (a y)(b j)(c t)(d k)(e i)(f n)(g x)(h l)(m p)(o w)(q r)(s u)(v z)
C = (a x)(b l)(c m)(d g)(e i)(f o)(h v)(j u)(k r)(n p)(q s)(t z)(w y)
D = (a s)(b w)(c r)(d j)(e p)(f t)(g q)(h k)(i v)(l x)(m o)(n z)(u y)
E = (a c)(b p)(d k)(e z)(f h)(g t)(i o)(j l)(m s)(n q)(r v)(u w)(x y)
F = (a w)(b x)(c o)(d f)(e k)(g u)(h i)(j z)(l v)(m q)(n s)(p y)(r t)
S = (a p)(b l)(c z)(f h)(j k)(q u)
They then can perform some multiplication of permutations to get the following formulas:
U = (a x)(b u)(c k)(d r)(e j)(f w)(g i)(l p)(m s)(n z)(o h)(q t)(v y)
V = (a r)(b v)(c o)(d h)(f l)(g k)(i z)(j p)(m n)(q y)(s u)(t w)(x e)
W = (a s)(b z)(c p)(d q)(e o)(f w)(g j)(h l)(i y)(k r)(m u)(n t)(v x)
X = (a p)(b f)(c u)(d v)(e i)(g r)(h o)(j n)(k y)(l x)(m z)(q s)(t w)
UV = (a e p f t y b s n i k o d)(r h c g z m u v q w l j x)
VW = (a k j c e v z y d l w n u)(s m t f h q i b x o p g r)
WX = (a q v l o i k g n w b m c)(p u z f t j r y e h x d s)
It should not be surprising that the final three permutations have the same cycle structure (two cycles of length 13) since VW = H-1 UV H and WX = H-1 VW H. The Poles would then deduce the formula for H .
H = (a y u r i c x q m g o v s k e d z p l f w t n j h b)
Finally, they would deduce the formula for N using the fact that H = N P N-1.
N = (b z q h y)(c f t v l s m i e o k n w u)(d p r)(g j x)(a)