Marian Rejewski

From Example Problems
Jump to navigation Jump to search
File:MR 1932 small.jpg
Marian Rejewski (probably 1932).
Courtesy of Janina Sylwestrzak, Rejewski's daughter.

Marian Adam Rejewski (Template:IPAudio; 19051980) was a Polish mathematician and cryptologist, famous for his ground-breaking, long-running work in decrypting German Enigma ciphers. His achievements jump-started British reading of Enigma in World War II ("ULTRA"). The intelligence so gained substantially altered the course of the war, and the use of ULTRA intelligence may have hastened the defeat of Germany by as much as two years.

Education and codebreaking in Poland

Template:Cipher Bureau

File:Dyplom Rejewskiego.jpg
Rejewski's Master of Philosophy diploma, Poznań University, March 1, 1929.

Born August 16, 1905 in Bydgoszcz, Poland, Rejewski was a mathematics graduate of Poznań University who, as a student, had attended a cryptology course organized there for selected mathematics students by the Polish General Staff's Cipher Bureau. As a postgraduate student he studied actuarial statistics for a year at Göttingen, Germany. Returning to Poland, he taught mathematics for two years at Poznań University. On September 1, 1932, as a civilian employee, he joined the Cipher Bureau (Polish: Biuro Szyfrów) of Polish Military Intelligence at the General Staff building (the Saxon Palace) in Warsaw. Shortly thereafter, he was asked to study ways of attacking the German Army's Enigma cipher machine, which had come into service in 1930.

Solution of the Enigma wiring

In his work on Enigma, Rejewski pioneered the use of pure mathematics in cryptanalysis. Previous methods had exploited linguistic patterns and statistics in natural language texts: for example, letter-frequency analysis. Rejewski, however, applied techniques from group theory — theorems about permutations — in his attack on the Enigma cipher. These mathematical techniques, combined with material supplied by French military intelligence, enabled him to reconstruct the internal wirings of the machine's rotors and non-rotating reflector. "The solution," historian David Kahn writes, "was Rejewski's own stunning achievement, one that elevates him to the pantheon of the greatest cryptanalysts of all time." (Kahn, The Codebreakers, revised ed., p. 974). Rejewski used a mathematical theorem that wartime Bletchley Park luminary, Professor I. J. Good, has described as "the mathematical theorem that won World War II."[1]

Rejewski first studied the set of "indicators" received with the Enigma messages intercepted on a single day. Each indicator was a six-letter sequence which encoded the Enigma rotor starting position to be used to encipher the actual message. An operator would construct the indicator by selecting three letters at random, representing the rotor start position, and encipher them twice on the Enigma using a global setting. The double encipherment of the indicator was meant to act as an error check to detect garbles, but it also had the unforeseen effect of greatly weakening the system.

Rejewski studied the cycles formed by the first and fourth letters of each indicators, and similarly, the cycles formed by the second and fifth, and the third and sixth. Assisted by the Enigma operators' habits of choosing highly non-random indicators, Rejewski was able to deduce six permutations corresponding to the encipherment at six consecutive positions of the Enigma machine. These permutations could be described by six equations with various unknowns, including the wiring of the rotors, the reflector, the plugboard, and the entry wheel.

At this point, Rejewski ran into difficulty; the large number of unknowns made the equations complex. He would later comment in 1980 that it was still not known whether such a set of six equations is solvable without further data. In the event, he was assisted by cipher documents obtained by French Intelligence, and which had been passed on to the Polish Cipher Bureau. The documents had originally been procured by a German traitor, Hans-Thilo Schmidt, and included the Enigma key settings for the months of September and October 1932. These were given to Rejewski on the 9th or 10th of December 1932, who used them to eliminate the effect of the plugboard from the equations. With the reduced number of unknowns, solving the equations became a tractable problem.

