Summary of Section 15.1 in Körner

A useful observation about Enigma is that the whole sequence of scrambler rotors and the reflector merely serves to implement a substitution cipher with a particular alphabet, where the particular alphabet is a combination of the rotor wirings, the order in which they are placed in the machine, and their current position. Knowing the wiring of the rotors means that it is possible to produce an ordered listing of the 26³ cipher alphabets that result from turning the rotors through all of their positions. (If it is not known which rotors were put in the machine and/or which order they were put in, then it is necessary to consider the listings that result from each possible rotor choice/ordering combination.) Successfully deciphering the message then means figuring out which of the 26³ cipher alphabets was used for the first letter of the message.

At this stage it might be possible to try each of the 26³ cipher alphabets as the starting point for the message - after all, it should be apparent fairly quickly if the setting leads to intelligible text. However, there's a problem - the ciphertext you get for a particular plaintext message depends not only on the scrambler settings, but also on the plugboard. If you have the plugboard settings wrong, typing in the ciphertext may not give you anything that makes sense even if you have the scrambler settings right. Furthermore, the number of possible plugboard settings is way too large to try by brute force.

There is a shortcut, however, if you know (or guess) some of the plaintext of the message. (This guess is known as a crib.) Consider the following table (Table 15.2 from Körner):

	plaintext	scrambler cipher alphabet																										ciphertext
		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
1	T	J	F	Z	X	H	B	S	E	K	A	I	Y	Z	T	V	U	C	W	G	N	P	O	R	D	L	M	A
2	H	P	N	S	K	U	Z	O	W	V	L	D	J	R	B	G	A	T	M	C	Q	E	I	H	Y	X	F	L
3	E	K	D	P	B	I	Q	T	M	E	O	Z	N	H	L	J	C	F	T	G	R	X	Z	Y	U	W	V	A
4	G	X	O	D	C	H	Z	L	E	P	Y	U	G	Q	W	B	I	M	V	T	S	K	R	N	A	J	F	P
5	E	O	F	Y	E	D	B	Z	X	L	W	Q	I	N	M	A	S	K	V	P	U	T	R	J	H	C	G	H
6	N	V	W	P	T	M	X	K	U	O	L	G	J	E	Z	I	C	R	Q	Y	D	K	A	B	F	S	N	Q
7	E	D	R	T	A	G	U	E	M	Z	K	J	X	I	V	Y	W	S	B	Q	C	F	N	P	L	O	I	N
8	R	V	Z	E	J	C	Q	U	N	L	D	Y	I	R	H	W	X	F	N	T	S	G	A	O	P	K	B	S
9	A	H	X	I	Z	G	P	E	A	C	Y	O	V	S	T	K	F	W	U	M	N	R	L	Q	B	J	D	N
10	L	H	V	X	M	Z	I	K	A	F	S	G	W	D	Q	U	R	N	P	J	Y	O	B	L	C	T	E	T
11	H	O	W	M	P	Y	L	T	Z	K	X	I	G	C	U	A	D	R	Q	V	F	N	S	B	J	E	H	T
12	E	R	U	Z	L	J	Y	I	T	F	E	M	D	K	X	Q	R	O	A	P	H	B	W	V	N	F	C	L

The left column shows the crib (THEGENERALHE) and the rightmost column shows the ciphertext where the crib is aligned (ALAPHQNSNTTL). We can verify that this is a plausible alignment for the crib by checking that the plaintext and ciphertext letters are never the same on a particular row. The middle column shows the cipher alphabet implemented by the current scrambler settings - the alphabet in the first row corresponds to the initial scrambler settings, and the alphabets on subsequent rows result from advancing the scramblers by one step from the previous setting.

The goal is to determine if the Enigma setting which yields the cipher alphabet on the first row (JFZXHBSE...) is the correct setting for deciphering the message. If it is, then enciphering T by applying the plugboard, using the alphabet JFZXHBSE..., and applying the plugboard again should yield A; enciphering H by applying the plugboard, using the alphabet PNSKUZOW..., and applying the plugboard again should yield L; etc.

Since we don't know how the plugboard is set up, let's make a guess - say A<->A. (This notation means that the plugboard transforms A into A - i.e. A is not affected by the plugboard.) We now proceed to discover other plugboard settings based on this. Since we made an assumption about the plugboard settings for A, let's start with row 9 of the table:

1. First apply the plugboard to the plaintext A, yielding A.
2. Next, encipher A using the scrambler - look for the letter on the current row in column "A" - this is H.
3. Now we know that H must become ciphertext N (because plaintext A comes out as ciphertext N) and the only thing left to do is apply the plugboard again, so there must be a plugboard setting H<->N.

At this point, we have our plugboard settings as A<->A, H<->N, B<->L, U<->Q, X<->L. But there's a problem - L can't be transformed to both B and X. Since this is an impossible situation, something must be wrong - the assumption that A<->A is the plugboard setting must be incorrect.

So, we move on to the next possibility (A<->B) and repeat the same procedure. (Actually, A<->B could be skipped given the knowledge it is wasn't allowed to switch a letter with its neighbor. But we'll ignore that knowledge here.) Working with A<->B gives us X<->N (from row 9) and F<->Q (row 6). At this point we're stuck - we've tried all the rows with A, B, X, N, F, or Q as plaintext letters. However, the process can also be applied in reverse, using the ciphertext letters - on row 1, the ciphertext A must have been the result of B coming out of the scramblers, so we find a B in the cipher alphabet on row 1 and discover that it must have come from an input letter of F because it is in column F. Since F must have come from applying the plugboard to the plaintext T, we get F<->T as another plugboard setting. At this point, there's a contradiction again - we can't have both F<->Q and F<->T as plugboard settings.

Repeat the procedure for the remainder of the possible plugboard settings for A (A<->C, A<->D, etc). Considerable shortcuts are possible. One is based on not stopping when the first contradiction is found - if you keep going with A<->B until you can't derive any more settings, you'll get a huge list: A<->A, A<->B, A<->C, A<->D, A<->E, A<->F, A<->G, A<->H, A<->I, A<->J, A<->K, A<->L, A<->M, A<->N, A<->O, A<->P, A<->Q, A<->R, A<->S, A<->T, A<->U, A<->V, A<->W, A<->X, A<->Y, A<->Z, B<->E, B<->H, B<->L, B<->N, B<->Q, B<->T, C<->E, C<->H, C<->L, C<->N, C<->Q, C<->R, C<->S, C<->T, D<->E, D<->H, D<->L, D<->N, D<->Q, D<->T, E<->E, E<->F, E<->G, E<->H, E<->I, E<->J, E<->K, E<->L, E<->M, E<->N, E<->O, E<->P, E<->Q, E<->R, E<->S, E<->T, E<->U, E<->V, E<->W, E<->X, E<->Y, E<->Z, F<->H, F<->L, F<->N, F<->Q, F<->R, F<->S, F<->T, G<->G, G<->H, G<->L, G<->M, G<->N, G<->P, G<->Q, G<->S, G<->T, G<->W, G<->X, H<->H, H<->I, H<->J, H<->K, H<->L, H<->M, H<->N, H<->O, H<->P, H<->Q, H<->R, H<->S, H<->T, H<->U, H<->V, H<->W, H<->X, H<->Y, H<->Z, I<->L, I<->N, I<->P, I<->Q, I<->R, I<->S, I<->T, J<->L, J<->N, J<->Q, J<->T, K<->L, K<->N, K<->Q, K<->T, L<->L, L<->M, L<->N, L<->O, L<->P, L<->Q, L<->R, L<->S, L<->T, L<->U, L<->V, L<->W, L<->X, L<->Y, L<->Z, M<->N, M<->P, M<->Q, M<->R, M<->T, N<->N, N<->O, N<->P, N<->Q, N<->R, N<->S, N<->T, N<->U, N<->V, N<->W, N<->X, N<->Y, N<->Z, O<->Q, O<->T, P<->Q, P<->S, P<->T, P<->W, P<->X, Q<->Q, Q<->R, Q<->S, Q<->T, Q<->U, Q<->V, Q<->W, Q<->X, Q<->Y, Q<->Z, R<->S, R<->T, R<->U, R<->V, R<->X, S<->S, S<->T, S<->V, T<->T, T<->U, T<->V, T<->W, T<->X, T<->Y, and T<->Z. (Körner calls these long sequences "avalanches".) Furthermore, if you start with any of these settings you'll generate the entire list - you didn't have to start with A<->B. What this means is that if you start with a new setting such as A<->C, if you ever derive a setting you've already seen when finding a contradiction (such as A<->A, H<->N, B<->L, U<->Q, X<->L or A<->B, X<->N, F<->Q, F<->T) then you'll know you'll get a contradiction eventually and you can stop right away.

