Editorial introduction:
Historians agree that Polish mathematicians' contribution to breaking the codes of Enigma, the German coding machine, was crucial. It saved millions of lives, including American soldiers fighting in the Atlantic, North Africa, and Europe against the Nazis. We present our readers with a paper about the efforts to break the codes of Enigma. This publication is an excerpt of Mark Litak's undergraduate work at the University of Minnesota. This is not intended to be another historical work on this subject; instead, it is a presentation of a mathematician's point of view.
Creating the Enigma
In classical cryptography, ciphers are created using an algorithm that replaces one letter with another or one symbol with another. These ciphers are vulnerable to many different types of attacks, most notably frequency analysis, which analyzes the frequency of each letter in a message and compares it to the frequency of letters in the particular language the message was encoded in. Such ciphers are known as monoalphabetic ciphers, also known as substitution ciphers, as they simply rearrange the alphabet, substituting one letter for another. In other words, each letter in the plaintext (the text that is being encrypted) corresponds to only a single letter in the ciphertext (the encrypted text).
A breakthrough in cryptography came with the invention of polyalphabetic ciphers, where one letter in the plaintext might correspond to multiple letters in the ciphertext in some systematic way. Each letter in the plaintext had its own “alphabet,” or substitution cipher. The most famous polyalphabetic cipher is the Vigenère cipher, where a “key” is chosen, often a word, for a message; the length of this key is known as the cipher period. Each letter in the message is matched with one of the letters in the key, then the “values” of the letters are added together to make a new letter.
The Vigenère cipher, known for centuries as “le chiffre indéchiffrable,” or “indecipherable cipher,” was broken in 1863 with the Kasiski attack, which can guess cipher period, and again in 1925 by the Friedman attack, which could both make an educated guess as to the cipher period and make a reasonable guess as to what the key was. Both of these relied upon the fact that the cipher period was usually short and repeated itself within the message. It seemed, then, that the main weakness of polyalphabetic ciphers was the length of the key. So, a cipher with an extraordinarily long cipher period would truly be the most secure.
ENTER THE ENIGMA
The Enigma Machine
The Enigma is a rotor-based cipher machine that solves the problem of a short key length. The first rotor-based cipher machines were invented in 1915 by two Dutch naval officers, Theo van Hengel (1875-1939) and Rudolf Pieter Cornelis Spengler (1875-1955). However, a German electrical engineer Arthur Scherbius (1878-1929), popularized the concept with the Enigma, which he patented in Germany in 1918 and the United States in 1928.
The main encryption of the Enigma mechanism was two-fold: a set of three rotors that each rearranged the alphabet like a monoalphabetic cipher and a plugboard that exchanged letters with each other. When a key was pressed, the current would flow to the plugboard, then through the rotor mechanism, then through the plugboard once more, until finally lighting one of 26 lamps that corresponded with each letter of the alphabet. The operator would then write down which lamp was lit up, and the sequence of lamps that were lit became the ciphertext. The biggest portion of what made the Enigma so secure was that when each letter was typed, the rightmost rotor would turn, creating an entirely new alphabet for each keypress. Besides, due to a portion of the Enigma called the reflector, entering the ciphertext with the same initial Enigma settings allowed the operator to input the ciphertext and get the plaintext.
Each of these rotors could be taken out of the Enigma and interchanged with each other. During the war, there were five rotors, out of which three would be chosen. They could also be rotated so that the initial substitution cipher could be different, even if all of the rotors used were the same and in the same order. The plugboard could also be rearranged manually. The way that the rotors and plugboard were set up is known as the Enigma setting.
Every one of these security measures resulted in a cipher that, on paper, was nigh unbreakable. The cipher period was 16,900—far too long to be vulnerable to either the Kasiski or Friedman attacks. The number of possible ways to encrypt ciphertext was 655,742,361,353,332,664,320 ≈ 269.15. This led to a lot of confidence in the Enigma’s abilities to consistently encrypt anything in an unbreakable way, and this overconfidence led to its ultimate downfall.
CRACKING THE ENIGMA
Polish Breakthrough
Polish intelligence had been intercepting encrypted German military messages for years. However, in 1928, standard cryptologic attacks had stopped working. They realized that the Germans had begun using machine encryption. The Polish government acquired a commercial Enigma machine for analysis. Still, this analysis ended up not actually being very useful, as the Germans had made many changes to the machine their military used. The interior wiring of each of the rotors was different, and the commercial Enigma did not have a plugboard at the front. To move further with breaking the codes of Enigma, the Cipher Bureau (Biuro Szyfrów) recruited three young mathematicians from Poznań: Marian Rejewski (1905-1980), Henryk Zygalski (1908-1978), and Jerzy Różycki (1909-1942).
In 1931, the French intelligence obtained the Enigma setting for the next few months and a book of instructions on how to encrypt each message through a German spy named Hans-Thilo Schmidt (1888-1942). Shortly after, Biuro Szyfrów obtained the Enigma settings for the next few months and a book of instructions for how to encrypt each message from the French.
Using only the information provided to them by the French, along with intercepted messages, Rejewski was able to use permutation theory to determine the way each of the rotors was wired, as, at that point, only three rotors were being used. This was momentous, especially that he was able to do so with so little information. Also, he was able to determine a method for decrypting each message, which relied on a major weakness in the German Enigma operating procedure.
When a message was sent, the sending operator would set their Enigma setting to the settings given for that particular day. Then, the operator would choose three new rotor settings, and transmit them twice, then change the rotor settings to the new ones they had chosen, and continue the rest of the message with the new settings. This meant that the first and fourth letters, second and fifth, and third and sixth letters would all be the same at the beginning of each message. Rejewski would be able to reconstruct the Enigma setting of the day, once again using permutation theory. Rejewski designed the first “bomba,” a precursor to the Bombes used in Bletchley Park, which was essentially a set of six Enigmas wired together. Biuro Szyfrów was usually able to find the Enigma settings within two hours. By 1938, Poles could decrypt 75% of intercepted messages.
However, in 1938, the Germans added two new rotors that were able to be used within the Enigma. Rejewski was able to determine the wiring as he did earlier. Still, he could not design a machine that would determine the rotor settings, as the Biuro Szyfrów did not have enough human resources and funds to create new “bomba.” Due to the expense, as well as the looming threat of war, the Polish gave away their cryptanalytic secrets, including designs for the “bomba” and the reconstructed rotors, to the French and British in a meeting in Pyry near Warsaw in July 1939. After the meeting, the Biuro Szyfrów destroyed all of their documents. Once the German-Soviet forces attacked Poland in September 1939, the mathematicians moved to France in order to avoid being captured.
British Further Developments
With the information given to them by the Polish, the British set up a shop in Bletchley Park. Alan Turing (1912-1954) was a prominent mathematician who worked on the Enigma-breaking machine's design, the Bombe, which exploited a major flaw of the Enigma. This flaw is an inherent result of the reflector.
The reflector allowed enciphered text to be deciphered by simply using the same Enigma settings. Due to this reflector, no letter could be encrypted onto itself. Plaintext could be matched to where it was believed to be in the text, and rotor settings that potentially matched each known-plaintext were discovered using the Bombe, a machine of Turing’s design, based on the Polish “bomba.” The Bombe was a series of interconnected Enigmas and manually checked each of the rotor settings to see if any would match the plaintext-to-ciphertext encryption. This would take around an hour.
Crucially, this method was completely independent of any known German operating procedure. If the Germans had changed the procedure for beginning a message, and they did in 1940, the Polish method would not have worked. However, Turing’s method for determining rotor settings did work independent of any procedural changes and exploited a flaw in the design of the Enigma itself. Turing built on the work done by Rejewski and made a crucial change that would have cracked the Enigma no matter what the Germans decided about their operating procedures.
In addition to creating the Bombe, Turing determined the German navy's Enigma operating procedure, which was significantly different from the standard procedure, especially since the naval Enigmas were different. Additionally, he determined a statistical procedure for making better use of the Bombe, which was so crucial to wartime and post-war codebreaking that it was only released to the public in 2012. Turing’s contributions to cracking the Enigma are very significant and should absolutely never be discounted.
Final remarks
Turing himself credited the Polish with cracking the Enigma, which allowed him to crack it, only better. The Enigma's secrets were given to them to ensure the safety of the Polish mathematicians and the safety of the secret that the Enigma had been broken; also, due to limited funds, the Polish Cipher Bureau could not make any more steps forward with the Enigma machine.
In addition, the method of decryption that the British determined was far stronger than the method that the Polish determined. The Polish method involved a weakness in operating procedure, which was changed. This would have crippled the Polish system; the British system of decryption was able to handle it.
Rejewski is not credited nearly as much as Turing. This ought to be remedied, as his brilliant deduction of rotor wiring and Enigma settings using permutation theory was truly inspired. However, Turing’s accomplishments should not be minimized either. His method significantly improved the Polish method, and this, in and of itself, deserves recognition. Breaking the Enigma code was a cumulative effort of (alphabetically) British, French, and Polish mathematicians and military intelligence. It shortened the duration of the war and saved millions of lives.
Recommended reading:
Azad, Saiful, and Al-Sakib Khan Pathan. "Practical Cryptography: Algorithms and Implementations Using C++." Auerbach Press, 2015.
"Cryptography." https://stanford.edu/class/archive/cs/cs106a/cs106a.1164/handouts/29A-
CryptographyChapter.pdf
Accessed on Jan 31, 2021
Christensen, Chris. "Polish Mathematicians Finding Patterns in Enigma Messages." Mathematics Magazine, vol. 80, no. 4, 2007, pp. 247-273, DOI:
10.1080/0025570X.2007.11953492.
Casselman, Bill. "Marian Rejewski and the First Break into Enigma." Feature Column American Mathematical Society, November 2009
Accessed on Jan 31, 2021
Crypto Museum, History of the Enigma. The rotor-based cipher machines
Accessed on Jan 31, 2021
Gene F. Pfeffer "The Codebreakers' War in the Atlantic"
Accessed on Jan 31, 2021
Photograph of the Enigma machine at World War II Gallery, the National Museum of the United States Air Force. Dayton, Ohio.
Accessed on Jan 31, 2021
Films online:
"The Battle to Crack Enigma"
"Sekret Enigmy" (1979). Movie in Polish only
All photographs: wikipedia.org