The Story of Cracking the Enigma. Part One - Marian Rejewski and the Reverse Engineering of Enigma

Introduction

This is the second article in a series I am writing on the Enigma cipher, the first being my article on the machine itself. See: Enigma - Historical Lessons in Cryptography. This is part of a longer series on the role of cryptology and codebreaking in the history of computing.

This article is the first of the series on the breaking of Enigma. Which will follow the story from the earliest breaks by the Polish to the Turing Welchman Bombes, the engines of the code breaking factory that was Bletchley Park.

These articles are intended to be low level enough to get into the key details but hopefully easy enough for anyone to follow.

In this first article I want to talk about the Polish genius that reverse engineered and enabled the breaking of Enigma in late 1932, some years before the British.

The story of the Polish codebreakers is one of heroic efforts in the face of imminent danger leading to eventually fleeing the oncoming German Nazi threat as it began its advance across Europe.

The story is well told in many books, however my favourite and I think the most complete is XY&Z: The Real Story of How Enigma was Broken by Dermot Turing. It’s a great read and tells the full story of what happened to the Polish codebreakers as they worked on Enigma leading up to the invasion of Poland and beyond. I am focussing on the reverse engineering of the machine in this article, but I encourage the reader to seek out XY&Z for a much more complete story of the Polish codebreaking heroes.

Historical Context and Background

A Place in History

If you visit Bletchley Park today you will find a memorial to the Polish codebreakers tucked away near the cottages behind, and to one side of, the famous mansion. It may seem like it is a little out of the way. However, when the monument was installed much of the museum grounds you see today were not as accessible or open to the public. At the time you entered the park near the Mansion and the Polish codebreakers monument was at the heart of the site. Now days you enter the park from the opposite end of the site and would be forgiven for missing the monument given all the other things to see now that more huts are open and there are many more exhibits on display.

The spot occupied by the Polish memorial is a lovely little corner of the park and in no way diminishes the significance of the it. But I am sure that if it were installed today it may be put in a more prominent position with regard to the orientation of the park as it is now. Such was the importance of the Polish codebreakers to breaking Enigma and Bletchley Park.

That said, as the veil of secrecy lifted on the breaking of Enigma during World War II and the histories began to get written, they were often told with firmly from the British point of view and asserting that Bletchley Park where it was all done from start to finish. Sometimes consigning the Polish story to a few paragraphs. This was probably due to a couple of factors, one was the lack of information about the codebreaking generally but I think another reason was that people thought saying that the Enigma machine was broken in Poland some 7 years before the British got to it somehow diminished the story of Bletchley Park and what the British did. This is not the case at all of course. What was done at Bletchley was beyond just the pure codebreaking and beyond Enigma. Additionally the British had to tackle the Enigma machine as it evolved and into in something more complex than what as solved by the trailblazing Polish codebreakers.

That said, when one thinks of Enigma and it’s breaking, it probably summons images of Alan Turing and Bletchley Park rather than that of Marian Rejewski, Jerzy Różycki and Henryk Zygalski. But Rejewski, Różycki and Zygalski did indeed crack Enigma seven years before Bletchley did and in doing so gave the British a huge advantage at the start of World War II.

In his book The Hut Six Story, Gordon Welchman, responsible for architecting the codebreaking processes at Bletchley Park and creating the British Bombe along with Alan Turing and who we will hear much more about in a later article, said:

The Poles managed to give us the details of the machine and the benefit of their expertise in time for us to exploit them early in the war. We would ultimately capture mean Enigmas, but, as things turned out everything was to depend on what we achieved in the first three months and later, in the very first year of the war. In fact the Hut 6 balloon might never have gotten off the ground at all if I had taken six months instead of three to get things moving.

He goes on to say:

Rejewski, working alone, began an investigation that entitles him to be regarded as one of the greatest cryptanalysts of his day.

Why Poland?

Poland was geographically squeezed between two historically aggressive neighbours in Germany and the Soviet Union who in the past squeezed the country out of existence. It is therefore no wonder that in the early 20th Century, the Polish developed intelligence services including a codebreaking function to keep an eye on activities from their neighbours. Hence it is no wonder that the Polish intelligence services took an interest in deciphering German radio traffic such that an agency was established to do exactly that.

