Was the Enigma cryptanalysis a complete NP problem

The Enigma system structure and cryptanalysis

Transcript

1 DIPLOMA THESIS The Enigma System Structure and Cryptanalysis Carried out at the Institute for Information Systems, E184-3 Department for Knowledge-Based Systems of the Vienna University of Technology under the guidance of Ao.Univ.Prof. Dipl.-Ing. Dr.rer.nat. Uwe Egly through Thomas Mayr Gerlgasse 10 / Vienna Austria Vienna, in October 2003

2 Summary The Enigma and the Enigma System 1 have been extensively researched historically and technically for some time. This thesis provides an overview of the general functionality of the Enigma system and discusses some specific differences between the systems. In addition, we will deal in detail with the methods for cryptanalysis of the Enigma. For graphical illustration I implemented two simulators as part of this work. A simulator simulates the structure and functionality of a number of different Enigma models. With the second simulator, some methods of cryptanalysis that are dealt with in this thesis can be easily reproduced. These simulators were developed for the Typewriter Museum Peter Mitterhofer and are in use there both on the multimedia terminal and on homepage 2. Keywords: Enigma, Enigma models, cryptanalysis, Enigma Simulator 1 The Enigma system refers to the entire communication system consisting of the Enigma machine, the transmission device, the key system and their application instructions. 2

3 Acknowledgments First and foremost, I would like to thank my supervisor, Professor Uwe Egly, for the many technical impulses and suggestions for improvement during the course of my work. My special thanks go to the Peter Mitterhofer Typewriter Museum in Partschins, especially my sister Maria Mayr, for providing numerous documents and articles about the Enigma. At this point I would also like to thank my parents and siblings who made my studies possible in the first place. I would also like to thank my friend Christine Dickert and her family for their human and culinary support. Last but not least, many thanks to all those who have contributed to the success of this work through their professional and personal support.

4 Contents 1 Introduction Overview A brief historical overview The first rotor machines Evolution of the Enigma Fraction of the Enigma Poland () Bletchley Park England () Function and application Rotated alphabets Structure of the machine Rollers Plug board Keypad Lamp field Current flow General settings Key room Key distribution The key book Model variations and related machines Commercial Models of the Enigma Enigma A Enigma B Enigma C Enigma D Military models Enigma I i

5 4.2.2 Enigma II Wehrmacht-Enigma Marine Enigma Reichsbahn-Enigma Abwehr-Enigma Enigma replicas GREEN TYPEX M Other rotor machines C Cryptoanalytical methods La Méthode des Bâtons First Polish successes Help from outside The breakthrough Deciphering the motto keys Determining the roller wiring Determining the rapid rotation The characteristics method Changed encryption rules Zygalski perforated sheets Bomba Weakness of the Polish methods Bletchley Park Modification of the Polish bomba Turing Welchman bomb Marine Enigma M3 and M Overview of all methods Ciphertext-only attacks Gillogly attack The simulator Enigma simulator package enigma.data More packages Operating Instructions Outlook Bomb Simulator Bomb - Implementation Details ii

6 6.2.2 Graphic representation A Glossary 122 iii

7 List of Figures 3.

8 6.11 Current propagation sequence Bomb Wizard Bomb Wizard Bomb Wizard Bomb Wizard v

9 List of Tables 3.1 Vigenère Square vi

10 Chapter 1 Introduction Even before the end of the First World War, the German engineer Arthur Scherbius began developing a cipher machine. This should replace the inadequate manual encryption methods from the First World War. He received his first patent on February 23, 1918 for an encryption machine that used rotors for encryption. Other designers in America, the Netherlands and Sweden also developed the idea of ​​the rotors almost at the same time. The Enigma, the most famous cipher machine of all, emerged from Scherbius' developments. A first commercial model of this machine was first introduced in 1923, and later models were built and used even after World War II. The enormous popularity of the Enigma does not result from its civil use, but from its use in the Second World War. There she was an important element in the warfare of the Germans. Their use and the decryption by the Allies was decisive in Hitler's Blitzkrieg and the submarine war in the Atlantic. Now to the construction of the machine. The Enigma is an electromechanical cipher machine based on rotors 1. It is composed of the following components: a 26-letter keypad; a 26-letter lamp field; an encryption unit consisting of three movable encryption rollers; and in most cases a so-called plug board. 1 Also referred to as rollers in the following. 1

11 The encryption or decryption of a text is very easy. The text to be encrypted or decrypted is entered using the keypad like a typewriter, with an incandescent lamp lighting up each time a key is pressed, which indicates the encrypted character. For each character in the message, the associated encrypted character can be read from the lamp field. The machine also has an involutive character. We want to explain its effect with the help of an example. For example, if the letter A is pressed on the keypad and then the letter L lights up, if the machine starts from the same configuration, the letter A would light up when the letter L is pressed. As a result of this fact, encryption and the associated decryption of a text can be carried out by a machine with the same start-up configuration. Although this has practical advantages (only a start configuration is required for encryption and decryption), it is, as history has shown, a weakness of the encryption system. 1.1 Overview In Chapter 2 we get a brief historical overview. We take a closer look at the development of the first rotor machines, and especially the evolution of the Enigma. In addition, we take the side of the cryptanalysts and look at their success in decrypting the Enigma. Chapter 3 deals with the structure and use of the Enigma. To do this, we first consider the basic properties and the mathematical definition of a rotor machine. This is still needed in the following chapters. Then we turn to the functionality of the Enigma and its internal structure. We also deal with the use of the machine and the associated key system. Chapter 4 provides a brief overview of the model variations of the Enigma. The basic characteristics of the commercial and military models are discussed. In addition, some rotor machines related to the Enigma are considered. Chapter 5 forms the core of this work. The methods for cryptanalysis of the Enigma are presented here. This chapter is divided into three large sections. The first part deals with the methods developed in Poland from 1932 to 1938. The second part deals with the methods that were developed and used in Bletchley Park, the British center for cryptanalysis. At the end of this chapter we consider 2

12 still shows the functionality of a ciphertext-only attack (from 1995), which was carried out with today's computer support. Chapter 6 describes the software simulator of the Enigma and the simulator of the cryptanalytic methods. Both the internal functionality and the operation by the user are described. 3

13 Chapter 2 A brief historical overview 2.1 The first rotor machines The idea of ​​a movable rotor for encryption had, it seems, different people at the same time (see the standard work by David Kahn [Kah79]). According to Kahn, the American Edward Hebern was the first to come up with the idea in 1917, but the patent was not granted until 1924. Second was Arthur Scherbius, who applied for a patent in February 1918. Soon afterwards, two more were added, namely the Dutchman Hugo Koch (patent application on) and the Swede Arvid Damm (patent application on). Different machines resulted from all these ideas and patents. Koch's patents were built by Scherbius' company. Hebern built a machine for the American government. The von Damm company was bought by Boris Hagelin, who also built various machines. Scherbius presented his first model of the Enigma for the first time in 1923 at the international postal congress. 2.2 Evolution of the Enigma The Enigma became one of the most widespread and best-known encryption machines. There were more than four civil models and eight military models or variants in Germany alone. In addition, the civil version (Model D, Model K) was bought by many countries. Some of these countries, such as Switzerland, adapted these machines. In Japan the Enigma D was copied (called Green by the Americans), in 4

