March 9, 2011

The Enigma Machine Part 3 The Science of Secrets How the Poles Cracked the Enigma Code

"MARIAN REJEWSKI WAS THE
GREATEST CRYPTANALYST OF ALL TIME"



Enigma Codebreakers (00:03:39m)


The Enigma was a complex electro-mechanical device used by the German Army and Navy during World War II to encrypt messages. Their encryptions were so elaborate that German Command was convinced that nobody could ever break their ciphers. They were wrong.

German soldiers encrypting/decrypting message on Enigma

A team of Polish mathematicians and cryptanalysts Marian Rejewski, Jerzy Rozycki, and Henryk Zygalski were the first to uncover the secrets of the Enigma. They laboriously studied the Enigma and developed solutions, techniques, and specialized instruments to crack the codes. Meanwhile French and British Intelligence remained clueless never suspecting that the Poles had already cracked the Enigma code. In fact the Poles had been deciphering and reading secret German messages for years, right up to the eve of the Invasion of Poland.

The French and British were astonished when the Poles presented them with fully functional replicas of the Enigma machine.

Enigma Machine
Marian Rejewski was a genious. He applied pure mathematical analysis of group theory as the means to discovering the internal wiring configuration of the rotors. His work was well under way when secret documents were given to him by Captain Gustave Bertrand, chief of French radio intelligence. The documents were procured from a spy in the German Cryptographic Service, Hans-Thilo Schmidt, and included information about the Enigma settings for the months of September and October 1932. French Intelligence presented the documents to Rejewski in December 1932 thus enabling him to reduce the number of unknowns and reconstruct the wiring system and nonrotating reflector.

In the words of historian, David Kahn, "The solution was Rejewski's own stunning achievement, one that elevates him to the pantheon of the greatest cryptanalysts of all time". The mathematical theorem that Rejewski used was hailed by one mathematics professor as "the theorem that won World War II."

Rejewski studied the ciphertexts, intrigued by its permutations, particularly the first six letters of each message. He discovered that Enigma operators were using a six-letter indicator to ensure security, that is, the message key setting consisted of three letters which was typed twice. This was the ground setting shared by all German operators for global settings for that day and through which the Germans unwittingly introduced a weakness in their cipher. Rejewski detected that the indicator, in plaintext followed specific patterns: for example, the first and fourth letters were the same, the second and fifth were the same, and the third and sixth were the same. Other patterns might be the second and fifth letters, the third and sixth letters, This new insight gave the Poles the means to break the Enigma codes.

Rejewski knew that certain pairs of letters were related. For example, assume that there were four messages with the following indicators: BJGTDN, LIFBAB, ETULZR, TFREI. B was related to T: L was related to B; E was related to L; T was related to E; and I was related to E; This was defined as a "cycle of 4" as it required four jumps until it returned to the starting letter. With enough messages on any given day, all the letters of the alphabet would be covered by; different cycles of various sizes, changing to different cycles the next day.

It became apparent to Rejewski that despite the unpredictability of the Enigma machine itself, the Enigma operators had a tendency to choose predictable letter combinations as indicators, say, for example, a girlfriends initials. Rejewski's insight, in addition to the data received, made it possible for him to deduce the six permutations which corresponded to the encryption at six consecutive positions of the Enigma machine. These permutations were then described by six equations which represented the internal wiring of the entry drum, rotors, reflector and plugboard. Because of the large number of unknowns in the set of his equations Rejewski began to encounter difficulties. (In 1980, he commented that without further data it could not be determined whether the six equations were soluble.)

Rejewski solved another obstacle that had been puzzling British cryptologists. In the commercial model of the Enigma, the keys were connected to the entry drum following the sequence of letters according to the German keyboard, that is QWERTZU. However, the military version of the Enigma had been modiified so that this was no longer the case. Instead. the letters followed in alphabetical order, ABCDE and so on. Rejewski understood the German penchant for orderliness, was thus able to resolve the problem. He later commented that "from my pencil, as by magic, began to issue numbers designating the connections in rotor N. Thus the connections in one rotor, the right-hand rotor, were finally known."

