Effectiveness of the diagonal board

Cryptologia, Jul 1999 by Davies, Donald W

ABSTRACT: The bombe was an electromechanical machine devised by Alan Turing and Gordon Welchman for breaking the German Enigma cipher in World War II. Welchman's contribution was the `diagonal board' and it was vital to its success. The device reduced the number of times that the bombe stopped for an apparent solution which was not valid. The ratio by which the false stops were reduced is calculated in this paper. The work showed that there remained a class of false stops which had not been eliminated and further investigation showed that an attachment called the `machine gun' helped to reduce the time lost for this reason. While this work was in progress, numerical results derived by Turing became available, but he did not give the theory and these are consistent (apart from apparent numerical errors) with our results.

KEYWORDS: Enigma machine, Bletchley Park, Gordon Welchman, Bombe, diagonal board, cryptanalysis.

FUNCTION OF THE DIAGONAL BOARD

The bombe was a cryptanalytic search machine used at Bletchley Park to decrypt enciphered messages from the Enigma cipher machine by searching through the 26^sup 3^ initial rotor positions, using a short piece of known plaintext with its associated ciphertext, called a 'crib'. Some knowledge about the bombe and the 'menus' will be assumed. A companion paper provides this background.[1] When the conditions specified by the menu were met, the bombe stopped its search with a proposed solution, but false stops were common.

The diagonal board was an attachment to the bombe which reduced the number of false stops by imposing an extra condition. The stecker board (plugboard) of the Enigma and its cables ensured that if any letter X is transformed to letter Y then letter Y was transformed to letter X. This can be called the involution condition and departure from it prevents a stop when the diagonal board is in operation. The stecker board connects, through a permutation, two parts of the Enigma machine. On one side are the keyboard and display of the Enigma, showing the letters known to the operators. On the other side is the scrambler which comprises three rotors and the reflector or umkehrwalzer. To understand the bombe's construction these two sides of the stecker board must be distinguished, since the bombe itself does not assume an involution.

In this paper, I shall estimate how much the diagonal board improved the operation of the bombe by reducing the number of false stops. The numerical results which are derived in this paper (Table 2) were of great importance when the bombe and its diagonal board were being developed at Bletchley Park at the start of WWII. Alan Turing obtained similar figures and included them in a paper which has now been released (2). The factor which I call V was known then as the H-M factor. Frode Weierud suggest this might mean "Hit-Miss".

The standard, 3-rotor Enigma is assumed and a menu with a single web i. e. derived from a connected graph.

The menu uses a set of letters taken from the crib (both plain and cipher). N will denote the number of letters in the menu. In the bombe, each letter of the menu is represented by a cable containing 26 wires, one for each letter of the alphabet. Thus there are N cables, but in physical form one of these may comprise several cables joined together.

At each step in the bombe's searching process the bombe's mechanism connects these wires in a complex manner and the connections change at each step of the search. For most of the time, these connections result in all 26 wires being connected together in each cable. The search stops at a possible solution when a specific pattern of connections is observed by the machine, namely that one of the wires in each cable is isolated from the rest. We shall call this the `solution-wire' and it is connected though all the cables so the test for this condition can be made in any of them. The solution wire is present N times, once in each cable. Nearly always, all the wires except the solution wire are connected together. It is possible to have more than one possible solution at a stop, e. g. two solution wires, but this is very rare and will be ignored.

The logical significance of cable A having solution wire B is that, in this proposed solution, letter A at the keyboard and lamps of the Enigma machine is plugged via the `stecker board' to letter B of the scrambler. By tracing the solution wire through all the cables, the plugging of all the menu letters can be found. Note that on the scrambler side of the stecker board there may be menu letters and/or non-menu letters.

The diagonal board makes additional connections is the following manner: It is joined by a 26 wire cable to each of the menu cables. For each letter pair (X,Y) where X and Y are different, wire X of cable Y is connected by the diagonal board to wire Y of cable X. There.are 26(26 -1)/2 potential connections in the diagonal board, but only N(N -1)/2 of them are functional when a menu of N letters is joined to it by N cables.