14 Poland was the name of a replica of the Enigma Lacida. The Enigma was also used as a model in the USA and England. In the USA it was developed into the M-235 and in England to the Typex. Even after World War II, the machines captured by the Allies were given to developing countries. In Switzerland and Italy, too, new rotor machines were built and used after the war, with the Enigma as a model. More information about the individual models can be found in Chapter 4 Model Variations and Related Machines. 2.3 Breakage of the Enigma For a long time, the Enigma was considered a safe machine. Before World War II, the English and French had little hope of breaking the Enigma system. It seemed that the machine is safe. Too many possibilities to try out all the keys, no obvious weakness that enables a promising attack, this was, as it turned out, too pessimistic an assumption Poland () Poland was surrounded by the countries of Germany and the Soviet Union after the First World War. In Poland they saw themselves as endangered by these two countries, because, according to the Treaty of Versailles, Germany had to cede large parts of its territory to Poland and was willing to regain it. The communist Soviet Union also seemed a threat to Poland. So it was natural for the Poles to collect as much information as possible about their neighbors. A decryption service, the Biuro Szyfróow, was set up as early as the end of the First World War. In the Polish-Soviet war of 1920 this service achieved very good results. As early as 1920, the Poles began to form a cooperation with the French Deuxième Bureau. In 1926 the German Navy began to experiment with a version of the Enigma (radio key C 1 based on the Model C), the army started with a version based on the Model D to send radio messages for training purposes. These radio messages were intercepted by the Poles, among others, and they recognized that the Germans were obviously using a new, unknown encryption method. They suspected that a variant of the commercial Enigma was being used. However, this did not help the cryptanalysts much and so the Polish attempts to decrypt messages were completely unsuccessful until 1931. 5

15 French help Hans-Thilo Schmidt worked in the Reichswehr cipher station. In 1931 he approached the French embassy in Berlin with an offer to sell secret documents. So Schmidt came into contact with the agent Rex, who worked for the French secret service. On November 8, Schmidt (code name Asche) sold two documents to his contact for the first time. These documents were examined by an experienced French cryptanalyst. He explained that the documents were in part interesting, but did not contribute anything to decryption. Subsequently, these documents were also shown to the British, who did not know what to do with them. Only the Poles, who had been exchanging information with the French since 1920, were better informed and able to describe exactly which documents were important. Secret material flowed from Germany via France to the Poles and that by the year The Poles recognized the enormous importance of decrypting encrypted radio traffic. So they tried to recruit new employees. For this purpose, math students 1 were subjected to a special aptitude test. The three best, namely Marian Rejewski, Hendryk Zygalski and Jerzy Różycki, were selected and were given a permanent position in the Polish service from September 1, 1932. First successes First Rejewski was commissioned to deal with the Enigma and the available documents. It didn't take long for Rejewski to report initial successes. He found out the substitution of the entry roller and determined the wiring of some rollers. This enabled the Polish service to continuously read Enigma radio messages from 1933 onwards. Zygalski and Różycki were also familiarized with the new knowledge, and subsequently both developed new methods. Zygalski designed the perforated sheets named after him and Różycki the so-called clockwise method 2. Until 1939, the Poles had not passed on any of their successes to the French. It was only when Hitler canceled the non-aggression pact in April 1939 and the tensions continued to increase over the course of the months that the Poles decided to pass on all the knowledge they had gained about the Enigma to the French and the British. But there was another reason for this change of heart. The Germans increased the number of 1 At this time the classical cryptanalyst was mostly experienced in linguistics 2 We will deal with these methods in more detail in a later chapter 6

16 available reels from three to five. This increased the existing setting options for the Enigma tenfold and thus also the effort required to decrypt the messages. The few resources were no longer sufficient for decryption, they had to cooperate with other countries. France and England each received a replica of the Enigma (with 5 rollers and the reversing roller B), the plans for a bomba and the Zygalski perforated sheets (see later chapters). The success story of the Polish cryptanalysts was almost over. They had to flee to France, where they continued to decipher messages with the help of the perforated sheets. After France surrendered in 1940, they fled to Algeria for a short time, but soon returned to the free part of France. It was only with the occupation of free France that they fled to England via Spain. There they worked for the Polish deciphering center. Bletchley Park and British successes were closed to them. 7th

17 2.3.2 Bletchley Park England () In Bletchley Park, the new center of British deciphering, the information provided by the Poles was very useful. Already towards the end of 1939 Alan Turing designed the concept of the British bomb, which was built in the middle of 1940 and also delivered good results. Any information obtained by deciphering the Enigma had to be used carefully. Because if the Germans had suspected a loophole in the Enigma, they would certainly have improved the system and thus made decryption more difficult. For this reason, all information from Bletchley Park was drawn with the code name ULTRA, whereby this name should represent a real network of agents to the outside world. Again and again there were setbacks, blackouts in the deciphering of German radio messages, which were due to changes on the German side. From 1943 onwards, all problems were solved and the radio messages could be deciphered without any long delay. In the USA, too, after the outbreak of war, the deciphering of Japanese and German messages became increasingly important. The British concluded an extensive cooperation with the Americans and exchanged all information about the Enigma. Over time, the US caught up with its superior resources. With the help of the British, they built their own bombs, which were much faster (20 times) than their British counterparts. For example, they were soon able to decipher all the messages from the Triton radio network from German submarines in the Atlantic on their own. 8th

18 Chapter 3 Functionality and application The Enigma works electromechanically. All important components (keypad, cipher drum, lamp field, connector board) of the machine are connected by a 26-wire (cable) bus. If a button is pressed, voltage is applied to a cable of the bus, the current now flows through the system depending on the current setting of the machine and lights up an incandescent lamp in the lamp field. So that the same lamp does not always light up when a button is pressed repeatedly 1, the internal status of the machine is changed each time one button is pressed by mechanically moving one or more rollers. The encryption of the Enigma is mainly based on the concept of rotated alphabets. 3.1 Rotated Alphabets A rotated alphabet can be defined in the following way (see [Bau00a]). Let {p i Rp i i N} be the set of R-rotated standard alphabets, where R is the rotor.We use the 26-letter alphabet (A-Z) as the alphabet. As an example, we set the permutation of the rotor R to. EKMFLGDQVZNTOWYHXUSPAIBRCJ 1 This would otherwise only represent a simple monoalphabetic substitution. 9

19 The rotor R is now rotated with the help of p, where p represents a cycle of the standard alphabet. The standard alphabet raised to the power in cycle notation: p 0 = (abcdefghijklmnopqrstuvwxyz) p 1 = (bcdefghijklmnopqrstuvwxyza) p 2 = (cdefghijklmnopqrstuvwxyzab) ... pi represents the inverse substitution of the table 3.1 for the rotor in rotated . 1: Rotated alphabet R 10

