Marian Rejewski and the First Break into Enigma
Posted 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...
During 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 machine
The 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
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 cycles
A 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:
- Every permutation can be expressed as a product of disjoint cycles, uniquely up to the order in which the cycles are written.
This I have just demonstrated.
- The inverse of a cycle is the cycle written backwards. If X = (A B C D E F) then X -1 takes F to E, E to D, etc. so is the cycle (F E D C B A).
- A cycle can be shifted cyclically without changing it. Thus (A B C D E F) and (B C D E F A) are the same permutations.
- I define a reflector to be a permutation that swaps all the letters in the alphabet. The reflector permutation in the Enigma machine is a reflector in this technical sense. The important point is not just that applying the reflector twice makes no change - i.e. is the identity permutation - but that no letter is taken into itself.
- The Enigma encryption formula after k turns of the rotor is
|E = PkQ P -k R Pk Q -1 P -k
which may be written as
if Xk = P-kQ Pk. If X, Y are any two permutations, the product X Y X -1 is called the conjugate of Y by X, and there is a wonderful fact about conjugates - the cyclic form of a permutation Y and any of its conjugates has the same shape. More precisely, we can write this new cyclic expression in a very simple way. If the cyclic expression for Y has the cycle (a b c d e), for example, then that for the conjugate X Y X -1 has the cycle (aX -1 bX -1 cX -1 dX -1 eX -1), where in each case the entries in the cycle denote the result of applying X -1 to the appropriate letter. This is trivial to see - if Y takes p to q then the conjugate XY-1X -1 takes pX -1 to pX -1 XYX -1 = pYX -1 = qX -1.
- In particular: The conjugate of a reflector is a reflector. Thus every Enigma encryption is a reflector.
- The key observation of Marian Rejewski, often called Rejewski's Theorem - the trick that made things work for him - is a fact about the product of two reflector permutations. Roughly speaking, the cyclic expression of the product of two reflectors has cycles that come in pairs, each cycle in a pair being of the same length. It is messy to state precisely, but an example should make it sufficiently clear. Suppose S is one reflector and T is another. If the cyclic expression for the product ST contains a cycle
(a b c d e f g) then it also contains another, different cycle (G F E D C B A), with S = (aA)(bB)(cC)(dD)(eE)(fF)(gG) ... .
I'll prove the theorem for an example that should indicate the proof for the general case. Suppose S = (ah)(gf)(cb)(ed), T = (ad)(bf)(ec)(gh)) . We can picture the two reflectors in one diagram (S = pink, T = blue):
The product ST then implements the rule follow pink, then blue. We can picture its cyclic representation best in two parts. If we start with a we get the cycle (a g b e), and if we start with h we get (h d c f):
Things become clearer if I unscramble these:
The cyclic expression for ST is (a g b e)(h d c f), and if I write it backwards underneath this I get the pair
(a g b e)(h d c f)
(h f c d)(a e b g)
This should at least suggest how the general proof of Rejewski's Theorem goes. This result is not a deep mathematical fact, but its proof is elegant and simple. It is fascinating to realize that it was this that made Rejewski's initial attack on Enigma feasible.
Part III. The message indicators
It 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 A0, A1, etc., for all of these are all reflectors. We know that
X A0 = F
X A3 = K
Y A1 = A
Y A4 = J
Z A2 = H
Z A5 = I
Since the Ai are reflectors Ai-1 = Ai, we then have
F A0A3 = K
A A1A4 = J
H A2A5 = I
If we have enough six-letter headers, we can reconstruct the products A0A3, A1A4, A2A5 :
|A0A3 = (A I U X C H) (B W) (D Q L) (E O S F K Y) (G) (J) (M R V) (N) (P T) (Z)
A1A4 = (A J C E G K U X O T I Z H) (B S W N Q P L R D Y F M V)
A2A5 = (A S G B L P) (C V U E H I N) (D Q X W Y O) (F K Z T J M R)
Where does that get us? Using Rejewski's Theorem, we see that it drastically limits the possibilities for the permutations A0, etc. themselves. The simplest case would be A1 and A4. Here, we must be able to write one of the 13-cycles under the other in reversed order to get the reflectors A1. Possibilities are
|(B S W N Q P L R D Y F M V)
(H Z I T O X U K G E C J A)
leading to (B H) (S Z) ... ,
|(B S W N Q P L R D Y F M V)
(Z I T O X U K G E C J A H)
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 AiAi+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.
- Marian Rejewski, How Polish mathematicians deciphered the Enigma, Annals of the History of Computing 3, July 1981, pp. 213-234.
- ----------, Mathematical solution of the Enigma cipher, Cryptologia 6, January 1982, pp. 1-18.
- There are many good web sites about Enigma. Here is a short selection from among many good articles in Wikipedia about the topic. These all have many links to further material. Nothing that I have found on the Internet explains the mathematics well.
- Technical Details of the Enigma Machine
- Robert Churchhouse, Codes and ciphers: Julius Caesar, the Enigma, and the internet. Published By Cambridge University Press in 2002.
- ----------, A classical cipher machine: the ENIGMA, Bulletin of the Institute of Mathematics and its Applications 27 (1991), 129-137.
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.