Marian Rejewski, a Polish mathematician, was recruited into that agency: The Polish Biuro Szyfrów (Cipher Bureau), to attack the German Enigma cipher.

The codebreakers started by doing statistical analysis of the cipher text and found that it was most likely a polyalphabetic cipher and that the first six letters of the cipher text were most likely the message key.

However they had a problem. Even though the Polish codebreakers knew the Germans were using Enigma and they were well aware of the commercial version of the machine, the German government and military had altered the machine and until the Polish understood how, they were could not reconstruct its workings or fully attack the cipher.

The French Connection

Between World War I and the start of World War II the French had been building an intelligence network to keep an abreast of goings on within continental Europe. Of particular interest was Germany and the Soviet Union. In fact the Soviet Union was of most interest to the English and the French. As such the French intelligence services established a relationship with the Polish whereby they agreed to share information. The Poles would supply information about their Soviet neighbours and the French would reciprocate with intelligence from Germany and any other sources.

This turned out to be a very fortuitous agreement for the Poles, because the French we running an agent in Germany with close links to the cipher services and Enigma in particular.

Agent Asché

Hans-Thilo Schmidt was the purest of traitors, one motivated my money. He wanted the good life and wasn’t succeeding in business so turned his ideological ambivalence into a revenue generator.

Schmidt, codenamed Asché, was also a most valuable asset, in that he had access to material relating to Enigma via his role in the German army cipher office.

Schmidt literally walked in off the street and presented himself to the French and offered his services. For money of course. Initially he provided manuals for the Enigma machine including the German military operating procedures.

The French, knowing of the Polish cryptography efforts passed the material to the Biuro Szyfrów as part of the intelligence sharing arrangements they had.

Agent Asché went on to supply the French with further information relating to Enigma and other intelligence over a two year period. After the fall of France to the Germans, Schmidt’s handler was captured by the Gestapo and he was eventually betrayed. He was arrested in 1943 and died of apparent suicide later that year.

The Polish get up and Running

With the information on the Enigma operating procedure from the French via Hans-Thilo Schmidt accompanied by intercepted cipher text messages, the Polish codebreakers were able to start work in earnest on first reconstructing the military Enigma and then onto to breaking it.

Schmidt’s material confirmed that the Enigma was generated using an Enigma that used three rotors that were wired differently from the commercial Enigma and the plugboard that didn’t exist on the commercial version. They also confirmed that the the first six letters of a message were the message key.

It is important to note that while the French were able to provide the Polish with operating manuals for the military Enigma machine they did not have any codebooks or key material and they didn’t know the wiring of the rotors. As was discussed in the Enigma machine article, knowing how the machine works doesn’t mean you can immediately decrypt messages. The Poles didn’t even know the inner workings of the machine yet. So there was much work to do just to get to the starting line.

Rejewski was tasked with doing this work and how he did it was nothing short of genius.

The State of Play at this Point

At this point in our story, the Poles have established the Biuro Szyfrów (Cipher Bureau) to work on attacking German ciphers, in particular Enigma. The French are running a spy in Germany with access to Enigma material and are providing it to the Poles via their intelligence sharing agreement. Marian Rejewski is set the task of analysing and reconstructing the machine.

Before they can crack Enigma cipher, they must fully understand the machine itself.

This is where we leave our historical section and move to the technical discussion of how the Polish reconstructed the workings of the Enigma machine via intercepts and how they got themselves into a position to crack the Enigma cipher itself.

Operating Procedures

Rejewski knew the Enigma machine consisted of three rotors, a plugboard, a lapboard and a keyboard. What he didn’t know was the wiring of the rotors or how the keyboard was wired to the rotors.

Of note is that at this time the Enigma machine used a set of only three rotors which could be inserted into the machine in any order. Later the Germans would add two additional rotors to make a set of five to choose from for the key.

Via the material provided by Hans-Thilo Schmidt, the Polish code breakers knew that once the machine was setup with its daily key the operating procedure at the time told the cipher clerk to use a particular set of starting positions for each rotor (the Grundstellung) for the day.

