Simple Enigma Cryptanalysis
Burton Rosenberg
25 January 2003.
One method for breaking the German Enigma depended on the
repeat of a three letter message key at the beginning of the
message. The three letter key was sent using the daily setting
and was the setting for the remainder of the message. It
was sent twice to reduce error.
Eventually German operators stopped doing this and other
methods were needed.
We illustrate the analysis with a vastly reduced Enigma
machine. It has one rotor and a six letter alphabet.
There is no sticker board, but this is not important for
this attack. We assume that
the message opens with a single letter code repeated twice
and calculate the cycle structure of a certain product permutation.
We will see that the cycle structure of the permutation depends on
the initial setting of the rotor. Although the cycle structure does
not completely identify the initial setting, it narrows the
possibilities, and the sticker board has no effect.
Our enigma has the following structure. The reflecting wheel
implements the permutation
r = (1 2)(3 4)(5 6).
The single rotor implements the permutation
s_0 in its zero position, and s_i in its i-th
position. s_i=s_{i mod 6}
After each character the rotor turns one position.
The enciphering of the i-th character is:
a_i = s_i r s_i^{-1}
(reading permutations left to right) where
s_i = t^i s t^{-i}
where t is the permutation simulating the turning of the rotor
by one
t = (1 2 3 4 5 6)
Since the first cleartext character
is repeated, say xx, if the ciphertext begins yz then:
x = a_0^{-1}(y) = a_1^{-1}(z)
z = a_0 a_1 (y)
since a_i has the same cycle structure as r,
it is involutory, thus eliminating the inverse notation.
We have one sample of the product permutation a_0 a_1.
With additional messages we reconstruct a_0 a_1. The cycle
structure depends on the initial setting.
We investigate three different rotor permutations.
The calculations were done in mathematica. The function enc1
is the enciphering function s r s^{-1}. The tws1 function is
the "twist" function, simulating the turn of the rotor, t s t^{-1}.
The composition permutation a_i a_{i+1} is computed for all i.
Rotor 1
s = (1)(2 3)(4 5 6).
Odd initial settings have
cycle structure two three-cycles, even intial settings have
cycle structure a pair of two-cycles and a pair of fixed points.
This cuts key search in half.
A larger Enigma would have a richer vocabulary of cycle structures,
cutting the key space by a greater fraction, and the sticker board
is rendered irrelavant.
Rotor 2
s = (1 2 3 4)(5 6)
This demonstrates that some choices of rotors are unfortunate.
The sequence of permutations s_i repeat themselves.
In particular
a_0=a_3, a_1=a_4, a_2=a_5.
Rotor 3
s = (1 2 3)(4 5 6)
This demonstrates that certain rotors prevent this attack.
All products a_i a_{i+1} have similar cycle structure.
In this case, a pair of three cycles.