So, repeating the procedure for the remainder of the possible plugboard settings for A (A<->C, A<->D, etc) yields a contradiction for every one. What is the conclusion? No matter what the plugboard setting is for A, this particular starting scrambler setting could not have generated the observed ciphertext. As a result, either the scrambler setting is not the right one or the crib is wrong. Continuing to assume that the crib is correct, we would then proceed to another scrambler setting and repeat the process.

What happens if the scrambler setting is correct? Consider Table 15.3 from Körner:

	plaintext	scrambler cipher alphabet																										ciphertext
		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
1	T	J	F	Z	X	H	B	S	E	K	A	I	Y	Z	T	V	U	C	W	G	N	P	O	R	D	L	M	G
2	H	P	N	S	K	U	Z	O	W	V	L	D	J	R	B	G	A	T	M	C	Q	E	I	H	Y	X	F	F
3	E	K	D	P	B	I	Q	T	M	E	O	Z	N	H	L	J	C	F	T	G	R	X	Z	Y	U	W	V	N
4	G	X	O	D	C	H	Z	L	E	P	Y	U	G	Q	W	B	I	M	V	T	S	K	R	N	A	J	F	A
5	E	O	F	Y	E	D	B	Z	X	L	W	Q	I	N	M	A	S	K	V	P	U	T	R	J	H	C	G	I
6	N	V	W	P	T	M	X	K	U	O	L	G	J	E	Z	I	C	R	Q	Y	D	K	A	B	F	S	N	B
7	E	D	R	T	A	G	U	E	M	Z	K	J	X	I	V	Y	W	S	B	Q	C	F	N	P	L	O	I	F
8	R	V	Z	E	J	C	Q	U	N	L	D	Y	I	R	H	W	X	F	N	T	S	G	A	O	P	K	B	J
9	A	H	X	I	Z	G	P	E	A	C	Y	O	V	S	T	K	F	W	U	M	N	R	L	Q	B	J	D	B
10	L	H	V	X	M	Z	I	K	A	F	S	G	W	D	Q	U	R	N	P	J	Y	O	B	L	C	T	E	B
11	H	O	W	M	P	Y	L	T	Z	K	X	I	G	C	U	A	D	R	Q	V	F	N	S	B	J	E	H	L
12	E	R	U	Z	L	J	Y	I	T	F	E	M	D	K	X	Q	R	O	A	P	H	B	W	V	N	F	C	A

Again, let's start with the assumed plugboard setting A<->A. Then H<->B (row 9), N<->F (row 2), W<->L (row 11), X<->B (row 6) - contradiction. You can continue with A<->B and A<->C and will again discover contradictions. Let's next try A<->D: Z<->B (row 9), N<->N (row 6, using it in reverse), E<->L (row 10, in reverse), I<->I (row 5), X<->F (row 7), H<->Y (row 11, in reverse), G<->C (row 4, in reverse), Q<->T (row 1, in reverse). At this point, there are no additional plugboard settings to be deduced - and yet, no contradiction has been found. This means that the initial scrambler setting is a plausible one for this message - and, as a side effect, we've discovered some of the plugboard settings as well. If you continue on and try the remaining combinations for A (A<->E, A<->F, etc), you'll discover that they all end in contradiction as well.

The result is that it is possible to distinguish a correct scrambler setting from an incorrect one - try all of the plugboard possibilities for A (or any other letter). If a contradiction is found for every possibility, the scrambler setting must be incorrect. If no contradiction is found, the scrambler setting may or may not be the right one. "False positives" are possible if the crib is too short, because you may not have enough information to deduce a contradiction even if one exists. For example, try A<->D for the first table (Table 15.2) but consider only the first six rows. (In other words, pretend the crib is only "THEGEN".) No contradiction is found, leading one to believe that this is a correct setting even though we have already shown that it isn't. However, eliminating settings with known contradictions reduces the possibilities, and with luck the remaining settings are few enough to check by hand.

The description of Turing's bombes from class involved looking for cycles between plaintext and ciphertext letters. Using the cycles boils down to using only certain rows of the table rather than all of them. In order to check settings, a bombe needed to link a number of Enigma machines equal to the number of rows being used - the 12-row example used above would require a 12-machine bombe. Practical requirements meant there was an upper bound on what could be put into a bombe, and thus an upper bound on the number of rows that could be used. Given that only a limited number of rows of the crib could be used, it was desirable to pick those rows which would be most likely to lead to contradictions if contradictions existed. (Otherwise many more false positives would be found.) This is the reason behind looking for cycles - rows with this type of pattern were more conducive to finding contradictions and thus eliminating incorrect settings.