20 Table 3.1 shows, for example, the element in column m and row i = 14 in the substitution notation in the following way. The substitution p 14 = () abcdefghijklmnopqrstuvwxyz opqrstuvwxyzabcdefghijklmn results from shifting the alphabet by 14 positions to the left. Then we get () abcdefghijklmnopqrstuvwxyz p 14 = mnopqrstuvwxyzabcdefghijkl by shifting the alphabet by 14 positions to the right. With () ABCDEFGHIJKLMNOPQRSTUVWXYZ R = EKMFLGDQVZNTOWYHXUSPAIBRCJ we denote the substitution of the rotor R. Then: p = 14 Rp 14 = () () abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ mnopqrstuvwxyzabcdefghijkl EKMFLGDQVZNTOWYHXUSPAIBRCJ () abcdefghijklmnopqrstuvwxyz opqrstuvwxyzabcdefghijklmn () CKMVLIGDOWPFQXSYATZUREJNBH ABCDEFGHIJKLMNOPQRSTUVWXYZ Consider as an example, which with the letter m happens. We start the substitution with m and replace it with the first substitution by y. Now the y is replaced by C with the help of the second substitution, C is again replaced by q in the third substitution. Applying this procedure to all elements results in the total substitution for i =

21 3.2 Structure of the Rolling Machine The most important component of the Enigma is the encryption unit (see Figure 4.4). This consists of three rollers 2, the reversing roller and an entry roller, which together do the actual encryption (or decryption). A roller is a flat cylinder made of metal. The roller has 26 contact pins evenly arranged on the two flat sides. An opening in the middle is used to attach the roller to an axle. The side surface of the cylinder is labeled with 26 letters or numbers from 1 to 26, the position of which is aligned with a contact pin. Inside the roller there are wires that connect two outer contacts. The wiring should be chosen randomly, which means 26! different possibilities exist. For example, in the Wehrmacht Senigma, the wiring of rotor I (rotor no. 1) is given by () ABCDEFGHIJKLMNOPQRSTUVWXYZ EKMFLGDQVZNTOWYHXUSPAIBRCJ. Three rollers can be plugged onto one axle, whereby the rollers can be in any position. If you have three reels, that results in 3! = 6 possibilities. Figure 4.4 shows an Enigma with an open lid. The three rollers (No. 4) with their letter rings are easy to see. If a roller is on the far right it is called the fast roller or R N for short, if it is in the middle it is called R M and if a roller is on the far left it is called the slow roller (because it rarely turns) or R L. Once the three rollers have been installed, a so-called reversing roller 3 must also be used. The reverse roller is constructed similarly to a roller, but only has contacts on one side. Each input contact is internally connected to another 4 input contact. If the encryption unit is completely plugged together, it can be inserted into the machine. The position of the rollers can be read directly from the rollers through a viewing window. The user can set position 2. In the case of the Marine Enigma M4 there are four rollers. 3 Often also called a reflector. 4 It should be noted here that no contact was made with oneself. As a result, the Enigma does not encrypt any letter by itself. This fact represents a weakness of the system, which was also exploited by the Allies in World War II. 12th

22 Change a roller by turning it around the axis by hand. Each roller can take up 26 different positions. This results in setting options with three rollers. The entry roller (ETW) was permanently installed in the machine. This is actually not a real roller, because it only represents the contact point to the roller unit. In addition, a fixed substitution was carried out by the entry roller. Reel locomotion The actual polyalphabetic character of the machine results from the fact that one or more reels rotate when each character is encoded. This means that the encryption alphabet changes each time a key is pressed. As previously calculated, different alphabets should result. This is not the case with most military models, as these machines have a mechanical feature. In the following we shall call this particular locomotion mechanism Enigma locomotion. This type of locomotion is very easy to explain using an ordinary odometer. Every time a disc makes a complete revolution (i.e. shifts from the letter Z to the letter A), the next higher disc (position) is also switched by one. The Enigma locomotion mechanism is very similar to this simple mechanism. Each roller has a groove (notch) on the left side. On the right side the roller has 26 grooves. As a counterpart to these grooves, there is a push pawl (metal rod) for each roller, which pushes upwards every time a button is pressed. The right-hand roller 5 (clearly visible in Figure 6.9) has 26 grooves on its right-hand side; the pawl engages in such a groove after every movement. The next time the button is pressed, the latched ratchet pushes up again, and the roller is moved forward every time. The middle roller R M again has its own pawl, but locking into one of the 26 grooves is prevented by the roller R N on the right, since it only has one groove on its left side. This means that the middle pawl can only engage every 26th time. The roller R M moves only once, while the right roller R N has already moved 26 times. The left roller 6 moves in the same way. The disk of the middle roller R M prevents the pawl from snapping into a notch in the left roller in most cases, exactly as in the case previously described between the right and middle roller. This construction results in a progression as in a Ki- 5 Also referred to as fast rotor R N. 6 Also known as the slow rotor R L. 13th

23 odometer, but showing a small anomaly. Let us assume that the push pawl for advancing the middle roller is engaged (i.e. the notch on the right roller is currently in the correct position). The next time the key is pressed, the rotor R N and R M would move. If the middle roller also reaches the notch position after it has moved forward (i.e. the pawl between the rollers R M and R L can engage), then the next time the left roller R L and the middle roller R M will move. The middle roller has turned twice in a row. This fact is often referred to in the literature as a double step anomaly. This anomaly shortens the period of the machine to = This also caused some problems with the decryption of the Enigma by the Allies during World War II. Table 3.2 shows an example of a rotor increment with a double step. In this position R L R M R N rotor I II III position A D T A D U A D V (R N locked) A E W (R M locked) B F X B F Y The roller position is I II III. This means that rotor I is in the left position, rotor II in the middle position and rotor III is in right position 7. Now we consider certain properties of the rollers. We interpret the data in Table 3.3 as follows: Rotor I has its notch Rotor notch Display I Y Q II M E III D V Table 3.3: Notches for the movement of rollers in the Wehrmacht Senigma 7, see also the glossary on page