First another snag needed to be overcome. The military Enigma had been modified from the commercial Enigma (with which Rejewski was familiar) in the wiring to the entry wheel. In the commercial machine, the keys were connected to the entry wheel in keyboard order ("QWERTZU..."). However, in the military Enigma, the connections had been wired in alphabetical order instead: "ABCDEF...". This small change had completely foiled the British attempts at solving Enigma, who had dismissed the "ABCDEF..." wiring as being too obvious. Rejewski, possibly guided by an intuition about a German fondness for order, simply guessed that the wiring was the normal alphabet ordering. He later wrote that, after having made this assumption, "from my pencil, as by magic, began to issue numbers designating the connections in drum N. Thus the connections in one drum, the right-hand drum, were finally known."[2].

Rejewski's technique enabled him to readily find the wiring of the right-hand rotor in the machine. He was further aided by the fact that the settings provided by French Intelligence covered two months which straddled a changeover period for the rotor ordering. A different rotor happened to be in the right-hand position for the second month, and so the wiring of two rotors were easily recovered. This simplified the analysis, and, by the end of the year, the wiring of all three rotors and the reflector had been solved.

It has been speculated whether the rotor wirings could have been solved without the documents supplied to the Polish Cipher Bureau by French intelligence. Another way was found that could have been used to achieve this, but the method was "imperfect and tedious," and relied to a large extent on chance. Lawrence (2005) argues that it would have taken four years for this method to have had a reasonable likelihood of success. Rejewski writes that "the conclusion is that the intelligence material furnished to us should be regarded as having been decisive to solution of the machine."[3]

Methods for solving the daily Enigma settings

File:Cyclometer machine Drawing from M Rejewski’s papers.jpg
Cyclometer (1934). Diagram from Marian Rejewski’s papers. 1: Rotor lid closed. 2: Rotor lid open. 3: Rheostat. 4: Glowlamps. 5: Switches. 6: Letters.

After Rejewski had determined the wiring in the remaining drums, he and fellow mathematician-cryptologists Jerzy Różycki and Henryk Zygalski devised methods and equipment to routinely break Enigma ciphers. Rejewski writes,

[Now] we had the machine, but... we didn't have the keys [and] we couldn't very well require... Bertrand to keep on supplying us with the keys every month. Supposely he did supply [further keys] but I never got any more. The situation had reversed itself: before, we'd had the keys but we hadn't had the machine — we solved the machine; now we had the machine [but] we didn't have the keys. We had to work out methods to find the daily keys... Within a short time we had found... several methods [particularly] the grill [and] the cyclometer... The cyclometer method especially was very important; ...it required a lot of preparation but, after that, finding the keys would take ten to twenty minutes...

The earliest method for reconstructing daily keys was the "grill," based on the fact that the commutator's ("plugboard's") plug connections exchanged only six pairs of letters, leaving fourteen letters unchanged.[4] Next was Różycki's "clock" method, which sometimes made it possible to determine which rotor was in the N rotor's position, that is, at the right-hand side of the Enigma machine, on a given day.[5] That was followed by Rejewski's "cyclometer," basically comprising two sets of Enigma rotors, which permitted the determination of the length and number of cycles in the "characteristics" for all 17,576 positions of the rotors for a given sequence of rotors (there being 6 such possible sequences, the resultant card catalog of characteristics encompassed 105,456 entries). This method's utility was independent of the number of plug connections in the commutator (and of the reconstruction of message keys). The catalog's preparation took over a year, but when it was ready, it made obtaining daily keys a matter of 10-20 minutes.[6] In January 1938, B.S.-4 (the Cipher Bureau's German section) was reading a remarkable 75% of Enigma intercepts; according to Rejewski, with only a minimal increase in personnel, this could easily have been increased to 90% (there was always some residue of garbled messages).

On September 15, 1938, new rules for enciphering message keys were put into effect in all German formations except for the S.D., necessitating a search for new ways of finding the keys. The cyclometer and card catalog were followed, at that stage in the evolution of German Enigma cryptography, by Rejewski's "bomb" (Polish: bomba), essentially an electrically powered aggregate of six Enigmas, which shortened the time needed to reconstruct daily keys to about two hours.[7] At about that same time, Zygalski invented a manual method, that of "perforated sheets" ("Zygalski sheets"), which, like the "card-catalog" method, was independent of the number of plug connections in the commutator; when the sheets were superposed and moved in the proper manner with respect to each other, the number of visible apertures gradually decreased, and if enough data were available there finally remained a single aperture (in English called a "female," a literal translation of the Polish play-on-words, "samiczka," perhaps more properly translated as "singleton"), probably corresponding to the solution.[8]