Once the rotors where set to the Grundstellung setting, the cipher clerk would choose three random letters to establish a message key. A Message key was required to ensure that the exact same configuration was not used for every message as this would produce what is called a depth which gives codebreakers an edge and a way into the cipher text.

The chosen random letters were then typed into the machine twice and the resulting cipher text added as the first six letters of the message. The message key letters were entered twice to create a checksum of sorts to minimise errors on receiving.

The receiving clerk would have the machine set to the daily Grundstellung setting, enter the first six letters and confirm they deciphered to the same three letters. For example if the first six letters were XYZABC they would expect to see something like DEFDEF when deciphered. If not the receiving cipher clerk didn’t see three repeated letters, they would know there was a transmission error or some other issue. Otherwise and all going well DEF would then be set as the starting position for the rotors on the receiving Enigma machine which could then be used to decipher the body of the message.

Operating Flaws

Using the same Grundstellung setting for all messages for the day and double enciphering the message key while convenient and useful for detecting errors was a big mistake.

For a start it meant that every message sent on a network had the same base setting, this meant the codebreakers had a large volume of material each day that had identical properties governed only by a message key for which the codebreakers knew a fragment of information in that they would know that for every message for the day the exact same settings were used to encode the first six letters.

The double enciphering of the message key meant that each message had a kind of inbuilt crib or information known about the plaintext. They knew that the first letter of the message key deciphered to the same letter as the forth, the second to the fifth and the third to the same letter as the sixth.

Marian Rejewski, working largely in isolation and in secret focussed his attack on Enigma on these first six letters that leaked information about the nature of the key.

To do this Rejewski turned to the mathematics of permutations.

Below we briefly introduce what a permutation is and talk about the key concept of disjoint cycles

Permutations

A mathematical permutation is defined as the re-ordering of elements of a set. The Enigma machine can be described mathematically as the product of the permutations (see below) that arise from the scrambling mechanisms in the machine. It’s not hard to intuitively see that a substitution cipher is just a permutation on the set of characters in the alphabet.

Rejewski would apply theories and axioms of permutation mathematics to reverse engineer the military Enigma machine (which he had never seen). He would use this to work out the wiring of the rotors and to work out how the rotors were ordered in the machine and finally as a method to help break the messages encrypted on the machine.

A quick side note here: The mathematics involved is complicated to explain but is not overly hard to understand. It would take an entire article to do it justice and in any case it’s not really the point of this piece. So I am not going to go into the full explanation of all the proofs and working here, there are many in depth papers and articles on this (see the references section below). I will endeavour to cover the fundamentals and how Rejewski brilliantly applied the mathematics to solve Enigma.

Disjoint Cycles

As covered in the Enigma machine article, an Enigma machine cipher is a polyalphabetic substitution cipher. A substitution cipher can be expressed as a permutation where the effect of the permutation is to change the plaintext letter into a cipher text letter.

Permutations can in turn be expressed as the product of a set of disjoint cycles. The cycles can be constructed by writing the plaintext alphabet on top of the cipher alphabet (i.e. showing the substitution cipher key) and follow the links between each letter from the plaintext to the cipher text you will eventually make a cycle. The cipher won’t make a single cycle (hence disjoint) and you’ll need to repeat making cycles until you have included all letters in the cycles. When complete you will have the permutation expressed as a set of disjoint cycles

This is quite hard to explain in words, but the diagram below helps to show how this works. Note that each letter is only included once.

Take the substitution cipher:

Follow the cycle of plaintext letters to cipher text letters as shown:

This shows the construction of the 10 letter cycle shown in blue. If this process is repeated for all the letters in the cipher it can be seen that it is composed of a 10 letter cycle, a 7 letter cycle, a 5 letter cycle and a 4 letter cycle. The notation shown is the typical way of expressing the cycles.

This is a simple and clear way to show the internal structure of the permutation, which will become important later.

Enigma Expressed in Terms of Permutations

The scrambling component of Enigma consists of six elements each given a label by Rejewski to enable him to compose the mathematical expression to describe the machine:

• The reflector. R
• The slowest and left most rotor. L
• The middle rotor. M
• The fast and right most rotor. N
• The plugboard or steckerbrett. S
• The wiring of the plugboard to the entry wheel. H

Refer back to the Enigma machine article for a more detailed description of these components in context.

