Polish Contributions to Computing
Marian Rejewski [pron. MAHR-yahn re-YEV-ski] was born on August 16, 1905, in Bydgoszcz, Poland (then Bromberg, Prussia/Germany) and died on February 13, 1980 in Warsaw. He studied mathematics at Poznan University and graduated with a master’s degree in 1929. After graduation, he spent a year in Göttingen, Germany, studying actuarial mathematics, and returned to Poznan to take a lectureship in mathematics at the University. At the same time, he began working for the Polish Cipher Bureau where he became permanently employed in 1932, working on a team breaking the German Enigma code. During the World War II, he continued work on breaking codes for the Allies, in France and Britain. He returned to Poland in 1946, but did not continue his work in cryptography and worked as a clerk until his retirement in 1967.

Major Contribution: Breaking the German Enigma cipher in 1932-33, with Jerzy Rózycki and Henryk Zygalski [1-4].

Basic Questions
What is the Enigma cipher? Enigma was a German ciphering machine used before and during World War II for coding commercial and military messages. The ciphering method is pretty elaborate, although described well in details in multiple publications by Rejewski himself [2-4] and others [5-8]. A succinct description of Enigma has been recently given by J. Copeland [9]. Briefly speaking, the encryption process relies on automatic encoding sequences of letters entered from the keyboard (of 26 letters, A through Z), by the arrangement of three rotating drums (rotors) and one reflecting drum that convert each letter according to a pre-assumed secret rule (which can be changed). When a message thus encoded is delivered to the recipient, Enigma deciphers it and produces the plain text, as typed in by the sender, provided that both machines were synchronized to the same settings. Multiple simulators imitating Enigma’s operation are available on-line, including one on this page under the Resources button. The cryptographic power of Enigma cipher is best illustrated by the number of possible Enigma configurations. A.R. Miller [10] discusses this issue in a very straightforward manner, attributing the number of combinations to the following five variable components of Enigma:
  • a plugboard which could contain up to thirteen dual-wire cables to connect pairs of letters
  • three ordered rotors which wired twenty six input points to twenty six output points
  • twenty six serrations which allow the operator to specify initial positions of the rotors
  • a movable ring on each of the rotors which controls their behavior by means of a notch
  • a reflector rotor to fold inputs and outputs back.
Miller’s calculations lead to an incredible number of the order of 10^114 (yes, ten to the power of one hundred fourteen) combinations, which is many orders of magnitudes higher than the estimated number of atoms in an observable universe!
How, then, could the Enigma code be broken (the encoding rule uncovered)? Theoretically, this is next to impossible. However, Marian Rejewski describes the process of how he and his coworkers came up with the solution that ultimately led them to breaking the Enigma code [2-4]. The essential notion to understand it is the mathematical term permutation, which means “changing an arrangement of elements in a sequence”. Thus, Rejewski and his team were tasked with finding the rule, which Enigma used to govern rearranging permutations of letters in the original text to produce the enciphered text, and vice versa. Two things were essential in this process: formulating mathematical equations which described the generation of permutations, and, using some additional intelligence information, solving them by a very laborious computational process. The equations Rejewski formulated involved all the components of the machine participating in the transformation of the initial text into an enciphered text. In Rejewski’s terms, equations (six of them for a known message header) had the following form:
A = SHPNP^(-1)MLRL^(-1)M^(-1)PN^(-1)P^(-1)H^(-1)S^(-1)
where A means a known header permutation (which was obtained by intelligence), S – the permutation produced by the switchboard, and H, L, N, M, R – permutations from all the drums. With a lot of guessing, deductive reasoning, and some preset configurations delivered by the French intelligence, Rejewski was able to break the Enigma code, but as he states in his papers, “To this day it is not known whether equations are solvable” [2].