Details of the Polish achievements were revealed to British and French intelligence representatives in a meeting at a secret Polish Cipher Bureau facility at Pyry, in the Kabaty Woods south of Warsaw, on July 25, 1939. The Germans had made changes to Enigma equipment and procedures in 1938 and 1939 that increased the difficulty of breaking messages; and as it became clear that war was imminent and Polish resources would not suffice to optimally keep pace with the evolution of Enigma encryption, the Polish General Staff and government had decided to bring their western allies into the secret. With the crucial Polish contribution of reconstructed sight-unseen German Enigma machines and the Poles' cryptological techniques and equipment, the British at Bletchley Park, and later the Americans, were able to continue the work of breaking German Army, Air Force, Nazi Party SD, and (though with substantially greater difficulty) Naval Enigma traffic.

The Poles' gift, to their western Allies, of Enigma decryption, a month before the outbreak of World War II, came not a moment too soon. Former Bletchley Park cryptologist Gordon Welchman has written: "Ultra [the British Enigma-decryption operation] 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... Enigma machine, and of the operating procedures that were in use."[9]

File:Marian Rejewski.jpg
Marian Rejewski as second lieutenant (signals), Polish Army in Britain, in late 1943 or in 1944, some 11 or 12 years after his first break into Enigma.

Work in France and Britain

In September 1939, after the outbreak of World War II, Rejewski and his fellow Cipher Bureau workers were evacuated from Poland via Romania to France. At "PC Bruno," outside Paris, they continued their work at breaking Enigma ciphers, collaborating by teletype with their opposite numbers at Bletchley Park, 50 miles (80 km.) north of London. According to French Air Force Captain Henri Braquenié — who had, with Bertrand, attended the historic July 25, 1939, Warsaw conference — for maximum communications security the allied Polish, French and British cryptological agencies used Enigma itself, with Braquenie closing "Bruno's" Enigma-encrypted messages to Britain with a "Heil Hitler!"[10]

When "Bruno" was evacuated upon Germany's invasion of France, the Polish cryptologists and their ancillary staff worked for two years in unoccupied southern (Vichy) France and outside of Algiers in French North Africa.

In early July 1941, Rejewski and Zygalski were asked to try solving messages enciphered on the super-secret Polish Lacida rotor cipher machine, which had never been subjected to rigorous decryption attempts. The two cryptologists created consternation by breaking the first message within a couple of hours, and further messages in like manner.

Just before the German takeover of the "Free Zone" in November 1942, the secret French-Polish "Cadix" center in southern France was evacuated. Its Polish military chiefs were captured and imprisoned by the Germans but protected the secret of Enigma decryption. Różycki, the youngest of the three mathematicians, had died in the January 1942 sinking of a French passenger ship as he was returning from a stint in Algeria to "Cadix" in southern France.

Rejewski and Zygalski fled France for Spain, where they were arrested and imprisoned for three months. Released upon the intervention of the Polish Red Cross, almost three months later, in July 1943, they made it to Portugal; from there, aboard the HMS Scottish, to Gibraltar; and thence, aboard an old Dakota, to Britain. Here Rejewski and Zygalski were inducted as privates into the Polish Army (they would eventually be promoted to lieutenant) and employed at cracking German SS and SD hand ciphers. Enigma decryption had become an exclusively British and American domain; the two mathematicians who, with their late colleague, had laid the foundations for Allied Enigma decryption and had conferred at "PC Bruno" with Alan Turing, were now excluded from the opportunity of making further contributions to their metier.

Postwar life