Each of these components, S,H,N,M,L,R, can be expressed as a permutation. In addition to these six permutations that describe the physical components of the machine there are permutations that describe the motions of the rotors. This gives a complete description of the machine in terms of permutations.

Because Rejewski was focussing only on the first 6 letters of the cipher text (the double enciphered message key), he reasoned that because of the way the rotors triggered one turn over of their neighbouring rotor every 26 turns, it would be rare that the left most and middle rotor would move during the input of the first 6 letters. Therefore he need only consider one of those rotor movement permutations into his system. Rejewski designated this permutation as P.

Because the right hand rotor moves 1/26th of a rotation on each key press, the P permutation effectively translates one letter to the letter next to it. While the rotor wiring might not be known the permutation a rotor in the right hand positions performs is known. i.e. The permutation P is known.

Rejewski initially assumed the entry permutation, H would be the same as the commercial machine which was wired to the entry wheel in the order of the keys on the keyboard. i.e. q was wired A, w was wired to B, e wired to C and so on. However this proved wrong and he assumed there must be some scrambled wiring but eventually he tried a guess that the wiring might be alphabetic i.e. a wired to A, b wired to B etc. Surprisingly this turned out to be correct. When a permutation does not change the order of the set, it is said to be the identity permutation. It is simple to see that a wiring that doesn’t transform one letter into different one has no effect on the cipher. Hence the H permutation is not considered in any of the final equations discussed below as it has no effect on the cipher at all.

We’ll come back to H briefly later, but because it is the identity permutation and has no effect on the mathematics we can leave it out of the equations below to simplify things.

With this Rejewski could describe the machine in terms of a product of permutations:

• The path through the scrambling mechanism: SPNMLR
• The path back through the scrambling mechanism after going through the reflector: L ^-1 M ^-1 N ^-1 P ^-1 S ^-1

Note that Rejewski did not know the nature of any of these permutations when he started the analysis.

The combined expression: SPNMLRL ^-1 M ^-1 N ^-1 P ^-1 S ^-1 = (SPNML)R(SPNML) ^-1 represents the complete permutation for the first letter of an Enigma message.

Subsequent letters would be:

• SP ² NMLRL ^-1 M ^-1 N ^-1 P ^-2 S ^-1 = (SP ² NML)R(SP ² NML) ^-1
• SP ³ NMLRL ^-1 M ^-1 N ^-1 P ^-3 S ^-1 = (SP ³ NML)R(SP ³ NML) ^-1
• …
• SP ⁿ NMLRL ^-1 M ^-1 N ^-1 P ^-n S ^-1 = (SP ⁿ NML)R(SP ⁿ NML) ^-1

If we further refine the expression and denote the path through the scrambler (SPNMLR) as X and the path back (L ^-1 M ^-1 N ^-1 P ^-1 S ^-1 ) as X ^-1 we can further simplify the notation to: X R X ^-1

In the mathematics of permutations this expression is the conjugate of R by X. Importantly there is a theorem in permutation theory that states:

The disjoint cycle structure of R and and any of its conjugates has the same shape.

This is indeed important and we will return to it later.

At this point we have the complete description of the Enigma machine in terms of a product of permutations and we have recognised that the machine is conjugated by the reflector permutation.

Exploiting the Message Key Flaw

Recall that at the time Rejewski was analysing the Enigma traffic the operators would setup the machine with the daily key, encipher a random three character message key twice and append the resulting six enciphered letters to the start of the message for the receiving end to use to reconstruct and check the message key.

Each of these six letters was generated by a composite permutation as defined above. Rejewski denoted these first six permutations as A,B,C,D,E and F. Because of the double enciphering the first and forth letters are cipher text from the same plaintext letter, the second and fifth letters are the same and the third and sixth are the same.

For illustration purposes, if we assume that letter is k, then we know that permutation A and permutation D both result the letter k. We don’t know the first and forth letters are the plaintext *k, but we know that permutation A and permutation D are working on the same letter.

This means we have some information about the key and can apply some analysis, logic and the mathematics of permutations to make some further assertions. As an example lets assume A changes ?? to V and D changes ?? to P. Then recalling that the Enigma machine is self-reciprocal (Plain text -> cipher text and cipher text -> Plain text), and applying some permutation mathematics we can also assert that the composition AD changes V to P. So without knowing any plaintext we can reason about the composite permutation AD.