24 at the letter Y. If the rotor I is locked, you can read Q instead of Y in the viewing window. The same applies to rollers II and III. This results in the following sequence. The starting position is ADT. If a key is pressed, the rotor R N moves on. If you press the button again, R N moves again and engages in position V. The next time the button is pressed, the middle rotor R M is also moved, since the pawl is locked in the notch of the right rotor R N and thus both rotors are moved by this. In this position (AEW) the middle rotor is now engaged. The next time the button is pressed, the slow rotor R L moves forward, but the middle rotor also moves with it because its own notch is locked. The same anomaly (double step) occurs with the fast rotor R N, only it is not noticed because the fast rotor, due to its notches on the right side, moves each time anyway Plug board In addition to the rollers, the Enigma has a plug board. This board is not changed during a coding 8. Every Enigma with a plug board comes with four to a maximum of 13 cables, each of which allows a plug connection between any two letters. With encryption, a letter is passed through the connector board before it reaches the roller unit. If the letter is inserted, it is swapped (substituted) by the letter connected to it. This substitution is involutorial, i.e. if A is connected to K, then A is substituted by K and K is substituted by A. The involutive character of the entire Enigma is not affected, because after the signal has flowed through the roller unit, it is once again passed through the plug board. The plug connections do not differ from those that were used before the drum encryption. 9. The plug board made it possible to considerably increase the possible settings of the Enigma for encryption. Any letter could be linked to any other letter. For one connector, that means 650 possibilities. In order not to count double permutations, this number has to be divided by two. Thus there are 325 possibilities to combine any two letters. This value can be 8 Can either be encryption or decryption. The machine makes no difference. 9 Each cable has two separate wires and each connector has two metal pins. 15th

25 can be increased enormously by using several plugs. Formula 3.1 can be used to calculate the possible permutations for a certain number of plug connections. 26! (26 2k)! k! 2 k (3.1) Table 3.4 was calculated using the above formula 3.1. In the table you can see that 11 plug connections result in the maximum number of permutations. According to Bauer [Bau00a], the Germans used 10 pairs of connectors for the Wehrmacht Senigma onwards. Number of affected plug connections Possible permutations Characters [%],,,,,,,,,, Table 3.4: Plug connections and number of possible permutations Keypad The Enigma keypad is arranged like a typewriter keyboard, with the difference that the letters P and L are positioned on the far left or on the right in the bottom row of letters. The connection of the keys (via the plug board) to the encryption unit is made via the stator 10. The type of wiring is important. Some models 11 are wired using the keypad scheme. The keys are 10 The stator is also called the entry roller (ETW). 11 examples are the Reichsbahn-Enigma, the Abwehr-Enigma and the Enigma K 16

26 connected to the rollers by the following substitution. () abcdefghijklmnopqrstuvwxyz QWERTZUIOASDFGHJKPYXCVBNML The Wehrmacht Senigma has no special substitution, all letters are connected directly. This results in: () abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ An important detail when switching the rollers is that they are always moved when a key is pressed, but before the actual encryption is carried out (see section 3.2.5) Lamp field The lamp field is on the same way as the keypad is arranged. There is an incandescent lamp under each window, which is marked with a letter. Current flow When a button is pressed, all pawls are moved upwards. Depending on the position of the notches, one or more rollers are moved. A circuit remains closed while the button is pressed. This is formed as follows (see Figure 3.1). Each button is connected to one pole of the voltage source (1) and the contact is only closed when the button is pressed. The keypad (2) is connected to the plug board (3), the current flows to this. If the actuated letter is plugged in, the current is diverted to the connected letter, if the letter is not plugged in, the current continues to flow without diversion. From the plug board, the current spreads through the entry roller (4), the output of which is connected to the right-hand roller. The current now takes a certain path through the rollers (5), depending on the roller position. The reversing roller (6) directs the current back into the roller unit, which in turn travels through the entry roller and the plug board. From the plug board, the current flows directly to the lamp field (7), where it lights up an incandescent lamp (which is connected to the other pole of the voltage source). This lamp shows the result of the encryption of a letter. 17th

27 Figure 3.1: Schematic structure and circuit of the Enigma 18

28 Figure 3.1 schematically shows the internal structure of the Wehrmacht senigma. The following settings were used: roller position IV I II, reversing roller B, ring position AAA, basic position UEY, plug connections (AS) (GN) (UI) (QM) (EX). All of these settings are explained in one of the next sections. The letter W is currently being pressed on the keyboard. When you press it down, the rollers move first. The fast rotor R N moves from Y to Z position. The current spreads from the W towards the plug board. Since the letter W is not inserted, it is not substituted there. The current therefore flows in the line via W to the next unit, the entry roller. This connects (with the Wehrmacht senigma) all lines directly to the fast rotor R N. Due to the current position of the fast rotor, the W contact of the entry roller is connected to the V contact of R N. A substitution now takes place through this roller, because V is internally connected to Y in roller II. As a result of the relative position of the two rotors R N and R M to each other, the Y is converted into a D. Analogously, this substitution process continues up to the reversing roller (the substitutions (DF), (FV) and (VD) result). This transforms the D into an X, which in turn runs backwards through the rotors (the substitutions (XR), (RM), (MW), (WN), (NI) and (IF) result). The F results, again due to the position of the fast rotor, a G. The current now flows on the line G to the plug board. There the current is diverted to N through a plug connection, which is connected to a contact of an incandescent lamp. This now lights up and shows the resulting character (N) of the encryption. 3.3 General settings The Enigma was mostly transported in a wooden box and a set of accessories is still available for use. At least three interchangeable rotors were required for operation, and in some cases there were even five or eight to choose from. The reversing roller was also interchangeable; there were up to three different reversing rollers. Cables with plugs were required for the plug board. Up to 10 connector pairs were common. Either a battery or a mains connection was required to operate the lamp field. The current keys for the encryption could be taken from a book, the so-called key book. Preparing the machine for encryption only requires a few simple steps. The lid of the machine must be opened and the rollers removed from the box. The desired rollers are now selected 19

29 and attached to the axle in the correct order. Then the rollers are reinserted and fixed. Another setting on the rollers is the ring position. Each roller has a letter ring, which shows a letter in the viewing window. This ring can be rotated relative to the core (the wiring). This is done by lifting a spring and turning the letter ring into the desired position. Now the lid of the machine is closed and each roller is rotated until the desired letter appears in the viewing window. Most models now only need to set the plug connections. 3.4 Key space The settings of the Enigma that are relevant for encryption are: 1. Selection of the rollers (which rollers are selected?); 2. Position of the rollers (in which position are they installed?); 3. Ring position for each roller; 4. Home position 12 for each roller; 5. Connector board. A key for the Enigma is made up of 5 different elements. Here, the key space size is to be calculated using the Wehrmacht senigma with five rollers. Unit Formula permutations Roll selection 3 Select rolls from 5 6 Roll position 13 3 Arrange rolls 10 Ring position Basic position! Plug board! 10! 2 10 Total Table 3.5: Size of the key area of ​​the Wehrmacht Senigma 12 Letter readable in the viewing window.13 The selection and order of the reels can also be written as = 60 (How many possibilities are there to divide 5 reels into 3 places). 20th