After the war, Zygalski remained in Britain while Rejewski took a big chance and returned to Poland in 1946 to reunite with his wife and two children. He worked as a bookkeeper at a factory—bringing disfavor on himself when he discovered irregularities—until his retirement, and was silent about his work before and during the war until, in the 1970's, he contacted the military historian Władysław Kozaczuk. He published a number of papers on his cryptologic work and contributed generously to books on the subject. A few years before his death, at the request of Wacław Jędrzejewicz, president of the Józef Piłsudski Institute of America, Rejewski broke enciphered correspondence of Józef Piłsudski and his fellow Polish Socialist conspirators from 1904. He died February 13, 1980 in Warsaw, at the age of 75.

An odd footnote to the story of Rejewski's cryptologic contributions is that his role in World War II had been so obscure that one best-selling book (William Stevenson's A Man Called Intrepid, 1976) not only did not credit him with the work he had done (repeating, instead, a variant of the cock-and-bull story about a "machine stolen from a transport truck") but identified him as "Mademoiselle Marian Rewjeski."

Posthumous recognition

Rejewski died in 1980 in Warsaw and was buried at the Powązki Cemetery, one of Poland's pantheons of the great and valiant.

The Polish Mathematical Society has honored him with a special medal.

On 4 July 2005, Rejewski was awarded a posthumous War Medal 1939-1945 by the British Chief of the Defence Staff [11].

Notes

  1. ^  I.J. Good, prefatory remarks to: Marian Rejewski...
  2. ^  Marian Rejewski, in Richard Woytak's 1978 interview, first published in Cryptologia, vol. 6, no. 1 [January 1982], reprinted in Władysław Kozaczuk's Enigma 1984, pp. 232-35.
  3. ^  Marian Rejewski, in Władysław Kozaczuk's Enigma 1984, p. 258.
  4. ^  ibid
  5. ^  ibid, p. 242.
  6. ^  ibid, p. 290.
  7. ^  ibid, pp. 242, 285-87.
  8. ^  ibid, pp. 242, 290.
  9. ^  ibid, pp. 243, 287-89.
  10. ^  Gordon Welchman, The Hut Six Story, p. 289.
  11. ^  Kozaczuk, Enigma, p. 87.

See also

References

  • Stephen Budiansky, Battle of Wits: the Complete Story of Codebreaking in World War II, New York, The Free Press, 2000.
  • Gustave Bertrand, Enigma ou la plus grande énigme de la guerre 1939–1945 (Enigma: the Greatest Enigma of the War of 1939-1945), Paris, Librairie Plon, 1973.
  • I.J. Good, afterword to: Marian Rejewski, "How Polish Mathematicians Deciphered the Enigma," Annals of the History of Computing, vol. 3, no. 3 (July 1981). This paper of Rejewski's appears as appendix D in Kozaczuk 1984.
  • Władysław Kozaczuk, Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two, edited and translated by Christopher Kasparek, Frederick, MD, University Publications of America, 1984. (The standard reference on the Polish part in the Enigma-decryption epic.)
  • John Lawrence, "A Study of Rejewski's Equations," Cryptologia 29 (3), July 2005, pp. 233–247.
  • John Lawrence, "The Versatility of Rejewksi's Method: Solving for the Wiring of the Second Rotor," Cryptologia 28 (2), April 2004, pp. 149–152.
  • Hugh Sebag-Montefiore, Enigma: the Battle for the Code, London, Weidenfeld and Nicolson, 2000.
  • Marian Rejewski, "How the Polish Mathematicians Decrypted Enigma" (in Polish), Annales Societatis Mathematicae Poloniae, Warsaw, Państwowe Wydawnictwo Naukowe, 1981. (Same paper as the preceding.)
  • Marian Rejewski, An Application of the Theory of Permutations in Breaking the Enigma Cipher. (Appears to be the same paper as appendix E in Kozaczuk 1984.)
  • "Rejewski, Marian Adam" Polski słownik biograficzny (Polish Biographical Dictionary), vol. XXXI/1, Wrocław, Wydawnictwo Polskiej Akademii Nauk (Polish Academy of Sciences), 1988, pp. 54-56.
  • Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, New York, McGraw-Hill, 1982.

External links

de:Marian Rejewski fr:Marian Rejewski he:מריאן רייבסקי lv:Marians Rejevskis nl:Marian Rejewski pl:Marian Rejewski sl:Marian Rejewski zh:马里安·雷耶夫斯基