Using this knowledge and given enough cipher text messages, each letter of the alphabet will eventually show up in the first 6 letters, allowing Rejewski to construct a complete cipher alphabet for the permutation AD. In other words the substitution cipher generated by the composite permutation AD. Similarly the alphabets for BE and CF could be constructed.

The structure of these composite permutations in terms of disjoint cycles can now be determined. These cycles provided a pattern determined by the key. Rejewski called this the characteristic form of the key.

If we have a sufficient number of messages (about eighty) for a given day, then, in general, all the letters of the alphabet will occur in all six places at the openings of the messages. In each place they form a mutually unique transformation of the set of letters into themselves, that is, they are permutations . . . They may be represented as disjunctive products of cycles and then assume a very characteristic form, generally different for each day. Rejewski, 1984, p. 274 via Chris Christensen

A Trapdoor Opens

So far this is not breaking the Enigma cipher directly but rather subjecting it to mathematical analysis to derive any patterns which provide a lever to understand the nature of the machine and break the key. Patterns are the enemy of cryptography.

Rejewski noticed that the disjoint cycle patterns built by using what was known about how the permutations generated the cipher text provided a pattern for the daily key. A pattern that would be generated by the order the rotors were in the machine and what the initial start position of the rotors were (the ground state of the rotors) and what the plugboard setting were.

This is still a huge number of combinations. Rejewski is looking for the trapdoor that gets him into the cipher despite the enormous number of combinations available to generate the key. From his analysis of the cipher and looking for ways to exploit the message key flaw he found a huge one.

What Rejewski discovered when he assembled the expressions for the permutations AD,BE and CF is that they form a conjugate. The product of the permutation for the first letter and the permutation for the forth letter (in the case of AD) is conjugated by the permutation for the plugboard.

From the Enigma machine article, recall that the plugboard adds an enormous number of combinations to the key settings of an Enigma machine.

The theory introduced above states that the disjoint cycle forms of a permutation and any of its conjugates have the same structure. This means the disjoint cycle structure of AD, BE and CF are the same regardless of the plugboard permutation. Which means the pattern of disjoint cycles derived from the first 6 letters of a set of messages is only affected by the wiring of the rotors, the order of the rotors in the machine and the ground setting.

This effectively eliminates the 150,738,274,937,250 combinations added by the plugboard and leaves 6 (the six letters at the start of the message) * 17576 (ordering of three rotors * possible start positions) = 105,456 possible rotor orderings and ground settings.

105,456 is still a large number, but it’s not an impossible number to deal with. There would be 105,456 unique characteristics (different disjoint cycle patterns) which would match to a particular rotor order and ground state.

The Poles would set about making a catalogue of all 105,456 characteristics. To do this they used the first machine used for code breaking in our story of Enigma. The Cylometer. Which will feature in the next article.

But before they could make use of it, Rejewski would need to determine the wiring of the rotors. Once again he used permutation theory.

A Method for Determining the Rotor Wiring

From the information Rejewski had from the first 6 letter of every message he was able to construct the composite permutations AD,BE,CF. What he needed to determine were the permutations A,B,C,D,E,F i.e. the permutations that generate the first six letters. This meant factoring the composite permutations.

This would allow him to work out the effect of the wiring of the rotors on the first six letters which would in turn would allow him to reconstruct the rotors.

Assuming the left and middle rotors are fixed during the encoding of the first six letters, it is the effect of the right most rotor that will be visible and therefore possible to determine. If all three rotors that were in use are used in the right most position over the course of a days, weeks or months that Rejewski is analysing, he will be able to see the effect of all rotors and eventually reverse engineer the wiring of all of them.

He still has a way to go however as he doesn’t know the plugboard settings which will mask the rotor wiring. Even thought, as discussed above, the rotor permutations look the same regardless of the plugboard allowing him to reason about the order of the rotors in the machine. Until he works out the plugboard settings for a particular key Rejewski can’t determine the rotor wiring and as a result which cycle patterns marry up to which rotor orders.

Factoring the Composite Permutations - Rejewski’s Theorem

