Finding the Enigma wiring by boxing

• Rejewski's break of the
  Enigma rotor wiring
• Elizebeth Friedman's break of the
  Enigma rotor wiring
• Breaking of the Commercial Enigma by Germans
• Buttoning-up
• Adding-up
• Boxing. This Page.
• Rodding
• Rejewski's Catalog
• Cyclometer
• Rejewski's Bombe
• Zygalski's Sheets
• Turing's Bombe
• Turing / Welchman Bombe

Introduction

In his treatise on the Enigma written in 1940, Alan Turing presents in chapter 3, two methods for finding the rotor wiring of an Enigma. At the end of the chapter he deals with the adding-up method a priori invented by Dilly Knox. But first, he presents another method that I personally call "Boxing" because the important concept of Box is used but also to differentiate it from the adding-up method.

Mathematical vision of the Enigma encryption

Let’s start by recalling the mathematical functioning of the Enigma.

Note: In this chapter we will use our Simplified Enigma view but with two rotors.

• E = Permutation of the Enigma with the rotor positions at i (for right rotor), and j (for middle rotor).
• N = Permutation of the Rotor at the right position (the fast rotor)
• M = Permutation of the middle rotor
• U = Reflector permutation (which includes the permutation of the left rotor)
• P = Permutation of the rotation.

Turing's Vocabulary: Alphabets, Rods, ...

Concept of Alphabet, constatations

Here are some alphabets using our simplified Enigma with 6 contacts and two rotors:

• \( E_{0,0} = ((1,0)(2,5)(3,4)) \)
• \( E_{0,1} = ((0,4)(1,5)(2,3)) \)
• \( E_{2,0} = ((0,3)(1,4)(2,5)) \)
• \( E_{2,1} = ((0,1)(2,3)(4,5)) \) N at position 1 and M at position 2.

A constatation is simply a transposition that corresponds to the encryption of a letter. If the letter 0 is encrypted as 1, the letter 1 is encrypted as 0. This reciprocal encryption is expressed by the transposition (0,1).

An alphabet is therefore composed of a sequence of constatations.

Note: This page uses a special notation for permutations. Additionally, we use the Python Sympy library to perform the calculations. I describe the permutations, the notations used, and Sympy in my page dedicated to rotors.

Rod Squarre, Rod, Beetle, Upright, Qwertzu, Adding-up / Buttoning-up

A Rod Square is simply the decryption table for a rotor. The x-axis shows the rotor position and the y-axis shows the ciphered letters. The table contains the plain letters.

In the following example, the plain letter 5 is encrypted as the letter 2 at position 0 and the plain letter 2 as the letter 5 at position 3.

Rotor                Reverse Rotor 
                     (Rod Squarre)
    0 1 2 3 4 5          0 1 2 3 4 5
---------------      ---------------
0 | 0 0 2 0 1 3      0 | 0 0 3 0 4 5
1 | 1 3 1 2 4 1      1 | 1 4 1 5 0 1
2 | 4 2 3 5 2 2      2 | 5 2 0 1 2 2
3 | 3 4 0 3 3 5      3 | 3 1 2 3 3 0
4 | 5 1 4 4 0 4      4 | 2 3 4 4 1 4
5 | 2 5 5 1 5 0      5 | 4 5 5 2 5 3

A Rod is simply a row of a Rod Square. It corresponds to the different plain letters that are encrypted with the same ciphered letter at different rotor positions.

A Beetle corresponds to a pair of contiguous letters on a Rod.

The Upright is the left column of a Rod Square. It corresponds to the reverse of the rotor wiring. In the Boxing and Adding-up methods, knowledge of the Upright is the objective.

Qwertzu is simply the fixed permutation made before the rotor permutation (also called ETW). In a Rod Square, this Qwertzu appears as the diagonals (which descend from top right to bottom left). With our simplified Enigma, there is no ETW, and therefore Qwertzu corresponds to the Identity permutation (0, 1, 2, 3, 4, 5). The same is true for the military Enigma (ABC...Z). However, in the case of the commercial Enigma, Qwertzu actually corresponds to the permutation (QWERTZU...BNML).

Adding-up or buttoning-up, in the narrow sense consist of replacing a plain letter in the Rod Square with the equivalent plain letter in the Upright column, moving down the diagonals (Qwertzu). This operation is obviously central in the methods of the same name.

Basic Terminology of Permutations

Alan Turing preferred to use the term substitution instead of the currently used term permutation.

Conversely, Turing used the term permutation to express the operation of composition.

Turing uses the term class or shape to denote the type of a permutation.

Finally, to indicate that a permutation is conjugate, Turing used the term "subjected."

miscellaneous

"hatted" which means random.

Boxing method, the basis

Vocabulary complements: Boxes and Compartments

