 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
| This article is the part of the series on the Enigma cipher machine. |
| Enigma machine |
| Cryptanalysis of the Enigma |
| Ultra |
In the history of cryptography, the Enigma was a portable cipher machine used to encrypt and decrypt secret messages. More precisely, Enigma was a family of related electro-mechanical rotor machines — there are a variety of different models.
The Enigma was used commercially from the early 1920s on, and was also adopted by the military and governmental services of a number of nations — most famously, by Nazi Germany before and during World War II (WWII). The German military model, the Wehrmacht Enigma, is the version most commonly discussed. Allied codebreakers were, in many cases, able to decrypt messages protected by the machine (see cryptanalysis of the Enigma). The intelligence gained through this source — codenamed ULTRA — was a significant aid to the Allied war effort. Some historians have suggested that the end of the European war was hastened by up to a year or more because of the decryption of German ciphers.
Although the Enigma cipher has cryptographic weaknesses, there were, in practice, other significant factors which allowed codebreakers to read messages: captured machines and codebooks, mistakes by operators, and procedural flaws.
Like other rotor machines, the Enigma machine is a combination of mechanical and electrical aspects. The mechanical mechanism consists of a keyboard; a set of rotating disks called rotors arranged adjacently along a spindle; and a stepping mechanism to turn some of the rotors with each key press. The exact mechanism varies, but the most common form is for the right-hand rotor to step once with every key stroke, and occasionally the motion of neighbouring rotors is triggered. The continual movement of the rotors results in a different cryptographic transformation after each key press.
The mechanical parts act in such a way as to form a varying electrical circuit — the actual encipherment of a letter is performed electrically. When a key is pressed, the circuit is completed; current flows through the various components and ultimately lights one of many lamps, indicating the output letter. For example, when encrypting a message starting ANX..., the operator would first press the A<tt> key, and the <tt>Z lamp might light; Z would be the first letter of the ciphertext. The operator would then proceed to encipher N in the same fashion, and so on.
Current flows from a battery through the switch controlled by the depressed key into a fixed entry wheel. This leads into the rotor assembly, where the complex internal wiring of each rotor results in the current passing from one rotor to the next along a convoluted path. After passing through all the rotors, current enters the reflector, which relays the signal back out again through the rotors and the entry wheel — this time via a different path — and, finally, to one of the lamps. In addition, some machines are equipped with a plugboard, which allow the connections between the keyboard and the entry wheel to be easily rewired by an operator. The earliest Enigma models lack a reflector.
The rotors (alternatively wheels or drums — Walzen in German) form the heart of an Enigma machine. Approximately 10 cm in diameter, each rotor is a disks made of hard rubber or bakelite, with a series of brass spring-loaded pins on one face positioned in a circle; on the other side are a corresponding number of of electrical contacts in an identical arrangement. The pins and contacts represent the alphabet — typically the 26 letters A–Z (this will be assumed for the rest of the description). When placed side-by-side, the pins of one rotor rest against the contacts of the neighbouring rotor, forming an electrical connection. Inside, a set of 26 wires connects each pin on one side to a contact on the other side in an essentially random fashion, different for every rotor.
By itself, a rotor performs only a very simple type of encryption — a simple
|
|}
When placed in the machine, a rotor can be set to one of 26 positions. It can be turned by hand using a grooved finger-wheel which protrudes from the internal cover when closed, as shown in Figure 2. So that the operator knows the position, each rotor has an alphabet tyre (or letter ring) attached around the outside of the disk, with 26 letters or numbers; one of these can be seen through a window, indicating the position of the rotor to the operator. In early Enigma models, the alphabet ring is fixed; a complication introduced in later versions is the facility to adjust the the alphabet ring relative to the core wiring. The position of the ring is known as the Ringstellung ("ring settings").
FThe rotors each contain a notch (sometimes multiple notches), used to control the stepping of the rotors. This was usually located on the alphabet ring.
The Wehrmacht Enigma was equipped with a number of rotors. For the Army and Air Force versions, three rotors were chosen from a set of five; these were marked with Roman numerals to distinguish them: I, II, III, IV and V, all with single notches. The Naval Enigma also had these rotors, but the Navy added three more — VI, VII and VIII — exclusively for their own use.
To avoid merely implementing a simple substitution cipher, some rotors turn with consecutive presses of a key. This ensures that the cryptographic transformation is different at each position, producing a formidable polyalphabetic substitution cipher.
The most common arrangement utilises a ratchet and pawl mechanism. Each rotor is affixed with a ratchet with 26 teeth; a group of pawls engage the teeth of the ratchet. The pawls are pushed forward in unison with each keypress on the machine. If a pawl engages the teeth of a ratchet, that rotor advances by one step.
Each rotor is also affixed with a notched ring, typically containing a single notch, but occasionally several notches. At a certain point, a rotor's notch will align with the pawl, allowing it to engage the ratchet of the next rotor with the subsequent key press. When a pawl is not aligned with the notch, it will simply slide over the surface of the ring without engaging the ratchet. In a single-notch rotor system, the second rotor is advanced one position for every 26 advances of the first rotor. Similarly, the third rotor is advanced one position for every 26 advances of the second rotor. The second rotor also advances at the same time as the third rotor, meaning the second rotor can step twice on subsequent key presses — "double stepping" — resulting in a reduced period (Hamer, 1997).
With three wheels and only single notches in the first and second wheels, the machine has a period of 26 × 25 × 26 = 16,900. Historically, messages were limited to a couple of hundred letters, and so there was no risk of repeating any position.
When pressing a key, the rotors step before the electrical circuit is connected.
The entry wheel (Eintrittwalze in German), or entry stator, connects the plugboard, if present, or otherwise the keyboard and lampboard to the rotor assembly. While the exact wiring used is of comparatively little importance to the security, it caused a brief hiccup in the progress of Polish cryptanalyst Marian Rejewski during his deduction of the rotor wirings. The commercial Enigma connects the keys in the order of their sequence on the keyboard: Q<math>\rightarrow<math>A, W<math>\rightarrow<math>B, E<math>\rightarrow<math>C and so on. However, the military Enigma connects them in straight alphabetical order: A<math>\rightarrow<math>A, B<math>\rightarrow<math>B, C<math>\rightarrow<math>C etc. It took an inspired piece of guesswork for Rejewski to realise the modification, and he was then able to solve the equations.
With the exception of the early models A and B, the last rotor is followed by a reflector (German Umkehrwalze), a patented feature unique to the Enigma family amongst the various rotor machines designed in the period. The reflector wires outputs of the last rotor up in pairs, redirecting current back through the rotors by a different route than that by which they had entered. The reflector ensures that Enigma is self-reciprocal: encryption is the same as decryption.
In the commercial Enigma model C, the reflector can be inserted in one of two different positions. In Model D the reflector can be set in 26 possible positions, although it does not move during encipherment. In the Abwehr Enigma, the reflector is turned in a similar way to the other wheels.
In the Wehrmacht Enigma, the reflector is fixed and does not rotate, and appeared in four versions. The original version was marked A, and was replaced by Umkehrwalze B on 1 November 1937. A third version, Umkehrwalze C appeared in 1941. The fourth version, first observed on 2 January 1944 is a rewireable reflector, called Umkehrwalze D, allowing the Enigma operator to alter the connections as part of the key settings.
The plugboard mechanism (Steckerbrett in German) is visible on the front panel of Figure 1 and some of the patch cords can be seen in the lid. It was introduced on German Army versions in 1930 and was adopted by the Navy as well. The plugboard contributes a great deal to the security. Enigma without a plugboard — "unsteckered" Enigma — can be solved by certain hand methods; these methods are, generally, much more difficult to mount on an Enigma with a plugboard, and codebreakers resorted to special machines, primarily the bombe.
The Enigma transformation for each letter can be specified mathematically as a product of permutations. Assuming a three rotor German Army/Air Force Enigma, let <math>P<math> denote the plugboard transformation, <math>U<math> denote the reflector, and <math>L, M, R<math> denote the actions of the left, middle and right rotors respectively. Then the encryption <math>E<math> can be expressed as
After each key press the rotors turn, changing the transformation. For example, if the right hand rotor <math>R<math> is rotated <math>i<math> positions, the transformation becomes <math>\rho^iR\rho^{-i}<math>, where <math>\rho<math> is the cyclic permutation mapping A to B, B to C, and so forth. Similarly, the middle and left-hand rotors can be represented as <math>j<math> and <math>k<math> rotations of <math>M<math> and <math>L<math>. The encryption function then becomes:
In German military usage, communications were divided up into a number of different networks, all using different settings for their Enigma machines. These communication nets were termed keys at Bletchley Park, and were assigned codenames, such as Red, Chaffinch and Shark. Each unit operating on a network was assigned a settings list specifying the Enigma for a period of time. For a message to be correctly encrypted and decrypted, both sender and receiver have to set up their Enigma in the same way; the rotor selection and order, the starting position and the plugboard connections need to be identical; these settings have to be agreed on beforehand, and were distributed in codebooks.
An Enigma machine's initial state, the cryptographic key, has several aspects:
Enigma was designed to be secure even if the rotor wiring was known to an eavesdropper, although in practice the wiring was kept secret.
One refinement is necessary; if a number of messages are sent encrypted with identical or near-identical settings, a cryptanalyst has several messages "in depth", and might be able to attack the messages using frequency analysis. To combat this, a different starting position for the rotors is chosen with each message; a similar concept to an initialisation vector in modern cryptography. The starting position is transmitted along with the ciphertext, and the exact method used is termed the "indicator procedure" — weak indicator procedures allowed the initial breaks into Enigma.
Enigma operators were at first given a new booklet every month that contained the initial settings to be used with the machines. For instance, on a particular day the settings might be rotor number 3 in slot 1, number 1 in slot 2, and number 2 in slot 3. The rotors were then spun, so the slot 1 rotor showed letter X, slot 2 letter J, and slot 3 letter A. Since the rotors could be moved around in the machine, with three rotors in three slots there were another six (3 x 2 x 1) combinations to consider, for a total of 105,456 possible alphabets. There was also a 'ring' setting for each rotor which added still more variation and that setting for each rotor was included in the keys specified in the booklets.
At this point, the operator was instructed to independently select (without a pattern -- which many operators found difficult) additional settings for the rotors; this time only for the positions, or "spins" of the rotors. A particular operator might select EIN, and these became the message settings for that encryption session. The operator then typed their message settings into the machine, which was still set up in the initial settings. To be on the safe side, they typed it twice. The results would be encrypted, so the EIN typed twice might turn into XHTLOA. The operator would then spin the rotors to his message settings, EIN in this example. The rest of the message was then typed in, and the ciphertext sent (typically by radio or telegraph).
At the receiving end the operation was reversed. The operator set the machine to the initial settings and typed in the first six letters of the message. In this example, EINEIN would be produced. By moving his rotors to EIN, the receiving operator would simply type in the rest of the ciphertext, deciphering the message.
Although many messages would be sent in any one day with six letters from the initial settings, those letters were intended to be random. Any attack on the cipher would have to cope with the fact that the base cypher key (most of the settings) changed frequently, and furthermore that every message had its own variant of that base key. With modern computers it would likely have been possible to 'crack the code' (or more correctly to break the cypher) without too much trouble, but with only pencil and paper it was nearly unthinkable.
Enigma was believed to be secure since even possession of a machine (including rotors) would be of little help without knowledge of the current key. This was a compelling security analysis, and the Germans relied on it. Enigma-encrypted German traffic included everything from high-level messages about tactics and plans, to weather reports, and even to trivialities such as birthday congratulations.
In 1918, engineer Arthur Scherbius applied for a patent for a cipher machine using rotors, and with E. Richard Ritter, founded the firm of Scherbius & Ritter. They approached the German Navy and Foreign Office with their design, but neither were interested. They then assigned the patent rights to Gewerkshaft Securitas, who founded the Chiffriermaschinen Aktien-Gesellschaft (Cipher Machines Stock Corporation) on 9 July 1923; Scherbius and Ritter were on the board of directors.
Chiffriermaschinen AG began advertising a rotor machine — Enigma model A — which was exhibited at the Congress of the International Postal Union in 1923 and 1924. The machine was heavy and bulky, incorporating a typewriter. It measured 65×45×35 cm and weighed about 50kg. A Willi Korn — was first introduced in the Enigma C (1926) model. The reflector is a key feature of the Enigma machines. Hamer et al write, "[Enigma] was a relatively large family of machines built around the same principle, wired wheels (rotors) with a fixed or rotatable Umkehrwalze (reflector)".
Model C was smaller and more portable than its predecessors. It lacked a typewriter, relying instead on the operator reading the lamps; hence the alternative name of "glowlamp Enigma" to distinguish from models A and B. The Enigma C quickly became extinct, giving way to the Enigma D (1927). This version was widely used, with copies going to Sweden, the Netherlands, England, Japan, Italy, Spain, USA and Poland.
Several copies of commercial Enigmas were purchased by the German Navy, leading to adoption of an adapted machine by the Navy in 1926, termed the Funkschlüssel C (Radio cipher C); the machine was revised slightly in 1933.
On 15 July 1928, the German Army (Reichswehr) introduced their own version of the Enigma — the Enigma G, revised to the Enigma I in June 1930. There was also a typewriter version, the Enigma II. The most important change was the addition of a plugboard; a variable wiring that could be reconfigured by the operator. The plugboard significantly increased the security of the machine. This version became known as the Wehrmacht, or Services Enigma, and was used extensively by the German military services and other government organisations, both prior to and during World War II. The machine's dimensions were 28×34×15 cm (weighing around 12 kg).
By 1930, the Army suggested that the Navy adopt their machine, giving the reasons of increased security (with the plugboard) and easier interservice communication. The Navy eventually agreed and in August 1934 brought into service the Navy version of the Army Enigma, designated Funkschlüssel M or M3. While the Army version used only three rotors, the Navy specified a choice of three from a possible five. In 1939 the Army went to a 3 rotors out of 5 system and changed their indicator procedures, leaving the Poles with too much work to keep up. This was one of the reasons for passing information and equipment on to British and French in July of that year. Still later, the Navy went to 3 rotors out of a possible 8. In August 1935 the Air Force also introduced the Wehrmacht Enigma for their communications. A four rotor Enigma was introduced by the Navy for U-boat traffic on 1 February 1942, called M4 (the network was known as Triton, or Shark to the Allies). The extra rotor was fitted in the same space by splitting the reflector into a combination of a thin reflector and a thin fourth rotor.
The Abwehr used a notable variant of the Enigma, known as the Abwehr Enigma, counter machine or the Zahlwerk Enigma, a four-wheel unsteckered machine with multiple notches on the rotors.
Other countries also used Enigma machines. The Italian Navy adopted the commercial Enigma as "Navy Cipher D"; the Spanish also used commercial Enigma during their Civil War. British codebreakers succeeded in breaking these machines, which lacked a plugboard. The Swiss used a version of Enigma called model K or Swiss K, for military and diplomatic use, which was very similar to the commercial Enigma D. The machine was broken by a number of parties, including Germany, France, Britain and the United States (the latter codenamed it INDIGO). An Enigma T model (codenamed Tirpitz) was manufactured for use by the Japanese.
It has been estimated that 100,000 Enigma machines were constructed, and after the end of the Second World War, the Allies sold captured Enigma machines, still widely considered secure, to a number of developing countries.
A number of other rotor machines were similar to the Enigma machine. For example, the British Typex machine, the US SIGABA and the Swiss NEMA machine.
From a purely cryptographic viewpoint, the importance of the Enigma was that it was broken, and that the break broke fundamentally new ground in cryptanalysis. From the perspective of WWII, Enigma's vulnerability was extremely important since it gave information which, in volume and detail, has rarely if ever been available about opposition tactical / strategic / logistical intentions. This significantly affected the course of the War. Information gained from cryptanalysis of German communications, primarily those encrypted with Enigma, was called Ultra. Much of the work which produced Ultra information was done at Bletchley Park in England. Enigma messages became available too late to have much effect on the Battle of Britain, but they had significant impact on the war thereafter — some have suggested that breaking Enigma shortened the war by at least a year. However, use of Ultra was hampered by the Allied highest level instance insistence that no exploitation of the information expose its source — often, a story would be made up to explain Allied actions. The Germans harboured occasional suspicions that their communications had been compromised (eg, that Enigma had been broken) and looked into the problem several times. Reviews of Enigma's security were undertaken, but the analyses found nothing definitive, and the machine continued in wide use, however even these reviews resulted in some strengthening of the system, and periods of difficulty for the cryptanalysts in Bletchley.
Naval Enigma decryptions made a difference in the Battle of the Atlantic. A break of some Italian Enigma messages led to the defeat of the Italian Navy at Capa Matapan. Ultra information was of considerable assistance to the British at El Alamein in Western Egypt. A decrypted Enigma message was involved in the hunt for the battleship Bismarck, betraying its intention to head for the coast of France after rudder damage. Intelligence from signals between Adolf Hitler and General Günther von Kluge was of considerable help during the campaign in France just after the Allied landings on D-Day. Ultra information was also misused or ignored at times, as for instance, at the Battle of the Kasserine Pass in North Africa and in warnings about the Battle of the Bulge attack.
A number of Enigma machines are on public display in museums. The Deutsches Museum in Munich has both the three and four-wheel German military variants, as well as several older civilian versions. There are also examples in the NSA's National Cryptologic Museum at Fort Meade in the United States, at Bletchley Park in the United Kingdom, as well as a number of other locations in Germany, the US, the UK, and a few other countries in Europe. A number are also in private hands.
An interactive fiction game Jigsaw by Graham Nelson contains a puzzle in which the player must decrypt a message with a simplified version of Enigma. The puzzle is generally accepted as the most annoying one in the game, which is perhaps some measure of how hard it was to decrypt messages produced by the original machine(s).
World War II Era Encryption Devices
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