Rejewski used five theorems from the mathematics of permutations (taken as stated from the article Polish Mathematicians Finding Patterns in Enigma Messages by Chris Christensen):

Theorem 1: The product of transpositions. If two permutations of the same degree consist solely of disjoint transpositions, then their product will consist of disjoint cycles of the same length in even numbers.

Theorem 2: The converse of theorem 1. If a permutation of even numbered degree includes cycles of the same length in even numbers, then this permutation may be regarded as a product of two permutations, each consisting solely of disjoint transpositions.

Theorem 3: Letters entering into one and the same transposition of permutation X or Y, enter always into two different cycles of the permutation XY.

Theorem 4: If two letters found in two different cycles of the same length of the permutation XY belong to the same transposition, then the letters adjacent to them (one to the right, the other to the left) also belong to the same transposition.

And finally a theorem derived by Rejewski which is referred to as Rejewski’s theorem.

Theorem 5: If H(i) = j; i.e., H = (…i j…); then T−1HT = (…T(i)T(j)…). Notice that this implies that H = (. . . i j . . . ) and T−1HT = (. . . T(i) T(j) . . . ) have the same disjoint cycle decomposition.

As mentioned above, I am not going to go deep into the full details of how these are applied or the proofs. Again, Chris Christensen’s article describes this far better than I can. Needless to say it was these that Rejewski used to factor the composite permutations by applying them to the varying lengths of cycle in the composites.

Note that there are a number of factorisations for each composite which are mathematically valid, but are not correct for the particular key. This means each factorisation has to be checked to see if it is possible within the other constraints of the machine and related permutations.

To factor the shorter cycles using the theorems above was relatively straightforward for Rejewski because there were only a few possible factorisations of the permutations. All of which could be tested in short order to see if they were valid. However the longer the cycles the greater the number of possible factorisations making checking all of them time consuming.

Here Rejewski exploited not mathematics to reduce the number of possibilities to test but human nature and/or bias in the choices of the operators. He reasoned that the choice of the indicator settings are probably not as random as they could be. Operators would tend to choose consecutive letters or letters that are above and below each other on the keyboard. By first using these common patterns as inputs, Rejewski was more often than not quickly able to determine the correct factorisation.

This is not the last time we will see the human nature and operator tardiness exploited in the story of cracking Enigma. For me it is the thing that separates out the great codebreakers from purely being great mathematicians or linguists. The ability to see the whole picture and reason outside of the mathematical box.

Rejewski constructed the equations below for the permutations that create the first six letters.

Note The constant Q represents composite permutation for the reflector, middle rotor and left most rotor. Which because Rejewski assumes won’t move during the enciphering of the first six letters, are therefore constant across all six equations.

• A = SPNP ^-1 QPN ^-1 P ^-1 S ^-1
• B = SP ² NP ^-2 QP ² N ^-1 P ^-2 S ^-1
• C = SP ³ NP ^-3 QP ³ N ^-1 P ^-3 S ^-1
• D = SP ⁴ NP ^-4 QP ⁴ N ^-1 P ^-4 S ^-1
• E = SP ⁴ NP ^-4 QP ⁴ N ^-1 P ^-4 S ^-1
• F = SP ⁵ NP ^-5 QP ⁵ N ^-1 P ^-5 S ^-1

Remember that in addition to Q, P is the entry permutation that changes when the right most rotor moves, N is the permutation implemented by the wiring of the right most rotor and S is the permutation implemented by the plugboard.

At this point we should take stock of where we are in the process of understanding the machine. But first a brief stop to discuss message keys.

Working Out the Message Keys

Even though Rejewski didn’t know the rotor wiring yet, he could work out the message keys. Recall that an Enigma key consists of the daily setting plus three randomly chosen letters that determine the message key.

As mentioned above, Rejewski correctly assumed that operators would be lazy when choosing message keys and may habitually use sequences or even just the same letter three times.

From the theorems above, Rejewski was able to prove that:

1. Letters belonging to one and the same transposition of permutation X or Y always belong to two different cycles of the same permutation XY.

2. If two letters in two different cycles of the same length of permutation XY belong to the same transposition, their neighbouring letters also below to the same transposition.