Turing, building on Rejewski's work, realized that the composition of two Alphabets has special properties. Turing calls this composition a Box. This Box is composed of one or more Compartments. Each Compartment is composed of two cycles of the same length. A compartment is constructed from a sequence of transpositions coming from the two Alphabets.

Turing teaches us that a Box completely determines the Alphabets from which they are constructed. Expressed differently, we can say that Alphabets can be deduced from a Box.

1st Example: Consider the following two alphabets:

	E01 = ((0,4)(1,5)(2,3))
	E21 = ((0,1)(2,3)(4,5))

	E21.E01 = ((0, 5), (1, 4), (2), (3))

2nd Example:

	E00 = ((1,0)(2,5)(3,4))
	E10 = ((0,5)(1,3)(2,4))
	E00.E10 = ((0,3,2)(1,5,4))

Turing's representation of a Box

Turing represents a Box vertically. Each compartment is separated by a line. Each cycle appears vertically. The diagonals represent the first permutation (for example (3,4), (2,5), (1,0) correspond to the permutation E00).

1st Example	2nd Example
	0 4		0 4			
	5 1		3 5
	---		2 1
	2 3		=== 	
	===

Factorization (Rejewski's formula)

Each compartment is made up of two cycles of the same length. Here is the formula (invented by Rejewski) that connects these two cycles to the transpositions which come from the two Alphabets:

\( XY= ((x_1 x_3 x_5 … x_{2n-1}) (y_{2n} … y6 y4 y2)), \) then we have
\( X = ((x_1 y_2)(x_3 y_4) … (x_{2n-1} y_{2n})) \quad \textrm{and} \quad Y = ((y_2 x_3) (y_4 x_5) … (y_{2n} x_1)) \)

The cycles \( (x_1, x_3, x_5, …, x_{2n-1}) \quad \textrm{and} \quad (x_3, x_5, …, x_{2n-1}, x_1) \quad \) give different factorizations.

1st Example:
Let's return to the previous example: Our Box, constructed from the two alphabets A1 and A2, is composed of two compartments, VW and XY:

	VW = ((0,5)(1,4))
	V = ((0,1)(5,4)) and W = ((1,5)(4,0))

	XY = ((2)(3))
	X = ((2,3)) and Y = ((2,3))
	
	A1 = ((0,1)(5,4)(2,3)) and A2 = ((1,5)(4,0)(2,3))

2nd Example:

	XY = ((0,3,2)(1,5,4))
	X1 = ((0,4)(3,5)(2,1)) and Y1 = ((4,3)(5,2)(1,0))
Other solutions:
	X2 = ((3,4)(2,5)(0,1)) and Y2 = ((4,2)(5,0)(1,3))
	X3 = ((2,4)(0,5)(3,1)) and Y3 = ((4,0)(5,3)(1,2))

Alphabets, Boxes, and Conjugation

When you have two alphabets (\( \alpha, \beta \)), it is preferable to use the composition of these alphabets (called Box by Turing) rather than the alphabets directly.

If we conjugate two alphabets separately by the same permutation, the conjugation of the composition by this same permutation corresponds to the composition of conjugations:

\( \mu = \gamma \; \alpha \; \gamma^{-1} \)
\( \rho = \gamma \; \beta \; \gamma^{-1} \)

\( \gamma \; (\alpha \; \beta ) \; \gamma^{-1} = \mu \; \rho \)

Note: The boxes \( \alpha \beta \) and \( \mu \rho \) have the same shape.

We have just stated nothing more nor less than the following theorem (from Rejewki): If two couples of alphabets (\( \alpha,\beta \) ) and (\( \mu,\rho \) ) such that the sizes of the compartments of the box \( \alpha,\beta \) are the same as the box \( \mu \rho \), then we can find a permutation (\( \gamma \)) that allows the conjugation.

The gamma permutation

The Boxing method relies on knowledge of gamma substitution. This permutation allows you to transform a letter in column i into a letter in column j in the Table Rod Square that defines the rotor (N). But this same substitution also allows you to conjugate an Alphabet (E) into the neighboring Alphabet. Thus, ultimately, if you know gamma, you can deduce the wiring of the rotating rotor.

\( \gamma = N^{-1}_{j} N_i \)
\( E_j = \gamma \; E_i \; \gamma^{-1} \)

These formulas apply to adjacent columns, so j=i+1. Since N is the permutation that describes the fast rotor, if i=0, we have \( N_{0}^{-1} \) which corresponds to the Upright.

According to the formula that relates a composition to an inverse composition:
\( N^{-1}_{j} = ( \; P \; N_i \; P^{-1} \; )^{-1} = P \; N^{-1}_i \; P^{-1} \)
Then:
\( P^{-1} \; \gamma = P^{-1} \; P \; N^{-1}_i \; P^{-1} \; N_i \)
\( P^{-1} \; \gamma = N^{-1}_i \; P^{-1} \; N_i \)

If we take the inverse permutations of the two sides of the equation, we get:
\( \gamma^{-1} \; P = N_i \; P \; N^{-1}_i \)

We note that: \( \gamma = P \; N_{i}^{-1} \; P^{-1} \; N_i \)

Note: The permutation P corresponds to the rotation. This is only correct if the diagonal (Qwertzu) corresponds to the Identity, which is the case for the military Enigma. In the case where the Qwertzu is known, this is the permutation that must be used instead of P.

Saga, example with Sympy

In this section, we will not reconstruct the entire wiring of an Enigma, but only the wiring of the fast rotor of our simplified Enigma. Therefore, we only need a few alphabets.

The data collected by the spy

The spy records four alphabets at different positions of the N and M rotors.

• E00 = ((1,0)(2,5)(3,4)) N at position 0 and M at position 0.
• E10 = ((0,5)(1,3)(2,4))
• E01 = ((0,4)(1,5)(2,3)) N at position 1 and M at position 0.
• E11 = ((0,2)(1,4)(2,4))
• E20 = ((0,3)(1,4)(2,5))
• E21 = ((0,1)(2,3)(4,5)) N at position 1 and M at position 2.

Calculate the boxes

There is a permutation (gamma) that transforms the Alphabet E00 into the Alphabet E01, but also E10 into E11 and E20 into E21. To find this substitution, we form the boxes delta1 (E00.E10), delta2 (E01.E11), delta3 (E00.E20) and delta4 (E01.E21). Indeed, this gamma substitution must also transform delta1 into delta2 and delta3 into delta4.

With Sympy:

>>> from sympy.combinatorics import Permutation
>>> E00 = Permutation([[1,0],[2,5],[3,4]])
>>> E01 = Permutation([[0,4],[1,5],[2,3]])
>>> E10 = Permutation([[0,5],[1,3],[2,4]])
>>> E11 = Permutation([[0,2],[1,4],[3,5]])
>>> E20 = Permutation([[0,3],[1,4],[2,5]])
>>> E21 = Permutation([[0,1],[2,3],[4,5]])
>>>
>>> delta1 = E00 * E10
>>> delta1
Permutation(0, 3, 2)(1, 5, 4)
>>> delta2 = E01 * E11
>>> delta2
Permutation(0, 1, 3)(2, 5, 4)
>>> delta3 = E00 * E20
>>> delta3.full_cyclic_form
[[0, 4], [1, 3], [2], [5]]
>>> delta4 = E01 * E21
>>> delta4.full_cyclic_form
[[0, 5], [1, 4], [2], [3]]
>>>

Calculate gamma

We know delta1 and delta2. If we want to find gamma, we just put delta1 under delta2 and assume that it is the encryption of delta2. In fact, gamma can also be calculated from delta3 and delta4.

Unfortunately, for each pair (delta1/delta2 and delta3/delta4), there are several solutions. The correct gamma value is the one that is common to both pairs.

	delta2	=  ((0,1,3)(2,5,4))		((0,1,3)(2,5,4))	
	delta1 =   ((0,3,2)(1,5,4))		((0,3,2)(5,4,1))
	g21a = ((0),(1,3,2),(5)(4)	g21b = ((0),(1,3,2,5,4))	...

	delta4 = ((2)(3)(0,5)(1,4))		((2)(3)(0,5)(1,4))
	delta3 = ((5)(2)(0,4)(1,3))		((5)(2)(0,4)(3,1))
	g43a  = ((2,5,4,3)(0)(1))	g43b = ((2,5,4,1,3)(0))		...

We can check with Sympy that the gamma value that we found is well combined with the boxes but also directly with the alphabets.

>>> gamma = Permutation(0)(1,3,2,5,4)
>>> gamma * delta1 * (~gamma)  == delta2
True
>>> gamma * delta3 * (~gamma)  == delta4
True
>>> gamma * E00 * (~gamma)  == E01
True
>>> gamma * E10 * (~gamma)  == E11
True
>>> gamma * E20 * (~gamma)  == E21
True
>>>

Reconstitution of the permutation N (the fast rotor)

If we take the formula which links gamma to the rotor wiring (N) and we set i=0, we have:

\( \gamma^{-1} \; P = N_0 \; P \; N^{-1}_0 \)

We have a conjugation, so we can calculate N as we did previously. We obviously have several solutions, for example:

	~gamma * P = ((0,1,5,3,2,4))
	P          = ((0,1,2,3,4,5))
	N0	   = ((0)(1)(5,2,4)(3))

>>> P
Permutation(0, 1, 2, 3, 4, 5)
>>> ~gamma * P
Permutation(0, 1, 5, 3, 2, 4)
>>> ~gamma * P == N0 * P * ~N0
True
>>>

Boxing and Cryptanalysis

The study of the machine

Alan Turing presents the Boxing method in an espionage context, adding immediately afterward that this use is highly unlikely. He then indicates that his method allows a better understanding of the Enigma and that it can be used in more probable methods.

Using the method through spying

Although Turing thought it highly unlikely that espionage would be used to find the wiring of an Enigma, he outlined the steps to be taken in this case.

If a spy can gain access to an Enigma for half an hour, he will have to record certain alphabets and a few constatations. Then, a cryptanalyst (like Turing) can deduce the wiring of the fixed elements and those that can move, in short, the rotors, the Qwertzu, and the Reflector. The steckers must be either absent or known.

The spy must record 11 alphabets (although he specifies that 9 may be sufficient): the alphabet at positions AAA, AAB, AAC, AAD, ABA, ABB, ABC, ACA, CAA, BAA, and CAD. In addition, he must also record two observations for each position ACB, ADA, DAA, CAC, and BAD.

Note: As can be seen, the Boxing method is a chosen-plaintext attack type.

Knowledge of the Military Enigma and Espionage

We all know that the documents collected by the spy Hans-Thilo Schmidt played a major role in Rejewski's reconstruction of the rotor wiring of the Military Enigma.

However, it is less well known that Asche (codename of Schmidt) had, on his own, encrypted a short text (the keyboard letters) without any steckers. He specified the plaintext, the ciphertext, and the complete key (Walzenlage, Ringstelling, and Grundstellung). In short, he could have collected the data necessary to apply the Boxing method... if he had been asked!

When the English, French, and Polish cryptanalysts met for the first time in Paris in 1939, they realized that their main problem was their lack of knowledge of the rotor wiring of the Military Enigma. This knowledge was an essential prerequisite for deciphering the messages. In fact, the Poles were aware of these wirings but hidding this from their colleagues.

At the end of this meeting, it was decided to ask Asche to find the wiring of the rotors (and the Qwertzu) using cables and a flashlight. If the Boxing method had been invented earlier (rather than in 1940), it would undoubtedly have been proposed instead of a physical inspection of the machine. In fact, by 1939, Asche no longer had access to Enigma documents and to an Enigma machine, and therefore the request (from the British) was not forwarded to him.

Using the Buttoning-up method with alphabets

The Buttoning-up method can be used instead of the Boxing method to find the wiring of two rotors (the middle one and the right one). The Buttoning-up method uses in-depth messages, but several alphabets (e.g., AAA, AAB, AAC, AAD) actually correspond to in-depth messages.

Create the test case with Sympy

To create the alphabets shown in the examples and in the Saga section, I used the following equations in Python with the Sympy library.

>>>
>>> P = Permutation([[0,1,2,3,4,5]])
>>> U = Permutation([2,5,0,4,3,1])
>>> N = Permutation([0,1,4,3,5,2])
>>> M = Permutation([5,1,2,3,0,4])
>>> def rot(j,i):
...     left = ((P**i)*N*(P**-i))*((P**j)*M*(P**-j))
...     right = ((P**j)*~M*(P**-j))*((P**i)*~N*(P**-i))
...     return left * U * right
...
>>> rot(0,0)
Permutation(0, 1)(2, 5)(3, 4)
>>> rot(0,1)
Permutation(0, 4)(1, 5)(2, 3)
>>> rot(1,0)
Permutation(0, 5)(1, 3)(2, 4)
>>> rot(1,1)
Permutation(0, 2)(1, 4)(3, 5)
>>> rot(2,0)
Permutation(0, 3)(1, 4)(2, 5)
>>> rot(2,1)
Permutation(0, 1)(2, 3)(4, 5)
>>>

The complete Turing's Box method

The Boxing method allows us to find the wiring of the fast rotor, as demonstrated. In fact, it allows us to find all the different wirings of an Enigma: the wiring of the three rotors, the ETW (Qwertzu), and the reflector. We refer the reader directly to Turing's treatise study these points.

Challenge

I have created several challenges concerning the Enigma. Most of these challenges can be solved using the methods developed by the allies before and during the Second World War.

My challenge number 22 is precisely designed to be solved using the Boxing method.

Acknowledgements

I would like to thank Manuel Vázquez & Paz Jiménez–Seral for enlightening me on several crucial elements of the Boxing method described by Alan Turing.

I would also like to thank John Wright, who helped me a lot.

Note: These people (Manuel, Paz, and John) brilliantly succeeded in solving challenge 22, which illustrates the Boxing method.

References

Books & Articles

• Enigma, the XYZ period (1939–1940), by Jean-François Bouchaudy (2021), Cryptologia.
  This article describes in particular the meeting in January 1939, which brought together French, British and Polish cryptologists responsible for the study of the Enigma.

Internet links

• The Enigma Collection, Editor: Frode Weierud.
  Turing’s Treatise on Enigma (The Prof’s Book), Chapter 3 (link).