Gresham Professor of Geometry



Download 115.46 Kb.
Page1/6
Date conversion15.05.2016
Size115.46 Kb.
  1   2   3   4   5   6

The reduced Enigma


Harold Thimbleby*

Gresham Professor of Geometry


Gresham College

Barnard’s Inn Hall

Holborn
LONDON, EC1N 2HH

Abstract


This article describes a simplified cryptographic machine, based closely on the World War II Enigma. This ‘reduced Enigma’ exposes some of the design flaws of the original Enigma in a new way. Had the Axis powers built a reduced Enigma, the outcome of the war might have been different.

A fully working reduced Enigma has been used very successfully in numerous public lectures, in school talks, and in university seminars. Hands-on demonstrations of the reduced Enigma dramatically brings alive ideas about design, codes, permutations and groups. As a working trapdoor function, the reduced Enigma also provides an unusually clear introduction to public key cryptography. This article provides background information, lecture suggestions, and details for building it.


Keywords


Education, Enigma, Public Understanding of Cryptography, “reduced Enigma”

Introduction


Cryptography is a fascinating subject. The paradoxical concept of “sharing secrets” has a natural appeal, and can be used as a motivation to discuss history, mathematics and computer science, or to help motivate many concepts such as key distribution, public key cryptography and digital signatures. This paper describes a simple cryptographic machine, closely based on the World War II Enigma: the machine has been used very successfully in lectures, both to public and school audiences, and to researchers. Design details for a simplified Engima are given, as well as relevant historical and technical context, particularly as highlighted through the simplified design. This paper, then, should be of equal interest to readers interested in cryptography and to lecturers who wish to communicate the ideas clearly, particularly with hands-on participation.

Any good lecture provides ideas that at different points draw the attention of different members of the audience. The Enigma provides an endless source of historical interest, mathematical interest, human factors interest, and so on. It is highly suitable for mixed audiences, typified by grandparents bringing along enthusiastic grandchildren! Likewise, but due to limitations of space rather than time, this paper, too, raises tantalising issues (e.g., Where do some of the numbers come from? What about different versions of the Enigma? What did people, on both sides, learn as the war progressed?) and numerous fascinating potential discursions (e.g., What did Alan Turing contribute? How do we do things better today? What about public keys?) that will stimulate the reader — or an audience — into unlimited further activity and reflection. Elsewhere we have discussed how to introduce the underlying cryptographic concepts to audiences of any age or skill, from school children to postgraduate specialists: see Bell et al., 2002.

However, the main point for the present that is conveyed, and that should be conveyed forcibly to all programmers and system developers, is that complex systems — particularly ones involving any interaction or human element — are hard to design to be effective and reliable under the pressures of real use, and one should first build simplified systems to fully understand the principles. In an hour’s typical lecture, the reduced Enigma can illustrate dramatic weaknesses in the real Enigma.

Mechanical devices are ideal for lectures. Unlike computer programs, you can see how they work, and using them allows participants to attempt more interesting activities than can be done purely manually. With cryptography, we have the added advantage that for an exciting and important period of history, the real devices in life-and-death use were mechanical too. Alfred Scherbius was one of many people in the early twentieth century to patent the basic idea of a mechanical or electromechanical code machine based on rotors. There were many designs and developments, but the most widely-known of these devices was the Enigma. The Enigma was used extensively by the Germans during the Second World War.

Original WWII Enigmas are now valuable antiques, and rebuilding an accurate Enigma is a complex job and one that anyway creates a code that is hard to explain in lectures. Yet in principle, an Enigma is ideal for explaining important concepts, such as key distribution problems, since it is easy enough to change keys and, of course, codes using any key work automatically.

What, then, is the simplest Enigma that can be made?





Figure 1. A German army Enigma in use. Here, pressing S lights up N. The three rotors are just visible under the cover at the top; the plug board is partly covered at the bottom.1



Figure 2. Close up of the three rotors. A row of lamps and some of the internal wiring is visible, as well as the switch connections. The rotors of this Army Enigma are set numerically, rather than by using letters. This would help ensure that settings were chosen randomly.



Figure 3. Close up of the Enigma plugboard, showing 9 connections. Note that the plugs and sockets are symmetric and can be inserted incorrectly.

What is the simplest Enigma?


Scherbius’s Enigma had a 26 button keyboard (with no space button) and 26 corresponding light bulbs. Briefly, a plugboard and a set of rotors mess up the wiring, so that as buttons are pressed one of the 26 light bulbs come on in turn, but not in any obvious order. The plugboard settings and initial rotor settings represent the key, and another Enigma with the same settings (and internal construction) can decode the message. There were lots of versions of Enigmas; for example the pre-war commercial ones did not have a plugboard. During the war, the Enigma and the procedures for using were under continual development; although the Germans were aware of some of the weaknesses we shall describe, no Enigma consolidated the best features of the different versions into a single machine. Rather than consider all the complications and variations, what is the simplest Engima style machine that works?