German Enigma Keyboard and Lamp Panel
The secret documents obtained from French Intelligence provided information regarding rotor settings for a two month period. In the second month, German operators had inserted a different rotor in the right-hand position. This made it possible for Rejewski to discover the wiring of the two rotors using the same method of calculation.
 

Rejewski later recalled: "Finding the [wiring] in the third [rotor], and especially... in the [reflector], now presented no great difficulties. Likewise there were no difficulties with determining the correct torsion of the [rotors'] side walls with respect to each other, or the moments when the left and middle drums turned."

By the end of 1932, Rejewski uncovered the secret of the wiring for all three rotors and reflector. The final details were resolved using sample messages from an Enigma manual, which provided both plaintext and corresponding ciphertext along with daily key and message key.

In 1980, Rejewski affirmed that there was indeed another method that could have been used to resolve the matter, but that the technique was "imperfect and tedious" and dependent on a certain degree of chance. He acknowledged that the intelligence material in his possession led him to resolve the mystery of the Enigma machine. The British could not accomplish this until the Poles showed them how to do it.

The following is a summary of inventions created by the remarkable Polish code-breakers. Though some British sources acknowledge and give credit to the Poles for having broken the Enigma Code, they have not done enough to reveal the true extent of the Polish contribution. Far too often British documentaries and periodicals mention the Polish contribution only very briefly and casually, if at all.

What the Poles did for Britain, and for the Allied war effort
merits our deepest respect.

 MARIAN REJEWSKI

JERZY ROZYCKI

 
HENRYK ZYGALSKI


THE GRILL METHOD

The Grill Method was used by the Polish mathematicians, before the advent of the Cyclometer, in decrypting Enigma messages. It had been described by Marian Rejewski as being "manual and tedious" and, like the later Cryptologic Bomb, as being "based... on the fact that the plug connections [in the Enigma's commutator, or "plugboard"] did not change all the letters." Unlike the bomb, however, "the grill method required unchanged pairs of letters [rather than] only unchanged letters."

However in December 1938 the Grill Method proved quite successful in working out the internal wiring of two Enigma rotors that had just been introduced by the Germans. ( Even though the Germans had introduced the new drums, version IV and V, they continued to use the old system for encrypting the individual message keys.)

THE CYCLOMETER

The Cyclometer was designed,by Rejewski "probably in 1934 or 1935," to facilitate decryption of German Enigma ciphertext. It was used to prepare a catalog listing the length and number of cycles in the "characteristics" for all 17,576 positions of the rotors for a given sequence of rotors.

Since there were six such possible sequences,the resulting "catalog of characteristics," or "card catalog," comprised a total of (6) (17,576) = 105,456 entries.

Diagram of Rejewski's Cyclometer

In Rejewski's articles he noted that the utility of the card catalog was independent of the number of plug connections being used on the Enigma machines (and of the reconstruction of message keys).

Preparation of the catalog "was laborious and took over a year, but when it was ready... daily keys [could be obtained] within about fifteen minutes."

But on November 1, 1937 the Germans changed the "reversing drum," or "reflector" which meant that the Cipher Bureau had to start all over again and produce a new card catalogue but the second time around was somewhat easier, taking less than a year to complete.

On September 15, 1938, the Germans implemented a drastic change to the entire procedure for enciphering message keys. As a result, the card-catalog method became completely useless. It did however spur the inventions of Rejewski's Cryptologic Bomb and Zygalski's Perforated Sheets.

BOMBA

Each Enigma machine was reset by its operator every day using a different trigram key, for example, FED, which determined the way the machine was to be set up before use: the rotor order, which rotors to install, which ring setting for each rotor, the initial setting for each rotor and the settings on the stecker plugboard. The operator would then select a trigram for each message, say, "BGK" which would be typed twice and encrypted using the daily key. Then the message would be typed using the same key.