Using these facts and the structure of the disjoint cycles Rejewski could test to see if common sequences (aaa,bbb,qwe etc) were possible.

In this way Rejewski could deduce relatively quickly if a particular sequence was used and thereby break the message keys.

In his paper on the topic Rejewski observes that he was able to determine the message keys at this point without needing to break any of the other components of the cipher. This is an amazing achievement and critical to the later job of breaking whole Enigma messages.

Rejewski also observes:

It would have been better for the Germans if the message keys had not been enciphered at all because encipherment, as we have seen, not only did not guard against exposure but in addition supplied a bonus in the form of six successive permutations, A to F - Rejewski, 1981

In what at first glance appears to be a good practice that makes the messages more secure, the Germans in actual fact reduced it significantly.

Getting back to the story. For now Rejewski is less focussed on breaking the messages themselves but rather on reconstructing the machine and its components.

What Rejewski Now Did and Didn’t Know

At this point Rejewski has a method for determining the rotor orders in the machine through the disjoint cycle patterns. In doing this he worked out the composite permutations AD, BE, CF then by applying theorems of permutation mathematics and exploiting operator habit he was able to work out a method for factoring the composite permutations to discover the individual permutations, A,B,C,D,E and F that create the first six letters. From which he derived the six equations shown above.

What Rejewski did not know were the permutations:

• Q - The middle rotor, left hand rotor and reflector
• S - The plugboard
• N - The wiring of the right most rotor

Rejewski wanted to solve for N in order to discover the wiring of the right most rotor. In order to do this he needed to know S, the plugboard configuration for a given key.

This stands to reason, he needs to eliminate the effect of the Steckerbrett to isolate and analyse the effect of the right hand rotor.

If he knew S Rejewski could use the equations to solve for N. He was setting about doing this when he got a lucky break in the form of new information from the the French run spy Hans Thilo Schmidt. Codenamed Asché.

Asché Provides a Fortuitous Break

On the 9th of December 1932 Rejewski was provided with another dump of documents from Hans Thilo Schmidt via the French intelligence services. This time the data included the daily Enigma keys for all of September and October 1932. As it turned out having the keys for these two months was incredibly fortuitous.

The Germans would change the rotor order every quarter i.e. every three months. Given the third quarter of the year finishes at the end of September and the forth starts in October, this means Schmidt had provided not only the daily Steckerbrett configurations and ground settings but also keys that had two different rotor orderings and therefore two different rotors appearing in the right hand position. The position Rejewski could use to determine the wiring if he knew the Stecker configurations, which he now did for September and October.

As a reminder, the daily keys would include the plugboard configuration, the rotor order and the initial setting for the rotors. The ground setting for an Enigma machine. What wouldn’t have been on the key settings was the wiring diagrams for the rotors of course. This was not relevant to the setup of the machine, but is of critical importance to breaking it. The Poles never got the rotor wiring detail from Schmidt so they had to work it out.

By substituting in the now known S to his equations, Rejewski could manipulate the equations and again use the theorems above to solve for N and thus work out the wiring of the rotor in the right most position. He could do this by looking at the effect of the permutations on the set of cipher text messages collected from the months of September and October. Because the keys they knew spanned the quarterly change of rotors, Rejewski could work out the wiring of two of the three rotors in use.

I am glossing over some of the mathematical detail here for the sake of brevity. But it is sufficient to say that through the work he put in as described above, Rejewski already had all the tools he needed to work out the right hand rotor wirings based on the analysis of the permutations the machine performed by the time he got the material from Schmidt.

The stolen information was a lucky break for solving the wiring of Enigma and saved Rejewski a lot of time and effort in further analysis. But the fact that he alone had done all the hard work to get himself in a position that having the key settings enabled him to immediately put it to use to get to a solution that allowed him to reverse engineer the entire machine was another amazing achievement.

The Enigma Machine Exposed