One might think that the simplest Enigma would have two buttons, labelled in binary as 0 and 1. Its two light bulbs would also be labelled 0 and 1. When an operator types out a binary message, say, 01011001… the lights would perhaps code it as 11001010… This is clearly the simplest scheme inspired by the Enigma. Unfortunately, because of their design, an Engima with only two buttons would have a disastrous property: 0 would always code as 1, and 1 always code as 0 — hardly a code. The problem arises due to the Enigma’s wiring, but is usually explained more simply: no letter can code as itself. This property of the real Enigma was one of its main weaknesses. Had Scherbius made a reduced Enigma first, he would certainly have spotted the problem. Instead he went for 26 letters straight away,2 and hence disguised the flaw in a layer of complexity. He and other developers fell for the classic trap of making a complication illusoire. Just making codes more complex rarely makes them harder to solve.

We will see below that this problem of the Enigma design is not the only one that a reduced Enigma exposes.

Figure 4 shows an Enigma circuit taken from a German navy manual. It is easiest to follow the wiring from the battery connection + on the right of the diagram. Suppose the Y button is pressed. Current is connected (along the solid wire at the far left) up to the rotors. The three rotors make a ‘random’ connection through to the reflector, and then back, where the circuit continues in the dashed wire (emerging from the rotors at the top right). The return wire connects (in this case) to the Z button’s switch, where it is connected through to the Z lamp. All lamps have a common return to the (negative) battery connection. So for these rotor positions, if Y is pressed Z lights; and if Z is pressed Y lights.



Figure 4. Part of the Enigma circuit, from a German navy manual (from Kahn, 1996b). The diagram shows three rotors at the top, with a reflector on the far left and a contact wheel on the right. In the middle, connected to the – battery terminal, are two (of the 26) lights; at the bottom (connected to the + battery terminal) are two of the key switches.

In actual operation, when a button is pressed the rotors turn, and the particular connection of YZ and ZY might not be repeated for a very long time. Of course if Y and Z are the only buttons, whatever the rotors do in detail, ultimately they cannot connect them any other way than together: which, as we’ve seen is degenerate. The German navy manual shows a worthless Enigma!

In general the Enigma wiring ensures that no letter can code as itself. The button Y (for example) either connects to the + battery terminal or to the Y lamp. If the Y button is pressed, the Y lamp cannot come on. The same is true for all 26 letters.

This, the Engima’s major weakness that no letter can code as itself, facilitates code breaking. If a crib (a suspected word in the plaintext) is slid along a ciphertext, if no letters correspond anywhere, then the crib is a possible decrypt at that point. A good crib might be HEILXHITLER, not least because it was said often, but because it has a pattern of several Hs and Es and Is.

Exploiting this weakness, the British cryptanalysts at Bletchley Park, developing original Polish work, built a machine, the Bombe, that automatically looked for possible decodings. A Bombe would typically find several possible Enigma settings that could possibly code a message containing (say) HEILXHITLER, and a room full of Enigma operators would work through the possible settings systematically until the message was successfully decoded. Using a reduced Enigma helps explain this issue to an audience: it is possible to press one button repeatedly and easily see its corresponding lamp never lights up; on a real Enigma, with 26 lamps flashing, it is impractical to see that a particular lamp never lights.

Why does the Enigma have this property? The simple wiring of the Enigma ensures the code is reciprocal: if Y codes as Z, in the same setting, Z codes as Y. An Enigma set up with the rotas in the same position can be used either to code or decode, and this has practical advantages. In fact, the Enigma could have been designed to be reciprocal without this problem (see Appendix 5), but the problem was not noticed.

Since every letter on the Enigma is coded as another letter, it might seem possible to build a reduced Enigma with three buttons and three lights. Suppose the buttons are XYZ. There are then just two possible codes: {XY, YZ, ZX} or {XZ, YX, ZY}. But the Enigma was also designed to be reciprocal, so that with the same key settings it could be used to both code and decode messages. With three keys this is not possible. Suppose X codes as Y, then at the same setting Y should code to Z, not to X. Instead, the Enigma should code so that if X codes as Y, then Y codes as X. This reciprocal relation must be true for any pair of letters, and therefore an Enigma must have an even number of letters. The real Enigma had 26 buttons, and in consequence X was used to double up as a space. (There are reciprocal codes with three letters that do work, but which the Enigma wiring can’t handle: for instance {XY, YX, ZZ} which doesn’t work because ZZ codes one letter onto itself.)

The simplest Enigma must have 4 buttons and 4 lights.


  1   2   3   4   5   6


The database is protected by copyright ©essaydocs.org 2016
send message

    Main page