British Intelligence considered it virtually impossible to decrypt Enigma messages because its configuration changed each time a key was pressed -  the letters "BGKBGK" could be encrypted in endless number of ways, such as "NITUPV", or perhaps "XBLEWZ", and so on.

Though the Germans considered their encryption procedure invincible, it was prone to errors. When Marian Rejewski discovered that the first letters of a message were actually the same as the second three, he was able to determine the internal wirings of the Enigma machine and thus reconstruct the device. It was easy to determine the general traits of the machine from examining the commercial model of the Enigma however the military versions were markedly different and presented an entirely new set of problems to resolve. It was becoming an increasingly difficult task decrypt Enigma messages due to the increasing frequency with which changes were made to the complexity of the machine, its keying procedures and more particularly the existence of thousands of keys to choose from.

In order to mechanize and speed up the process of decryption, Rejewski invented the "Bomba Kryptologiczna" (Cryptologic Bomb), in October 1938. Each Bomb constituted an electrically-powered aggregate of six Enigmas and took the place of some one hundred workers. Six of the units had been built in Warsaw for the Cipher Bureau before the outbreak of World War II.

Bomba Device decrypted Enigma messages: Invented by Marian Rejewski

The Bomb Method was based on the fact that the plug connections did not change all the letters. (much like the Poles' earlier "grill" method). While the Grill Method required unchanged pairs of letters, the Bomb Method required only unchanged letters therefore it could be applied even though the number of plug connections in this period was between five and eight. By mid-November 1938 the Bombs were ready, and the reconstruction of daily keys now took only about two hours.

However, on January 1st, 1939, the Germans increased the number of plug connections from seven to ten, thereby drastically reducing the effectiveness of Rejewskis Bombs. Just weeks earlier, the Germans had increased the number of rotors from three to five. This resulted in a tenfold increase in the Bomb's workload. It may have been possible to build an additional 54 Bombs thereby increasing their output to 60 from the initial, however, the prospect would have overwhelmed the budgetary confines of the Polish Cipher Bureau.

Diagram of a few possible Enigma connections using three rotors and reflector

For the duration of the War, the British Bombe became the main tool that would be used to break Enigma messages.  It was named after and indeed inspired by the Polish Bombe, invented by Marian Rejewskiwould be named after, and likely inspired by, the Polish bomb, though according to Gordon Welchman the cryptanalytic methods embodied by the two machines were different.

Up until July 25, 1939, the Poles had been successfully breaking Enigma messages for over six and a half years without telling their French and British allies. But on December 15, 1938, the Germans added two new rotors, IV and V which greatly increased the complexity of their encryptions. Many years after the end of WWII Rejewski wrote about it: (Remarks on Appendix 1, volume 1 (1979) British Intelligence in the Second World War" by F.H. Hinsley, page 80)

"we quickly found the [wirings] within the [new rotors], but [their] introduction [...] raised the number of possible sequences of drums from 6 to 60 [...] and hence also raised tenfold the work of finding the keys. Thus the change was not qualitative but quantitative. We would have had to markedly increase the personnel to operate the bombs, to produce the perforated sheets (60 series of 26 sheets each were now needed, whereas up to the meeting on July 25, 1939, we had only two such series ready) and to manipulate the sheets."

Hinsley, of British Intelligence, had speculated "that the Poles decided to share their Enigma-breaking techniques and equipment with the French and British in July 1939 because they had encountered insuperable technical difficulties". This was a preposterous notion on his part and  to which Rejewski responded:

"No, it was not [cryptologic] difficulties [...] that prompted us to work with the British and French, but only the deteriorating political situation. If we had had no difficulties at all we would still, or even the more so, have shared our achievements with our allies as our contribution to the struggle against Germany."

Barely a month after having given Polish Enigmas to the French and British, Germany invaded Poland on September 1, 1939.

World War II Mind of a Code Breaker 3/12 (00:10:01m)

 

Editors Note:  Reference was made in this video about "Jeffrey's Sheets" (4:47) however the narrator makes no mention that years earlier, Polish mathematician, Henryk Zygalski had already invented these perforated sheets which had been used to decrypt Enigma messages long before the "so-called"  Jeffrey Sheets.


ZYGALSKI SHEETS

This method was invented by Henryk Zygalski in October 1938 and used to decrypt messages enciphered on the Enigma. The device was comprised of 26 perforated sheets for each of the six possible sequences for inserting the three rotors into the Enigma machine's scrambler. (Later the sequence increased due to the implementation of additional rotors.)

Each sheet related to the starting position of the left (slowest-moving) rotor. The 26 × 26 matrix represented the 676 possible starting positions of the middle and left rotors and was duplicated horizontally and vertically: a–z, a–y. The sheets were punched with holes in the positions that would allow a "female" to occur.

ZYGALSKI SHEETS


Rejewski wrote about how these perforated-sheets were utilized:
When the sheets were superposed and moved in the proper sequence and the proper manner with respect to each other, in accordance with a strictly defined program, the number of visible apertures gradually decreased. And, if a sufficient quantity of data was available, there finally remained a single aperture, probably corresponding to the right case, that is, to the solution. From the position of the aperture one could calculate the order of the rotors, the setting of their rings, and, by comparing the letters of the cipher keys with the letters in the machine, likewise permutation S; in other words, the entire cipher key.
Like Rejewski's "card-catalog" method, developed using his "Cyclometer," the Zygalski-Sheet procedure was independent of the number of plugboard plug connections in the Enigma Machine.

CLOCK

The "Clock" was a method devised by Polish mathematician-cryptologist Jerzy Rozycki at the Polish General Staff's Cipher Bureau, to facilitate decrypting German Enigma ciphers. His method made it possible to determine which of the Enigma machine's rotors was at the far right - in other words, to identify which rotor always revolved at every depression of a key.


Polish Mathematicians-Cryptologists
L-R: Henryk Zygalski, Jerzy Rozycki, Marian Rejewski
(Cadix, between September 1940 and July 1941)

After the invasion of Poland in September 1939, the work of Enigma decryption became the exclusive domain of British and American Intelligence.  Rejewski and Zygalski were now excluded from the inner sanctum of Bletchley Park. According to British code-breaker Alan Stripp, very few people were aware of the Polish contribution because British Intelligence operations were held to a strict secrecy and "need to know" basis.

Stripp commented that "setting them to work on the Doppelkassetten system was like using the racehorses to pull wagons".

Gordon Welchman, who became head of Hut 6 at Bletchley Park, wrote:
Hut 6 Ultra would never have gotten off the ground if we had not learned from the Poles, in the nick of time, the details both of the German military version of the commercial Enigma machine, and of the operating procedures that were in use.
Welchman, Gordon (1984) [1982], The Hut Six story: Breaking the Enigma codes, Harmondsworth, England: Penguin Books, ISBN 0 14 00.5305 0  page 71

Marian Rejewski, Jerzy Rozycki and Henryk Zygalski have been celebrated throughout the world.  Rejewski had been decorated with numerous Polish medals before and after World War II. In 2000, they were posthumously awarded the Grand Cross of the Order of the Rebirth of Poland.

And on July 4, 2005,  the 1939-1945 War Medal was awarded posthumously by the British Chief of Defense Staff,, and received by Rejewski's daughter.

In 2002, a plaque was unveiled at Bletchley Park. The English side reads as follows:

This plaque commemorates the work of Marian Rejewski, 
Jerzy Różycki and Henryk Żygalski, mathematicians of the
Polish intelligence service, in first breaking the Enigma code. Their work greatly assisted the Bletchley Park code breakers
and contributed to the 
Allied victory in World War II

Bletchley Park - Plaque honoring the Polish Code-Breakers


After half a century of silence, the British have finally
honoured the Polish Code Breakers
for their contributions to the Allied war effort.



Flag of Polish Home Army (Armia Krajowa)



NEXT:




N.B. Sources and References will be provided at the completion of this special series.

1 comment:

Mike R said...

It is wonderful to see a tribute to those who played such a key role in breaking the Enigma. Thanks!

Post a Comment