It is at this point that Rejewski indeed had all mathematical tools and equations to solve the rotor wiring. He plugged in all the values and using messages across many days in September and October he expected to see valid results for N. However, to his surprise, the results he saw violated the rules of the mathematics and were therefore not valid. His assumption initially was that this was caused by a rotation of the middle rotor. When testing for this he found that this was not the case either. It turned out the problem was the assumption about the wiring between the plugboard and the rotors. The infamous H discussed above. After trying a few combinations without success, in a stroke of luck and perhaps intuition Rejewski guessed early on the wiring might be alphabetical and therefore the identity permutation. He was of course correct and H could effectively be ignored. This is interesting because when the British started to attack Enigma they got hung up on this. Rejewski comments in his paper that he didn’t think the British codebreakers had worked this out before he told them:

I have every reason to believe the British cryptologists did not manage to solve the problem because of the difficulty caused by the connection of the initial drum. First, in July 1939, when representatives of Polish, French, and British cipher bureaus attended a meeting in Poland, the first question put forth by the British cryptologist Alfred Dillwyn Knox was:“What are the connections of the initial drum?’ Second,Penelope Fitzgerald, Knox’s niece, in her book, The Knox Brothers (1978),stated that Knox was furious when he realised how simple it Was.

We’ll hear more about ‘Dilly’ Knox in a later article. It seems the British assumed the entry permutation wouldn’t be that straightforward and had simply not tested for it!

When he corrected for the identity permutation Rejewski found that the logic worked and he could get the correct plaintext using the corrected equations.

Once Rejewski knew the wiring of two of the three rotors in use at the time, it was relatively straightforward for him to then solve for the reflector and the third rotor.

Finally Rejewski had completed the reconstruction of the Enigma Machine. The Poles now had complete knowledge of the Enigma machine including the wiring of the rotors and procedures used by the Germans. They even made replica machines of their own to assist later with deciphering messages after breaking the daily keys. But first they needed a method for breaking the keys themselves.

Really the Polish are just at the starting line in terms of breaking actual messages. They obviously couldn’t rely on leaks of codebooks and keys supplied via espionage. However through Rejewski’s genius work they have a critical set of tools with which they can pull apart the cipher and build the required methods for breaking the daily keys and read the German encrypted communications.

After reverse engineering the Enigma machine in secret and in isolation, Rejewski was joined by Jerzy Różycki and Henryk Zygalski to begin the codebreaking effort. In the next article we’ll see what they did and how they did it.

Conclusion

Marian Rejewski working in isolation was able to completely reverse engineer the military Enigma machine and put the Polish codebreakers in a position to break the cipher and read German military traffic. The team of Polish codebreakers went on to do just that. Well before the British were up and running at Bletchley Park.

Their efforts would allow the British codebreakers to get up and running much quicker than would have been otherwise possible providing a critical intelligence advantage at one of the most critical times.

Rejewski’s role in the Enigma story is hugely important, it’s hard to overstate how important the work he did was. He is truly one of the greatest cryptanalysts of his day.

References

There are certain to be errors and mistakes in the text above. These are all mine and are not those of the authors of the reference material below.

I used many sources in the making of this article. The main ones that helped me the most with understanding the processes and getting my head around the mathematics were:

• Polish Mathematicians Finding Patterns in Enigma Messages by Chris Christensen
• Marian Rejewski and the First Break into Enigma by Bill Casselman
• Permutation Groups and the Solution of German Enigma Cipher by Jiri Tuma

In addition I used Rejewski’s 1981 paper, How Polish Mathematicians Deciphered the Enigma

There are many great books on the topic of Enigma and the Polish codebreakers. The books listed below were the primary sources for this article.

Dermot Turing’s book XY&Z: The Real Story of How Enigma was Broken was invaluable. Telling the story of the Polish codebreakers and their collaboration with the French and British.

For any article on Enigma, David Kahn’s legendary book The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet is essential reading.

I always return to Simon Singh’s excellent Codebook for technical detail,context and to crib his great ability to explain complicated things in a straightforward way.

Secret History: The Story of Cryptology by Craig Bauer was also a vital reference.

The Hut 6 Story by Gordon Welchman was a useful source of quotes and information on the impact of the Polish codebreaking efforts.

I have many great books on Bletchley Park, Enigma and Cryptography. I have cataloged them all here on Libib

Appendix - Pronunciation of Polish Names for English Speakers

• Jerzy Ro ́z ̇ycki (Roozh-IT-ski)
• Henryk Zygalski (Zig-AHL-ski)
• Marian Rejewski (Rey-EF-ski)