The first methods: The F Catalog

Enigma Home Page

The first methods

Introduction

In late 1932, Rejewski reconstructed the Enigma machine. During 1933, Polish cryptanalysts were able to read Enigma messages by reconstructing the daily key.

This page is dedicated to the study of the "F-catalog," which is used to identify the slow rotors—specifically, the left and middle rotors. Using the F-catalog requires having first determined the plugboard settings (Steckers) via the Grill method.

Enigma Encryption Equations

Equations A and F

The chapter describing the Grill method outlined the equation specifying the substitutions associated with the indicator. There are six "A" equations (labeled 0 through 5).

Six "F" equations (0 through 5) were also calculated; these are derived from the A equations but exclude the rotation of the right-hand rotor (the fast rotor). If no plugboard settings are used, and the middle rotor remains stationary, and the position of the right-hand rotor is known, then all six F equations become identical.

Equations formulas

If they are no steckers:

\( A_0 = P^x C P^{-x} U P^x C^{-1} P^{-x} \)
\( A_1 = P^{(x+1)} C P^{-(x+1)} U P^{(x+1)} C^{-1} P^{-(x+1)} \)
...
\( F_0 = P^y C^{-1} P^{-y} (A_0) P^y C P^{-y} \)
\( F_1 = P^{(y+1)} C^{-1} P^{-(y+1)} (A_1) P^{(y+1)} C P^{-(y+1)} \)
...
\( F_0 = P^y C^{-1} P^{-y} P^x C P^{-x} U P^x C^{-1} P^{-x} P^y C P^{-y} \)
\( F_1 = P^{(y+1)} C^{-1} P^{-(y+1)} P^{(x+1)} C P^{-(x+1)} U P^{(x+1)} C^{-1} P^{-(x+1)} P^{(y+1)} C P^{-(y+1)} \)
...
y = 0 to 25 and when y == x, then (we have found the true position of the right rotor):

\( F_0 = U \)
\( F_1 = U \)
...
\( F_0 = F_1 = ... = F_5 = U \)

  • P : Permutation of the rotation (x: position of the right rotor)
  • C : Permutation of the right Rotor
  • U : Permutation of other rotors (middle, left and reflector)

Equation U

\( U = ( P^{j} \cdot MR \cdot P^{-j} ) \cdot ( P^{i} \cdot LR \cdot P^{-i} ) \cdot UKW \cdot ( P^{i} \cdot LR^{-1} \cdot P^{-i} ) \cdot ( P^{j} \cdot MR^{-1} \cdot P^{-j} ) \)
  • LR, i : The Left Rotor, its position
  • MR, j : The Middle Rotor, its position
  • UKW: The Reflector

Creating the catalog

The catalog will typically be a file containing the U-substitution and the corresponding left and middle rotors.

To create it, we explore all combinations of the left and middle rotors (6 combinations): I-II, I-III, II-I, II-III, III-I, III-II. For each rotor order, we calculate U for every position of the left and middle rotors. Thus, in total, we obtain U for 6 × 26 × 26 = 4,056 combinations.

I created a program to generate this catalog (it uses SymPy): 

$ python catalog-F.py
Syntaxe: catalog-F.py UKW
     UKW == A or B

$ python catalog-F.py B > catalog-F_B.txt
Here is an excerpt from the catalog (all configurations containing the pairs (am) and (by)): 
$ grep am catalog-F_B.txt | grep by
[[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]  -- 12*:RP-
[[am][by][cf][dl][eo][gk][hr][iv][jt][nu][ps][qw][xz]]  -- 21*:AU-
[[am][by][ck][de][fl][gp][hj][iv][nq][ou][rw][sx][tz]]  -- 23*:BK-
[[am][by][ci][dj][ew][fp][gn][hs][kx][lq][ov][ru][tz]]  -- 23*:CU-
[[am][by][cn][ds][et][fx][gp][hz][ij][kq][lw][or][uv]]  -- 31*:NK-
[[am][by][cs][df][en][gz][hl][it][jo][kv][px][qr][uw]]  -- 31*:QJ-
[[am][by][ck][ds][ej][fl][gn][hu][iz][ox][pt][qv][rw]]  -- 31*:ZE-
[[am][by][cz][ds][eg][fj][ht][iu][kl][nx][ov][pw][qr]]  -- 32*:NZ-
Notes:
  • Each line of the catalog contains the U-substitution, the left and middle rotors, and the rotor positions (excluding the right rotor).
  • To perform searches quickly, the catalog must be sorted—for example, based on the pairs (a.)(b.)(c.)...

Using the Catalog

At the end of the Grill procedure, the daily plugboard settings, the position of the right rotor, and the U-substitution value have been obtained—for example: 

==== Rotation x =  6
6 0 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]
6 1 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]
6 2 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]
6 3 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]
6 4 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]
6 5 == [[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]

Next, we look up this substitution in the catalog:
The Grill method provided us with the pairs (am), (by), (ce), and (dh). We look for these pairs in the UKW B catalog. We see that the resulting substitution is correct, as the other pairs are also obtained. We obtain the rest of the Walzenlage: rotors 1 and 2 (I-II), as well as the Grundstellung (RP-) for the left and middle rotors, but with a Ringstellung of AA- (instead of ZZ-). 

$ grep am catalog-F_B.txt | grep by | grep ce | grep dh
[[am][by][ce][dh][fz][gs][ir][jx][ku][lq][nw][op][tv]]  -- 12*:RP-

References

  • Rejewski's report from the French secret service archives (in French). SHD (Service des archives de l’armée française à Vincenes) – DE 2016 ZB 25/6. 1949. Fond Bertrand – dossiers 280 à 285. The German version, file 281, and the French version, file 282.
    This report describes the Polish methods, particularly the first methods for finding the daily keys.