30 As can easily be seen from Table 3.5, the size of the key space is largely determined by the setting options on the connector board. This includes about 2 possible keys. 3.5 Key distribution In the previous section we saw how many setting options the Enigma provides. Now we will see which settings have been changed how often and how they have been exchanged. In the Third Reich there were different Enigma systems. The army and the air force used the same models, the Wehrmacht senigma. The Navy also used the Wehrmacht Senigma, but with minor changes. The Reichsbahn and the Abwehrdienst had their own models in use. Thus the models of the different departments were not compatible with each other. In addition to the different models, there were many different key networks. Different army units, air corps and SS units all used different key networks. Certain rules were defined for each key network and there was a so-called key book. The key book A key book contained the keys for the respective key network for a certain period of time. These books were conventionally distributed every few months. There are different settings for each day, some settings changed less often, some even several times a day. The roller selection and position was specified for each day, the ring position and the plug board settings were also different each day. All these settings formed the key of the day. In addition, there was the basic position. It was used to encrypt a spell key. Slogan key Each encryption required four parameters (roller position, ring position, basic position, plug board). So-called saying keys were used so that not every message was encrypted with the same day settings. A slogan key consisted of the current day key and a roller position. The position of the rollers had to be freely selected by the encryptor and encrypted with the help of the basic position. 21

31 Encryption works as follows. First the day key is set: the rollers are inserted into the machine in the correct order, the ring position is set individually for each roller and the plug board is plugged in. The basic setting is then set in the viewing windows and a freely chosen three-letter key (e.g. WKR) is encrypted with these settings. This key is keyed in twice 14 in a row to be on the safe side. Now the previously selected key is set and the actual message is encrypted with it. An example 15 will be given here. The first part of the encrypted message is: HCALN UQKRQ AXPWT WUQTZ KFXZO MJFOY RHYZW VBXYS IWMMV WBLEB DMWUW BTVHM RFLKS DCCEX IYPAH RMPZI OVBBR VLNHZ UPOSY EIPWJ TUGYO SLAOX RHKVC HQOSV DTRBP DJEUK SBBXH TYGVH GFICA CVGUV OQFAQ WBKXZ JSQJF ZPEVJ RO - If this message have been following settings used: Wehrmacht senigma with rotor position II I III, reversing roller B, ring position ZWD, basic position FRX, plug board (EZ) (BL) (XP) (WR) (IU) (VM) (JO). Let us now turn to the decryption of the encrypted text. The first six characters represent the encryption of the message key. With the known day key and the known basic position FRX, entering HCALNU results in the character string AGIAGI. AGI is the key to the following text. The decrypted text for this partial message without the saying key reads: AUFBE FELDD ESOBE RSTEN BEFEH LSHAB ERSSI NDIMF ALLEX ZXZTX UNTRUE INLIC HENFR ANZOE SISQE NANGR IFFSD IEWES TBEFE STIGU NGENJ EDERZ AHLEN TROTHEZ GENZHUMEN TRANSRIBLE this text to be transcribed to the following data Message: On the orders of the Supreme Commander, in the event of a French attack that is unlikely at the moment, the western fortifications are to be held in spite of any numerical superiority. 14 This represents a cryptographic weakness (ciphertext-ciphertext compromise). 15 This example is an authentic message from the Wehrmacht from 1938 and was already given in [DK90]. 22nd

32 Chapter 4 Model Variations and Related Machines 4.1 Commercial Models of the Enigma Enigma A The Enigma A was presented for the first time in 1923 by Chiffrierenmaschinen AG. It had four rotors, but no reverse roller yet. It can be characterized in the following way: R (i1, i 2, i 3, i 4) = ρ i 1 RN ρ i 1 i 2 RM ρ i 2 i 3 RL ρ i 3 i 4 RK ρ i 4. In the above equation R (i1, i 2, i 3, i 4) is the substitution obtained by the machine, i 1, i 2, i 3, i 4 indicate the position of the rotors. The four rotors are described by R N, R M, R L and R K. The position (see also Section 3.1) of the rotors is described with ρ i. The rotors of the Enigma A have 28 1 contacts. The rotor advance is irregular, toothed drive wheels with gaps are used for this. Each rotor is driven by such a wheel. They move regularly with periods of 11, 15, 17, 19. The 11-wheel has five teeth and six gaps. The 15-tooth wheel has nine teeth and six gaps, while the 17-tooth and 19-tooth wheels have 11 teeth and six and eight gaps, respectively. This allows the number of basic positions to be calculated. This machine did not yet have a plug board, so the number of keys was not too large. Not many copies of the first model were found. 1 In addition, three German special characters (ÄÖÜ) were used, according to [DK02] an infrequently used letter from the normal alphabet was omitted, presumably X, which was therefore not encrypted. 23

