After studying the wiring diagrams of the Enigma, determining how the machine works says little about how many permutations are involved in producing its cipher. Recently I started following the accounts and stories of one of the Polish mathematicians behind the earliest decryptions of the Enigma machine--Miran Rejewski. The contributions to the allies' decryption efforts made by him and his colleagues were quite ingenious. Their description of their techniques however are quite daunting.
I think it might be important to first breakdown the variable components of the Enigma and analyze how each component contributed to the vast number of possibilities that any given ciphertext could represent. For explanation purposes, this article will only cover permutations created from a 3-rotor/6-plug Enigma. After December of 1938, right before Hitler ended Germany's nonaggression agreement with Poland, there were significant changes made to the setup required by Enigma operators which made the number of possibilities for any given ciphertext much greater. Nonetheless, the following explanation could serve as a basis for calculating the permutations of the altered Enigma.
Lets first look at an overview of the Enigma's wiring:
(image taken from brej.org)
We can use this diagram to determine the 5 variable factors that compose the cipher. Keep in mind that although the rotors' internal wiring (represented by the various cross-lines in the Rotor columns) were fixed, the external leads for the wiring (represented as the circles connected to such lines) were not fixed with respect to the leads of the neighboring rotors and plugboard.
Factors:
1. The Plugboard (second to right column above)
The plugboard (sometimes called the commutator) had a pretty simple substitution function. Each input from the keyboard sent an electrical signal through the machine which would pass through the rotors only after it passed through one of the 26 leads of the plugboard. Military Enigma operators pre-1939 were given 6 wires, any number of which could be plugged into any two of the 26 sockets of the plugboard. The result would be that letters at the corresponding input/output sockets would be swapped via the cable connected to the board. This essentially changed where inputs from the keyboard would enter the internal wiring of the rightmost rotor. Let's look at the possibilities of plugboard connections:
There's obviously only 1 possible way to arrange 0 cables.
To arrange 1 cable, there are 26 ways to connect one end of the cable to to any given socket, and there are 25 remaining ways to connect the other end to another socket. However, since it does not matter which end is connected between these two sockets, (26 * 25) possibilities would be double counting each dual socket connection, thus the possibilities for one plug is (26 * 25) / 2 = 325 possibilities.
So from this, the following equation can be derived1:
Let n = number of wires used to rearrange inputs on the plugboard. The number of possibilities is thus,
26! / [(26-2n)! * n! * 2n]
n
0 = 1
1 = 325
2 = 44,850
3 = 3,453,450
4 = 164,038,875
5 = 5,019,589,575
6 = 100,391,791,500
Summing these values yields the number of ways the plugboard can map inputs to the rightmost rotor when the operator of the Enigma machine has a choice of 0 through 6 plugboard wires for any of the 26 sockets. Totaling 105,578,918,576 (1.05*1011)
2. Internal wiring of the three rotors
The the rotor could be understood in a similar way to the plugboard, as a substitution function, mapping a given input lead to a fixed output lead. Picture a thick disk with electrical terminals lined around the perimeter on each flat side. Because there are 26 letters and thus 26 different inputs, each side has 26 terminals, each mapped to 1 of the 26 terminals on the other side via internal wiring. Lets examine the possibilities of this internal wiring:
Mapping input terminals to output terminals could be expressed as:
(26 ways for terminal 1) *
(25 remaining ways for terminal 2) *
... *
(1 remaining way for the final input terminal)
= 26! ways to map inputs to outputs for a single rotor.
To compute the possibilities for three rotor wirings may seem like a simple multiplication by 3, but keep in mind that it is most likely not the case (and infact is not) that two or more rotors were wired in the same way; thus the equation is altered slightly to exclude those possibilities in which wirings of multiple rotors were identical:
(26!) * (26! - 1) * (26! - 2)
This gigantic number exceeds 6.5 * 1079 ... And were not even done examining the effect of the rotors yet! Keep in mind these are just the possibilities of the internal wiring. In reality, there was only one unique wiring for each of the 3 rotors. (In later episodes I will discuss how the allies actually determined the real wirings and how I intend to implement these wirings in my simulation)
3. Positioning rotors I, II, and III
It's important at this point to expand upon the behavior of these rotors. So far we have only examined the electrical behavior of the Enigma and at this point, the machine can really only be considered a simple substitution cipher. The use of the three rotors and all of the complicated wiring that goes along with them would virtually provide no additional security to encryption if this is all the machine did. However the mechanical behavior of the Enigma provides an interesting supplement to encryption. At various stages during a given stream of input, certain rotors rotate at intervals of 1/26 of a rotation. Because each rotor's rotations occur at different times, the connection of any given rotor's output terminal to its neighboring rotor's input terminal is constantly changing; each alteration to the interconnections of the rotors provides a new set of substitutions (polyalphabetic substitution). Detailed explanations of when these rotors turn will be covered in the rest of this article. For now, it is only important to keep in mind that each rotor has a period of 26 positions and that before starting encryption of a message, an operator can set each rotor to any of the 26 positions.
So the number of all possible starting positions for three rotors is straight-forward:
26 * 26 * 26 = 263 ways that three rotors can be placed at any of their 26 states.
But wait! Each of the three rotors can also be placed at any of the three rotor positions (i.e the stream of input is just as likely to be passed through I,II,III as III,II,I; or II,I,III etc.). So the above factor must be multiplied by the way to arrange the three rotors:
263 * 3! = 105,456 states of Enigma's rotors
4. Notches and the Ringstellung
So we know that the rotors change states every so often and we know that this causes the substitution mapping to constantly change. This is made possible by a handful of mechanical parts. The first of which is a mechanism in the rightmost slot which causes the residing rotor to "step" to it's successive state every time a key from the keyboard is depressed. This change happens before electrical current is passed through the rotors so that the change has an immediate effect on the input. The leftmost and middle rotors step as a result of another mechanical part which is attached to each rotor--the outer ring. Each rotor is fitted into a ring with letters printed in alphabetical order at each of the 26 steps (commercial Enigma's rings ordered letters the same way that keys appear on the German keyboard).2 This provided a way to differentiate between rotor states, but also was the cause of the stepping behavior of a neighboring rotor to the left. A notch on the rings rotated around with its rotor, and at a certain stage of a rotor's rotation, its notch would be at a given position which would trigger the Enigma to step the neighboring rotor. This triggering happened once every full rotation of a given rotor, so for 26 steps of the first rotor, there would be 1 step of the second, and 26 steps of the second would result in 1 step of the third. Rings for each of the rotors had different notch positions, for example the military Rotor I stepped at ring position "Q".3
So how does this affect the the number of possibilities that the Enigma cipher has? The answer here lies in how a ring is placed onto the circumference of the rotor. In other words, the ring fitting is not fixed but rather can be installed onto the rotor in 26 different ways corresponding to the 26 different stages of the rotor; this was called the rotor's ring setting or ringstellung. So the position of the ring (more specifically its notch position) relative to the order of its rotor's internal wiring has 26 different possibilities. There are 26 possible ways the first rotor can cause the second rotor to step, and likewise there are 26 possible ways the second rotor can cause the third to step.
262 = 676 possibilities for the rotors' mechanical behavior
5. The Reflector
The reflector is what you see at the far left of the above wiring diagram. Its function is to receive the electrical signal from the leftmost rotor's output terminal and send it back through another terminal of the leftmost rotor as input. In this way the signal which spawns from a keystroke makes a path through all three rotors and then is reflected through a completely different path through the same three rotors in reverse order. There is an important thing to be said about a property of the Enigma due to this reflector component which I will discuss in more detail in later episodes. In short, this establishes the transformation of plaintext>>ciphertext to be a mirrored process of the transformation of ciphertext>>plaintext.
Another important thing to realize about the reflector is that it performs the same function as the plugboard if 13 wires were to be plugged into 13 pairs of the plugboard's sockets. This nice observation allows us to borrow the previously used equation to find the number of possible mappings the reflector could be using:
26! / [(26-26)! * 13! * 213] = 7,905,853,580,625
However, like the internal wiring of the rotors, this wiring was fixed for each rotor manufactured for the Enigma so this number of possibilities wasn't exactly at the operator's disposal. Nevertheless, to unknowing cryptanalysts, the number could have very well have been this large.
Result
Multiplying these 5 factors together yields a number so large that observers might assume that such a cipher is unbreakable. And though I am not sure if the Germans ever attempted to approximate this value, there is no doubt that the idea of such vast possibilities left a strong sense of security in Enigma encryption machine.
In the next episode I will bridge the gap between all of this math and the stories of the Polish Cipher Bureau, their mathematical accomplishments, and the dramatic story of French espionage and German treachery!
Annotated References
1. The following article actually details the possibilities for up to 13 wires used on the plugboard. The number of wires with the highest mathematical number of different possibilities is 11 wires. I also have used this source for my calculated figure for the number of reflector possibilites.
The Cryptographic Mathematics of ENIGMA
Cryptologia [0161-1194] Miller yr:1995 vol:19 iss:1 pg:65
[Retrieved from http://ed-thelen.org/comp-hist/NSA-Comb.html]
2. The Brains behind the Enigma Code Breaking before the Second World War
Mathematics and War Raukus-Andersson yr:2003, vol:8 iss:1 pg:416
3. I have gotten a small amount of mixed information on where this notch position really is. However the majority of collected information, both from articles and simulators, suggests the notch positions on the military Enigma I for rotors I, II, and III are at "Q", "E", and "V" respectively. Please comment on any conflicting information you have! Here are some great (some award winning) simulation websites:
http://users.telenet.be/d.rijmenants/en/enigmasim.htm
http://startpad.googlecode.com/hg/labs/js/enigma/enigma-sim.html
http://russells.freeshell.org/enigma/