Significance
Breaking the Enigma cipher is considered by some to be one of the two most critical scientific events leading to the end of World War II – the other one being the development of an atomic bomb. The extraordinary contribution of Rejewski and his colleagues has been independently confirmed by many authors in books and papers. For example, an American historian, D. Kahn, describes it as follows: ”The solution was Rejewski's own stunning achievement, one that elevates him to the pantheon of the greatest cryptanalysts of all time” [6]. Since the special issue of Cryptologia appeared in 1982 [11-12], reprinted next in a book [13], to this day papers are being published on the Rejewski’s role in deciphering Enigma [14-15]. However, the destruction of the Polish Cipher Bureau at the beginning of war, displacements of the crew, certain political decisions of the Allies, and the need for a significant computational power, due to constant changes made in Enigma by the Germans, led to the discontinuation of work by Rejewski. In the meantime, another great figure in decrypting the Enigma cipher, Alan Turing, emerged. One can read a balanced account on the role of both men in deciphering Enigma, in an article by J. Copeland [9], and especially on Turing in [16].

Findings
The historical contribution of this website is in bringing together important pieces of information on Marian Rejewski. They have been known individually for some time, since the history of Enigma and breaking its cipher is very well researched, but never before has a single source been created that collects all this information and presents it for viewing, with links to the original material.

References [show]

[1] T. Lisicki, Die Leistung des polnisches Entzifferungsdienstes bei der Lösung des Verfahrens der deutschen Enigma-Funkschlüsselmaschine, Die Funkaufklärung und ihre Rolle im Zweiten Welkrieg, J. Rohwer, E. Jäckel (Eds.), Motorbuch Verlag, Stuttgart, 1979, s. 66-83.
[2] M. Rejewski, An Application of the Theory of Permutations in Breaking the Enigma Cipher, Applicationes Mathematicae, Vol. 16, No. 4, pp. 543-559, 1980
[3] M. Rejewski, How Polish Mathematicians Deciphered Enigma, IEEE Annals of the History of Computing, Vol. 3, No. 3, pp. 213-234, July 1981
[4] M. Rejewski, Mathematical Solution of the Enigma Cipher, Cryptologia, Vol. 6, No. 1, pp. 1-18, January 1982 (Reprinted in [13], pp. 310-327)
[5] W. Kozaczuk, Enigma: How the Poles Broke the Nazi Code, Hippocrene Books, New York, 2004
[6] D. Kahn, The Code-Breakers, Macmillan, New York, 1967 (Expanded Edition, 1996)
[7] G. Bertrand, Enigma ou la plu grande enigme de la guerre 1939-1945, Librairie Plon, Paris, 1973
[8] F.L. Bauer, Decrypted Secrets: Methods and Maxims of Cryptology. 2nd Edition, Springer-Verlag, Berlin, 2000
[9] J. Copeland (Ed.), The Essential Turing, Clarendon Press, Oxford, 2004. Chapter 4: Enigma. http://www.phil.canterbury.ac.nz/personal_pages/jack_copeland/pub/etsamp.pdf
[10] A.R. Miller, The Cryptographic Mathematics of Enigma, National Security Agency, Ft. Meade, Maryland, 2006
[11] Ch. Kasperek, R. Woytak, In Memoriam: Marian Rejewski, Cryptologia, Vol. 6, No. 1, pp. 19-25, January 1982 (Reprinted in [13], pp. 15-21)
[12] R. Woytak, A Conversation with Marian Rejewski, Cryptologia, Vol. 6, No. 1, pp. 50-60, January 1982 (Reprinted in [13], pp. 4-14)
[13] C.A. Deavours et al. (Eds.), Cryptology: Machines, History and Methods, Artech House, Norwood, Mass., 1989
[14] F.L. Bauer, Marian Rejewski und die Alliierten im Angriff gegen die Enigma, Informatik Spektrum, Vol. 23, No. 5, pp. 325-333, October 2000
[15] F.L. Bauer, Mathematik besiegte in Polen die unvernuenftig gebrauchte Enigma, Informatik Spektrum, Vol. 28, No. 6, pp. 493-497, December 2005 (Part 1), and Vol. 29, No. 1, pp. 53-60, February 2006 (Part 2)
[16] J. Copeland, Colossus: The Secrets of Bletchley Park's Code-Breaking Computers, Oxford University Press, New York, 2006

Copyright 2006. All rights reserved. W3C XHTML Compliant Valid XHTML 1.0 Transitional