33 sold 2, it was soon replaced by the Model B. Figure 4.1: Enigma model A with open lid Enigma B The Enigma B was similar to model A and was presented a little later as an improved model. In contrast to model A, this model only had 26 characters, but still looked like a typewriter and was also not transportable. Enigma C It was not until model C from 1926 that was transportable. It was also very similar to the later military models outwardly and from a technical point of view. In this model a reversing disk was used for the first time and thus there were three interchangeable rotors (R L, R M, R N) and a reflector. kg). 2 What you can understand, because it was bulky (65cm 45cm 38cm) and heavy (50 24

34 Figure 4.2: Enigma model B By using the reflector, the current flowed through all the rollers twice and the machine was really involutor, i.e. there was no difference between encryption and decryption. This was a particular relief in practice, but was a serious disadvantage in terms of security. Enigma D The model D was again very similar to the model C, but was commercially successful for the first time and was legally bought by many European countries and the military. One difference to model C was e.g. that the reflector was adjustable. 25th

35 Figure 4.3: Enigma model C 4.2 Military models The military models have also undergone further development. The German Navy first experimented with a model of the Enigma (radio key C) in 1926, which was probably based on the commercial Enigma C. Small changes were made in Radio Key C in 1933, but it does not appear that this line has been developed any further. The German army used a version of the Enigma known as the Model G. This was first introduced in 1928 and was based on the commercial Model D. The Model G now served as the basis for the Enigma I of the Army and the Model M of the Navy Enigma I The Enigma I was the first major military model (introduced around 1930). It is very similar to the commercial models C and D (but of course had different roller wiring), the connection to the stator was made 26

36 Figure 4.4: Enigma model D now in alphabetical order, the reflector was no longer movable and a plug board was used. 27

37 This model defined the so-called Enigma equation c i = p i T S i US 1 i T 1. Here, p i indicates the plain text character, T the plug board substitution, S i the variable substitution of the rollers and U the substitution of the reversing roller. Since the fixed substitution T is involutive, it can be equated with its inverse substitution T 1 (T = T 1). On the left side of the equation is c i, the cipher. The substitution S (i1, i 2, i 3) looks like this for a 3-roller model: S (i1, i 2, i 3) = ρ i 1 RN ρ i 1 i 2 RM ρ i 2 i 3 RL ρ i 4 In the above equation, the rotors in the left, center and right positions are defined by RN, RM and RL. The position of the rotors relative to each other is described by ρ i and their differences (ρ ix iy). Enigma II This model was technically the same as model I, but also had a writing mechanism. It was rarely used because it was considered impractical. Wehrmacht Enigma The Enigma I of the army later became the so-called Wehrmacht model, which was used in the army and in the air force. There were five different rotors to change, these were identical to those of the Navy. Reversing roller D In 1944, reversing roller D was used for the first time. This roller could be wired variably, which was done several times a month. Watch box The watch was an additional device that was used in combination with the Wehrmacht Enigma. This box was connected to the plug board. 40 different positions could be selected with a rotary knob. Each position causes a different permutation, the involutive character of the machine was only retained in 10 positions. 28

38 This provided additional security as some attacks exploited the involutive character of the machine. Marine Enigma The Enigma M3 of the Kriegsmarine had three rotors, which could be selected from a set of five, seven and later eight rotors. The rotors I V were also used in the Wehrmacht Enigma, VI VIII were only used in the Navy. In 1942, the M4 version of the Marine Enigma with a fourth roller (Greek roller) was introduced. This roller (β, γ) does not move with it. So that the M4 was compatible with the M3, the reversing rollers were split into B thin and C thin, so that messages for the M3 model could be encrypted with the M4 model Reichsbahn-Enigma The Reichsbahn model was an older model without a plug board, and therefore it was less sure. It was based on the commercial three-reel Enigma, the reverse reel could be set but did not move. Abwehr-Enigma The Abwehr-Enigma was used by the German Abwehr-Dienst. It didn't have a plug board, but the reflector moved with it. This made it a four-roller machine. The rollers were moved with the help of a gear and switching cams (similar to the Enigma A), they had 11, 15 and 17 cams (teeth), with a period of 26. This is why the machine was also called a model. In the next two sections we will briefly take a look at some of the most popular rotor machines. 4.3 Enigma replicas The commercial Enigma (model D) was bought by many countries, and their patents could also be viewed. So it was only logical that many countries copied them. 3 The combination of β and B thin results in the reverse roller B. 29

39 4.3.1 GREEN The machine called GREEN by the Americans was built by the Japanese in 1934. It was a replica of the Enigma D, the special thing about it being the horizontally lying rotors. It was developed by a government commission in England in 1935. In principle, it was compatible with the Wehrmacht Enigma and was even used to decode German radio messages. In real use it had five rotors, but two of them did not move. These represent a non-involutive input substitution (in contrast to the Enigma plug board). The locomotion also differed from the locomotion of the rollers as implemented in Enigma machines. This was also regular, but the rotors had several notches for indexing. There were interchangeable rings with five, seven, or nine notches. The output was not an advertisement with incandescent lamps, but a strip printer M-325. During the years, the famous American cryptologist William Friedman designed the M-325 machine for the US Army. This was also based on the Enigma, but was initially not introduced due to a few shortcomings. It was only built in 1944 under the name SIGFOY. 4.4 Other rotor machines C-38 The machine C-38 is not compatible with the Enigma, because it is not based on the principle of the rotated alphabets, but it simulates BEAUFORT encryption steps. An irregular shift was caused by five (C-35, C-36) or six (C-38) drive wheels. The C-38 was designed by the Swede Boris Hagelin, the C35 and C36 machines were forerunners of the C38. The C-38 was used in the US Army as M-209 (piece) and in the US Navy as CSP

40 Chapter 5 Cryptanalysis Methods This chapter is not structured according to the classification of the methods used (e.g. ciphertext-ciphertext attack, plaintext-ciphertext attack), but chronologically according to the first use and according to country. 5.1 La Méthode des Bâtons This method was known very early. It was used in 1935 by the British Alfred Dillwyn Knox against the commercial version of the Italian Enigma. There it was called cliques on the rods or rodding. It was known to the French as the méthode des bâtons. This method was used during the Spanish Civil War, in which a commercial version of the Enigma was used by everyone involved, the British, the Germans, the Italians and the Spanish. With this method, also called isomorphism method 1, the fast rotor R N and its starting position could be determined. To do this, however, the following conditions had to be met: 1. The internal wiring of the rollers must be known. 2. There must be no plug board. 3. Probable words must be known. 4. Only the fast rotor is allowed to turn. The first point was given with the commercial version of the Enigma, with other models the wiring had to be determined first. This 1 We will see later where the name comes from. 31

41 was soon possible with the enormous number of intercepted radio messages that were used to determine the wiring. With regard to point two, it should be noted that the commercial Enigma did not yet have a plug board, while later German military models were all equipped with a plug board 2. The exception was the Italian Navy, which used a weaker model without a plug board until 1941 and the model of the German Defense, which also had no plug board, but had an irregular reel advance. The problem of finding probable words was also small, because German (or Italian) units usually started messages with stereotypes such as ANXDEN (where X stands for a space). Fulfillment of the fourth point is also easily achievable with this method, since a short, probable word is sufficient for this method and thus the probability that another rotor will turn (except for the fast one) is small. Let us now consider a model with three rollers where S (i1, i 2, i 3) = ρ i 1 RN ρ i 1 i 2 RM ρ i 2 i 3 RL ρ i 3 ci = pi S i US 1 i a polyalphabetic one Substitution 3, where pi are plain text characters and ci are cipher text characters. S i indicates the known alphabets defined above and U is the reversing roller. If the above equation is formulated as 4 c i S i = p i S i U, then the sequence c i S i is the image of the sequence p i S i with the monoalphabetic substitution U, from which it follows that the two sequences are isomorphic. The cryptanalytic attack now consists in finding an index i for the probable word pi, p i + 1, .., p i + n, (composed of the characters pi) so that the words ci S i, c i + 1 S i + 1, .., c i + n S i + n and pi S i, p i + 1 S i + 1, .., p i + n S i + n 2 This weakness was the Enigma for the Germans too aware of why the plug board was introduced at the Wehrmacht Senigma. 3 Also commonly referred to as the Enigma equation. 4 The prerequisite for this is the condition S 1 i S i = ε, i.e. S i must be involutorial. 32

42 are isomorphic to each other. If there are contradictions to the expected isomorphism, the index i can be excluded. This method of elimination works because any two (i.e., random) sequences are not isomorphic. The longer the consequences, the fewer missed hits. One and very should serve as example sequences here. The pairs (es) and (ie) contradict each other, they screech (English screech), and can thus be excluded. In the case of a machine with three rollers, there are six options for inserting the rollers and = various options for positioning them. So a total of = different positions would have to be tested. On closer inspection you can see that this is not necessary. The regular advance of the Enigma's rollers means that the medium and slow rotors (R M, R L) only rarely move. The middle rotor turns e.g. only after every 26th movement of the fast rotor. This makes it likely that when you type a short word, only the fast rotor will move. The two stationary rotors form a pseudo-reversing roller with the reversing roller U (see Figure 5.1).This roller U (i 2, i 3) = ρ i 2 RM ρ i 2 i 3 RL ρ i3 U ρ i 3 RM ρ i 3 i 2 RL ρ i 2 has the same properties as the U, it is monoalphabetic and involutorial . This now results in the simpler starting position and S i = ρ i R N ρ i c i S i = p i S i U (i 2, i 3), where S i is of a simpler form. Now it is only necessary to test all the rollers in the fast position in all positions. The fast rotor and its position can be determined from this. Once the fast rotor and its position have been determined, the location and position of the further rotors can be determined from the resulting fixed cycles. A catalog with = 1352 entries for all U (i 2, i 3) can be used for this. This means that all settings such as the location and position of all rotors can be determined. 33

43 Figure 5.1: Rollers for Bâtons method 34

44 The example used by Deavours and Kruh in [DK85] should be given here. We assume it is encrypted to reconnaissance UPYTEJOJZEGBOT, where rotor I was used as the fast rotor. In table 5.1: Méthode des Bâtons with stripes continuously. For this purpose, the columns of the rotated alphabet of rotor I (see table 3.1) are used as stripes. For each pair of plaintext and ciphertext letters, two strips of the respective column of the rotated 35

45 alphabets placed. The pair of strips is shifted depending on the column index. To find out the correct rotor position, each line must be checked for involution. In Table 5.1 only one row is involutor, row Y. In all other rows there are pairs that violate the isomorphism. Line A shows two pairs that are not isomorphic in bold type. Line Y JGMGFUHRWCNSEW UZCZBJOTAMQESA results in nine pairs (AW), (ES), (BF), (CM), (GZ), (HO), (JU), (NQ), (RT), which all double cycles of the pseudo - Reversing roller U i 2, i 3 are. We have thus identified the right rotor and determined its position. The middle and left rotors can then also be identified. For this purpose, as already mentioned, we use a catalog with all possible substitutions for U i 2, i 3. With the substitution pairs obtained previously, we can identify the correct roller position and roller position in the catalog. 36

46 5.2 First Polish Successes The Poles were the first to achieve serious success in breaking the Enigma. According to [DK85] they registered the use of a new machine encryption as early as 1928, when the Enigma G, a forerunner of the Enigma I, was introduced by the German army. On the Enigma I was introduced, which later also became the Wehrmacht Enigma. Between 1928 and 1932 not much was known about the machines, only the 6-letter key at the beginning of a message had been clarified. For example, if a message began with KSRPIR on a day, it was noticeable that every other intercepted message on that day which had K in the first position also had a P in the fourth position. The same was true for digits two and five and digits three and six. In 1932 it was then clear that a modified Enigma was in use and that the first six letters represented the doubled rotor start position in encrypted form, whereby the same settings (rotor position, plug board, ring position) were used for all messages one day Help came from the French in 1931. From 1931 to 1938, Hans-Thilo Schmidt, an employee of the cipher office of the Reichswehr Ministry, known under the code name Asche, forwarded dozens of documents such as instructions for use, key instructions and even daily keys to the French cipher service via the French agent Rex. The French in turn passed the documents on to the British and Poles. How important this betrayal was to the Allies is easy to see from the material handed over. Instructions for use gave the cryptologists information about the changes made to the Enigma compared to the commercial model, short plain-text ciphertext examples and daily keys for two whole months helped to analyze the newly wired rollers. The breakthrough With this newly gained information, the Poles achieved their breakthrough. Not much was happening on the British side at this point; This may have been due to the fact that Poland, as a small country directly bordering Germany, was more fearful. In September 1932 the Polish cipher bureau in Warsaw hired three young mathematicians. 37

47 These were selected from two dozen math students, and they had to attend a short cryptanalysis course beforehand. These young mathematicians were called Marian Rejewski, Jerzy Różycki, Hendryk Zygalski. Rejewski soon concentrated his work on the intercepted radio messages Deciphering the message keys The roller wiring was determined by the Poles on the basis of the extensive radio communication material, with the help of known daily codes and from examples in the Enigma manuals. But even before the roller wiring was determined, the Poles deciphered the encrypted spell key. Marian Rejewski suspected that the freely chosen slogan keys have a certain characteristic deviation from the uniform distribution. The Germans actually used many stereotypical cipher keys such as aaa, sss and other letter repetitions. The pure repetition of letters was explicitly forbidden in 1937, but stereotypes still occurred. Horizontal (WER, ASD), vertical (QAY, RFV) and other sequences of the keypad were used. A large amount of messages were picked up every day. The first six characters of each message represented the encrypted, doubled slogan key. If there were about 80 messages, each letter appeared at least once in each position of the first three positions. This was necessary for the following procedure. Let us consider six permutations P 1, P 2, P 3, P 4, P 5 and P 6 denoted 5. For example, this means that P 4 is the permutation with a fixed basic position in the fourth position. As an example we take the i-th character of the proverb key as a. This results in XP i = a and XP i + 3 = b (for i 1, 2, 3), where the first permutation P i X to a and the second permutation P i + 3 equation to ap 1 i X to b maps. With X = ap 1 i the second P i + 3 = b results. If the involutor character of the enigma is also known, then P 1 i can be replaced by P i and the result is XP i P i + 3 = Y. The signs a and b therefore place the products P i P i + 3 of the unknown Permutations P i for i fixed 6. In Table 5.2, 65 encrypted, doubled 5 In [Rej80] are denoted by A, B, C, D, E and F. 6 This situation can be visualized as follows: The operator of the machine enters the first letter X, the lamp a lights up, the second press 38

48 1. AUQ AMN 14.IND JHU 27.PVJ FEG 40.SJM SPO 53.WTM RAO 2. BNH CHL 15.JWF MIC 28.QGA LYB 41.SJM SPO 54.WTM RAO 3. BCT CGJ 16.JWF MIC 29 .QGA LYB 42.SJM SPO 55.WTM RAO 4. CIK BZT 17.KHB XJV 30.RJL WPX 43.SUG SMF 56.WKI RKK 5. DDB VDV 18.KHB XJV 31.RJL WPX 44.SUG SMF 57.XRS GNM 6. EJP IPS 19.LDR HDE 32.RJL WPX 45.TMN EBY 58.XRS GNM 7. FBR KLE 20.LDR HDE 33.RJL WPX 46.TMN EBY 59.XOI GUK 8. GPB ZSV 21.MAW UXP 34 .RFC WQQ 47.TAA EXP 60.XYW GCP 9. ENT THD 22.MAW UXP 35.SYX SCW 48.USE NWH 61.YPC OSQ 10. ENT THD 23.NXT QTU 36.SYX SCW 49.VII PZK 62.YPC OSQ 11.HXV TTI 24.NXT QTU 37.SYX SCW 50.VII PZK 63.ZZY YRA 12.IKG JKF 25.NLU QFZ 38.SYX SCW 51.VQZ PVR 64.ZEF YOC 13.IKG JKF 26.OBU DLZ 39 .SYX SCW 52.VQZ PVR 65.ZSJ YWG Table 5.2: 65 encrypted slogan keys belonging to a daily slogan code listed. The following procedure is now used to determine the cycle for the product P 1 P 4. We start with proverb key no. 1. Here a changes over to a and thus forms a cycle of ones (a). According to Nr, the character s only merges into itself and thus also forms a cycle of one (s). It continues with the cycles of two. (bc) is formed by numbers 2-4 as follows. The b in no. 2 (or no. 3) goes over into a c, the c in turn goes directly back into a b according to no. A cycle of two has formed. Likewise, (rw) is formed by Nr and Nr. Longer cycles are also formed, such as (dvpfkxgzyo) and (eijmunqlht), which are indicated by numbers 5, 49, 27, 7, 17, 57, 8, 63, 61 and 26 as well as by numbers 6, 12, 15, 21, 48 , 23, 28, 19, 9 and 45 are defined. All cycles together result in the following cycle decomposition: P 1 P 4 = (a) (s) (bc) (rw) (dvpfkxgzyo) (eijmunqlht) P 2 P 5 = (d) (k) (ax) (cgy) (blfqveoum) (hjpswizrn) P 3 P 6 = (abviktjgfcqny) (duzrehlxwpsmo) This complete decomposition of the cycle is of great importance and is called a characteristic set or the characteristic of a certain day (because the basic position was changed daily). The ones of X also light up the lamp b. The inverse process should also be possible due to the involutive character of the machine. If you press a in the first position, X should light up, in the fourth position, after pressing b, X should light up too. Let us now consider the following operations one after the other: a goes over to X and X goes over to b again. This operation is called the product of permutations. If we now combine the letters a and b, we get the unknown product P i P i + 3. 39

49 cycles play a special role. They are referred to as females; their appearance was, as we shall see later, also of crucial importance for another cryptanalytical method. Before we proceed with the actual deciphering of the proverb keys, let us consider a sentence from group theory that is important to us. Theorem (Rejewski) 1 If two permutations of the same degree consist only of disjoint transpositions, then their product contains an even number of disjoint cycles of the same length. The reverse of this theorem is more interesting for our application. Theorem (Rejewski) 2 If a permutation with an even degree consists of an even number of disjoint cycles of the same length, then this can be represented as the product of two permutations consisting of disjoint transpositions. This sentence applies exactly to our case. The known product P 1 P 4 is to be broken down into its components P 1 and P 4. This sentence is formulated differently in [Bau00a]: In a genuinely involutive permutation P k with an even alphabet circumference, the cycles of the product P i P i + 3 occur in pairs of equal length. If P i contains the cycles of two (x 1 y 1), (x 2 y 2), ..., (xkyk) and P i + 3 contains the cycles of two (y 1 x 2), (y 2 x 3), .. ., (ykx 1), then P i P i + 3 contains the k-cycles (x 1 x 2 ... xk), (yk, yk 1 ... y 1). If a k-cycle of P i P i + 3 is written in reverse (marked with) and one in normal (marked with) sequence, the pairs of two-fold cycles of P i and P i + 3 are directly or offset one above the other. (x 1 x 2 ... x k 1 x k) (y 1 y 2 ... y k 1 y k) Here indicates that the cycle is written in reverse order. To determine whether and how much the second cycle should be postponed, Rejewski used the fact that the ciphers mostly came up with stereotypical key words out of laziness. In Table 5.2 you can see that the encrypted saying key SYX SCW occurs five times (and therefore most frequently). One can easily imagine that the most frequently used proverb key aaa was encrypted here. This assumption defines the following two-fold cycles: 40

50 P 1 (as) P 4 (as) P 2 (ay) P 5 (ac) P 3 (ax) P 6 (aw) From this the correct pairing can be found for P 3 (ax). This is marked with a vertical arrow. for P 6 (aw) the pairing is found (abviktjgfcqny) (xlherzudomspw) (xlherzudomspw) (bviktjgfcqnya) This in turn results in the two-fold cycles of P 3 and P 6: P 3 = (ax) (bl) (vh) (ie) (kr) (tz) (ju) (gd) (fo) (cm) (qs) (np) (yw) P 6 = (xb) (lv) (hi) (ek) (rt) (zj) (ug ) (df) (oc) (mq) (sn) (py) (wa) In order to be able to determine all further P i, this procedure is continued in the same way. The cycles of a P i that have already been found can be used. If these are not enough, one again has to guess the key through intuition. Here it should be sketched how Bauer in [Bau00a] managed this for this example. If we apply the cycle (qs) from P 3 to the no. 1 AUQ AMN, we get a key of the form ** s (where * means a character that is still missing). Furthermore, we know from our first assumption (SYX SCW corresponds to aaa) that P 1 contains the cycle (as) and thus we get s * s. The stereotypical key phrase sss is obvious here, in P 2 there is also the cycle (see below). (axt) (blfqveoum) (d) (ygc) (jhnrziwsp) (k) This results in the two-fold cycles for P 2 and P 5: P 2 = (ay) (xg) (tc) (bj) (lh) (fn ) (qr) (vz) (ei) (ow) (us) (mp) (dk) P 5 = (yx) (gt) (ca) (jl) (hf) (nq) (rv) (ze) ( io) (wu) (sm) (pb) (kd) 41

51 Now only the cycles of P 1 and P 4 have to be determined. The saying key no. RJL WPX has the form * bb. According to P 1, the r in the first position can only form (rb) or (rc). (rb) is more likely in our case, the key to the sentence is then bbb. This information can be used to pair the two cycles of two. Another spell key is required for pairing the cycles of ten. The key Nr LDR HDE results from * kk (from P 2, P 3, P 5, P 6). Again we use the stereotype kkk, from which (lk) and (kh) follow for P 1 and P 4. The following pairing results: (a) (bc) (dvpfkxgzyo) (s) (rw) (iethlqnumj) This results in the double cycles for P 1 and P 4: P 1 = (as) (br) (cw) (di) (ve) (pt) (fh) (kl) (xq) (gn) (zu) (ym) (oj) P 4 = (sa) (rc) (wb) (iv) (ep) (tf) (hk ) (lx) (qg) (nz) (uy) (mo) (jd) With the permutations P 1, P 2 and P 3 all key words can now be deciphered. P 1 = (as) (br) (cw) (di) (ve) (pt) (fh) (kl) (xq) (gn) (zu) (ym) (oj) P 2 = (ay) (xg ) (tc) (bj) (lh) (fn) (qr) (vz) (ei) (ow) (us) (mp) (dk) P 3 = (ax) (bl) (vh) (ie) ( kr) (tz) (ju) (gd) (fo) (cm) (qs) (np) (yw) With this procedure, if enough radio messages (ca) were available for one day, all selected message keys could be deciphered. Table 5.3 lists the deciphered spell keys. Of the 65 keys, 25 duplicate ones have been omitted, the rest are divided into 18 letter repetitions, 16 horizontal letter groups and four vertical letter groups. Only the two keys abc and uvw do not correspond to a row of letters on the keypad (see Figure 5.2), but because the letters follow one another in the alphabet, they are easy to predict. The deciphering of these slogan keys did not provide the Poles with any information, but from 1933 onwards it enabled them to determine the internal wiring of the rollers. 42

52