Marian Rejewski and the First Break into EnigmaPosted November 2009.The settings of an Enigma machine were exactly the same for writing and reading messages, which simplified its practical use enormously. It also simplified the task of the Allies enormously...
Bill Casselman
IntroductionDuring World War II the British read German military communications regularly, because they were able to decipher messages encoded on the Enigma machines used by the Germans. As the war developed and the German networks became larger and more complicated, the methods used by the British became correspondingly more and more sophisticated, depending on a huge effort with thousands of people involved in interception, decipherment, and interpretation of the German signals. But the process started long before the war, in 1932, with a tiny group of Polish mathematicians. They made the first breaks into the Germans' code by relatively simple techniques that were fortunately able to deal with the relatively simple German encoding techniques of those early days. One of the very first steps, and one of the most intriguing, was made by Marian Rejewski, who applied the theory of permutations in an interesting way to figure out `message keys' used by German operators as well as the structure of the German Enigma machines. I hope to explain here the mathematics behind Rejewski's accomplishment. [For more on Enigma, see my follow-up Feature Column.] Part I. A simplified Enigma machineThe real Enigma machines were rather complicated to start with, and got more and more complicated as the intelligence war went on. The one who was sending a message typed it into a keyboard of 26 letters, and the encrypted message appeared on a lamp display, one letter at a time. The signal passed through a plug board, an entry wheel, and three movable rotors before reversing itself in a reflector and passing out again through the same group of enciphering devices. At the end of some fixed period, which was originally 24 hours in length, the rotors and the plugboard were changed, as was also a ring on each rotor that determined how the rotors advanced with input, and a starting state. The setup for each period was circulated to an entire network ahead of time (also secretly, of course). But I am only interested in a single mathematical idea, and I shall work with a drastically simplified machine. Simplified, but not so far in fact from a model used by Rejewski. The machine we'll work with has in common with all Enigma machines one absolutely characteristic feature: if any stage character x were input and character y came out, then if character y had been input, instead character x would have come out. This will be made mathematically precise in a moment. The settings of an Enigma machine were exactly the same for writing and reading messages, which simplified its practical use enormously. It also simplified the task of the Allies enormously. The (virtual) machine I am going to work with has just one rotor, no plugboard, no complicated entry wheel, and ... well ... no keys and no lamps. The rotor implements a simple substitution cipher, but it advances one letter with each input letter, so it amounts to a simple polyalphabetic cipher, and it is well known how to read large enough messages of this type. The real Enigmas were much more secure. But I am going to ignore deciphering that uses the statistics of language and show instead how one odd feature of the enciphering process allowed Rejewski to introduce some more interesting mathematics.
To encipher a letter with this machine, you locate the letter on the outside rim, and then follow the path that the current state of the machine indicates. For example, if the machine is in its initial state, A becomes first C, then Z, then E. When you have done this, the rotor moves, so now the machine looks like this:
In this state, A becomes B, then successively A, Z, C, D, Z, and finally Y. The rotor moves again, so now A is enciphered to Q. When the message EYQ is received, the operator puts the machine in its initial state and the carries out the same process, getting AAA again. To summarize: to the input letter is applied a number of transformations following a path through the contacts, the rotor, and the reflector. Mathematically, each step as well as the composite of several steps is a permutation of the alphabet, or what might also be less formally called a rearrangement. The natural way to describe a permutation is by listing first the alphabet in order, then underneath this list the transformed letters. The rotor above, for example, amounts to this: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z C A I G Z H M R E L K J P F T S Q O N U W Y X V B D It is more natural to write the reflector (whose action is indicated by arcs between letters on the innermost circle) as (AU)(BE)(CZ)(DL)(FM)(GO)(HV)(IN)(JY)(KW)(PQ)(RT)(SX) rather than A B C ... U E Z ... since it makes transparent the fact that it is its own inverse. I recall that the inverse of a permutation is the permutation which undoes the original rearrangement. Thus the inverse of the rotor is A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B Y A Z I N ... E The total effect of the Enigma encryption of an Enigma machine is as a product of permutations. In the initial (or default) state of the machine the transformation can be expressed as
if we apply things from left to right, where Q is the rotor permutation and R is the reflector. How do we describe what happens later on, after the rotor has moved? Let P be the alphabet rotation permutation: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B C D E F G H I J K L M N O P Q R S T U V W X Y Z A This is the permutation you can read off from the contacts between the outer rim of the machine and the outer rim of the rotor after one turn. As you can also see from the diagrams above, after k turns the encryption is
Part II. Permutations and cyclesA permutation of size n is a rearrangement of n items in a given order. Most of the time I'll take these items to be the alphabet, but occasionally a smaller set, such as 1 2 3 4 5 6 7 8. A typical permutation would then be 5 8 7 1 4 3 2 6. A permutation can be just a list of the rearrangement in the proper order, but cyclic notation is often a more useful method. This is what I have used to write the reflector permutation above. For example, in the example of the 8 digits above we have 1 -> 5, 5 -> 4, 4 -> 1, which is where we started. Then we start with a new item: 2 -> 8 -> 6 -> 3 -> 7 -> 2. So we can write the permutation in cyclic notation as (1 5 4)(2 8 6 3 7). Ciphers are essentially permutations. At any given moment the machine is ready to implement a transformation from input letter (plain text) to output letter (cipher text) - i.e. encipherment permutes the alphabet. There are a number of important results about permutations that we shall need:
Part III. The message indicatorsIt was only late in the game that real copies of the German Enigma machines were obtained by the Allies. Up to then, their knowledge of the physical details of the machine rested on solid conjecture, together with a knowledge of the commercial machine, with which the military machine had much in common. The more important thing to know was the nature of the permutation implemented by each one of the rotors in the military machine. I am going to give you some idea of how Rejewski figured this out by explaining how his technique would work on my simplified machine. The principal reason the technique worked was because of a flaw in the Germans' procedure for sending messages. When someone wanted to send a message, he had to choose at random a place for each the three rotors to start - he had to choose a triplet of letters, like ABC or QEX, called the message indicator or message key, as the starting positions. This is because if all machines on the network started in the same position for every message, every message for the day would be using the same polyalphabetic cipher, and the enemy might conceivably have enough cipher text to apply standard methods of cryptanalyis to figure out what was up. But them the problem arises, how to transmit the indicator? The operator would enter the three letters into his machine with the machine set on some one position fixed throughout the network, and put the corresponding cipher text at the head of the message sent. Now if these were garbled in transmission, which could very easily happen, the message would be completely lost, so it was very important that they arrive safely. This was assured by having the operator continue on, typing the three letters over again, and add those three cipher letters after the first three. This duplication, in cipher, was a fatal error. For example, in our simple Enigma, suppose the indicator was ABC, and the network starting position was the default position. The cipher text would begin ETROIF.
In a single day, the Poles might intercept a hundred messages or more. They all started with the machine in the same state. In the encryption of the indicators, it would happen most of the time that the slow rotors would not move, so in effect the machine would be the simple machine I am working with. (Strictly speaking, you need to know some wonderful stories about French spies, plug board data, a stolen Enigma manual, and some unbelievably good luck in guessing the entry wheel correctly, but that's a story you can get from Rejewski himself.) So, suppose we have been reading a bunch of messages encrypted on my simple machine, but with possibly a different rotor from the one used above. What can we tell from knowledge of only the first six characters of several messages? What does each message tell us? Say the first six letters are F A H K J I. What we know is that the inputs for the 1st and 4th letters, 2nd and 5th, 3rd and 6th letters are the same. Say the input is the unknown sequence of letters XYZXYZ. The enciphering substitutions, which I'll call A_{0}, A_{1}, etc., for all of these are all reflectors. We know that X A_{0} = F Since the A_{i} are reflectors A_{i}^{-1} = A_{i}, we then have F A_{0}A_{3} = K If we have enough six-letter headers, we can reconstruct the products A_{0}A_{3}, A_{1}A_{4}, A_{2}A_{5} :
Where does that get us? Using Rejewski's Theorem, we see that it drastically limits the possibilities for the permutations A_{0}, etc. themselves. The simplest case would be A_{1} and A_{4}. Here, we must be able to write one of the 13-cycles under the other in reversed order to get the reflectors A_{1}. Possibilities are
leading to (B H) (S Z) ... ,
leading to (B Z) (S I) ... . Plus 11 other possibilities. In this business, with the stakes as high as they are and the apparently endless amount of work facing the Poles, 13 is a very small number. Armed with a relatively small list of possible initial Enigma permutations, Rejewski was able to start to consider possible message keys. What he suspected, and discovered to be true, was that lots of times German operators would choose very simple message keys, like AAA or BBB or ABC or XYZ. So he presumably expected that if he made lists of all the possible message keys, which with a bit of cleverness could be reduced to lists of perhaps 50 or so, many simple keys would appear, far more than could be explained by chance. This proved to be so. It also turned out that slightly different techniques of permutation calculations, together with the knowledge of the products A_{i}A_{i+3} could help figure out the wiring of the fast rotor in use that day. But that is a different story ... To find out more ...This essay has been reprinted several times, but this publication includes valuable appendices by Cy Deavours and Jack Good. This is the only place that I am aware of that explains closely the process Rejewski followed, although it is rather condensed. In particular, it does not really attempt to explain the mathematics involved. This is a slight variant of the first article by Rejewski. Both were translated from original documents in Polish. Almost all of this volume of Cryptologia is about Enigma. One of the clearest explanations of the mechanical operation of the Enigma machine. Chapter 9 of the book by Churchhouse has one of the very attempts, other than Rejewski's own, to explain how the double encipherment of message keys gives away so much information. But Churchhouse does not seem to have read Rejewski's account, relying instead on the much less detailed account in the appendix of the book Intercept: the Enigma war by Josef Garlinski. The appendix was written by Tadeusz Lisicki, apparently with the help of Rejewski who was still alive at the time. One of the strangest things about Churchhouse's discussion is that he doesn't seem to realize that Rejewski used his techniques to deduce the structure of the rotors in the military Enigma machine. Churchhouse's book refers to this article for details of the cryptanalysis of indicators. It offers a proof of Rejewski's observations about the products of complete involutions. The exposition is labored.
Bill Casselman Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services. |
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance |