ITP125 advantage after the war broke out.
ITP125Youyun Zhang Mechanism of Enigma machine and its decryption Enigma machine is a cypher machine that was invented byGerman during post World War I. It was very powerful in securing militarycommunication and was claimed by British as “the unbreakable machine” after afew cracking attempts.
However, assisted by some mathematicians and espionage workof Polish as well as some German soldiers’ operator mistakes, the Alliesmanaged to decrypt the message send by Germany use for Allie’s advantage afterthe war broke out. The Enigma machine looks like an oversized typewriter. Itconsists of several rotors which were just wheels that have letter by the sides,a lampboard what will light up the encoded letter after pressing the originalletter on the keyboard, and the bottom the machine has a plugboard, which hasten pairs of letters connected to each other by plugging wires. The invention of Enigma machine got the idea from thebasic theory of cryptography, substitution cipher.
One letter in, one letterout. When the original letter (plaintext) goes in, it first goes through theplugboard. On the plugboard, twenty letters are chosen to pair up to eachother, performing the first layer of substitution of two random letters out of twenty-six. Thenthe plaintext letter (or rather the electric current, but for the simplicityand my ignorance about electric engineering, the letter will be moving in thosewires instead of current in the rest of the paper) goes through the core ofEnigma machine, the rotors. A set of three rotors was commonly used. While onerotor only does a simplest thing – change a letter into a different letter andoutput the encoded letter, three rotors that are connected by wire don’t justrepeat the same thing over three times. Otherwise it’s no different than usingone rotor, since one letter could only be encrypted to a certain letter. Notadding too much work for the cryptologist.
The trick is once the first rotorhas fulfilled a cycle, the second rotor will automatically move, thereforechanges to a new configuration of next set of plaintext letters until the nextcycle is fulfilled. And when the second rotor has finished its cycle, the thirdwill also move. It’s very alike to the movement of the three hands of a clock.And to make the decipher more complex, the German later have five rotorsprepared on the side, each time before entering the plaintext, the cipher clerkwill have to pick three rotors from them.
But this was obviously not enough forthe paranoid German people, the next implementation they added was ingenious,as well as one of the most critical flaw that led to the decipher of Enigmamachine. After the letter go through the three rotors, a reflectoris waiting at the end of them. What the reflector does is that it takes theletter and substitute it with another letter again, then send it back throughthe three rotors that it comes from. The cleverness of this move is that twoimportant feature of Enigma machine was acquired from this.
First, it made theletter revisable. Because the connection between the three rotors are exactlythe same because these are standard rotors, therefore there’s only one path forthe letter to go in and out. So if all the settings of the machine are exactlythe same, the cipher clerk only needs to type in the encrypted message, thenthe plaintext will come out. This made it extremely easy for communication.Because German wouldn’t need someone knows engineer or Math sitting in front ofthe Enigma to reveal encrypted message. A simple soldier who could recognizethe alphabet could use this machine. The second feature of Enigma is that no letters will beencrypted to itself after going through Enigma machine. Though it seems not soimportant to know this, this feature actually helped a lot for the cryptologistto trying to guess from encrypted message.
A certain amount of German lexiconinvolves a lot of consonants letters like “t”, “h”, “k” in a sentence. Knowingthat the encrypted letters and plaintext letters shouldn’t have two sameletters line up eliminated a lot of possible combination of words. This will belater discussed. Before we go to the decryption of this machine, let’s takea look at how secure the Enigma machine could me. There were different versionsof Enigma, below we will consider the standard one that was used by Germanduring WWII.
So basically a cipher clerk who operated Enigma machine monthlyreceived a booklet of codes that stated the setting of machine for each day inthat month. (Interesting fact, the booklet was actually using soluble ink, sothat if a soldier were about to get captured, they can throw it into the water.)Three pieces of information will be stated in the setting: the choices ofrotors (for example, rotor II – rotor III – rotor V), and initial position ofrotors (for example, A-P-M, so that the letter goes in will go through the samemechanism as it goes out), and the plugboard switchover letters (for example,QEDKFSI). This standardization enabled the German to convey secret messageacross the battlefield.
We can take a look at the possible number ofcombination of the encoded message. Let F(X) noted as the number of combinationof setting X. So F(choices of rotors)=P(5,3)1.
F(combination of 3rotors)=26^3. F(combination of plugboard) is trickier. First we choose one pairof letter from 26 letters, which is C(26,2). Then we choose another pair,C(24,2). And so on, until we get the ten pairs and multiply them together asC(24,2) * C(22,2) * …
* C(8,2). But then we also not care about the order topick these ten pairs, so we divide the product we had in the last sentence by10!, which will be F(combination of plugboard). F(combination of plugboard)= C(26,2)* C(24,2) * C(22,2) * … * C(8,2) / 10!. This can be simplified to 26! / (6!10! 2^10). So F(combination of the Enigma)= F(choices of rotors) *F(combination of 3 rotors) * F(combination of plugboard)= 158,962,555,217,826,360,000.
This is why that the Enigma machine was famous for its “unbreakable”. It wasnearly impossible for human computers to crack, let alone the message was alsotime sensitive. The cracking of the Enigma machine was a competitionbetween human and computer. Before Alan Turing came to play, there was abreakthrough that came from the Polish people. This breakthrough occurredbefore German changed the rotors number into five and the pair of letter thatwas switched on the plugboard was still six. Back then the German were aware that the more encryptedmessage that their enemy had intercepted, the more likely for them to capturethe pattern of words and figure out the mechanism of Enigma machine. So theycame up with a security measure.
After having the cipher clerk set up themachine, before they sent the plaintext message, they would randomly pick threeletters of their own. They didn’t have to record them down, just typed thesethree letters into the machine (twice, to confirm). Then they switched threerotors into these three letters that were in their head, and started to inputthe plaintext message. And for the receiver of the message, another cipherclerk just had to do the same thing he did – set the machine, type in first sixletters to get the new setting of rotor initial letters, and switch the rotorsto the three letters that decrypted from the first six letters. The advantageof this extra layer of encryption was that among all the messages that wereintercepted, only the first six letter of every message was encrypted by usingthe key (i.e., initial position of rotors) on the booklet. Every plaintext wasencrypted by its own key from the mind of the operators.
This gave less cluefor the German’s enemy to work on, thus made the Enigma machine even moresecure. The Polish was able to figure out the inside mechanism(i.e., all the wires setting in rotors) and the procedure of using the machineby their years of espionage and excellent Math skills. They were just facingthe hardest problem – obtaining the settings in the booklet that German had.
APolish mathematician Marian Rejewski was able to crack this early version ofmachine using only human force. Knowing that within 24 hours the first sixletters of each captured message were encrypted by a same setting of themachine, as well as each these six letters are repetition of a three letterstring, Rejewski successfully found a mathematic solution to detour figuringout plugboard, and created a category of the possible setting of rotors. Thissolution greatly eliminated the possible number of combinations of theencrypted message, and made it possible for having a group of people sittingdown and cracking the message using brute force. After this, as the second World War started, Germanincreased the security level of sending encrypted message. The operators werenot given the initial position of rotors anymore. The new way they did it wasthat before entering plaintext, they set the initial position of rotors in toA-B-C globally. This was not dangerous because German had change the rotor by rebuildingit so that it was possible to rotate the alphabet ring around the circle. Nowthe wiring in rotor was not the same for each rotor anymore.
And then the cipherclerk typed down his/ her own key in three letters twice. Even if it is publicthat A-B-C is the initial position of rotors, the cryptologist wouldn’t be ableto figure out what’s the relative position between rotor and its outsidealphabet ring. The message became even harder to decrypt. However, laterRejewski was able to figure out another solution and decipher that version of Enigmaagain.
It was not until 1940, when German decided that key came from operatoronly needed to be typed in once, that Polish wasn’t able to crack German’ssecret message anymore. Before Nazi German attacked Poland, the Polish gave theencrypted method they had to the British, proved that Enigma is not as”unbreakable” as the British claimed to be. Among all the cryptologist, AlanTuring was the person who came up with the final crack of the Enigma machine.Seemingly impossible to adopt the way the Polish used, Turing was thinking of amore brutal method to decrypt. And the solution was evitably pointing towardsusing a machine against a machine. There were a few prototypes that werecreated, but the one Turing came up was different.
As stated before, Enigma machine has a feature that aletter can’t be encrypted to itself after going through the machine. TheBritish was able to figured out some cribs (also known as known-plaintextattack). They found out that everyday six in the morning there would be amessage about weather sent in the message. And German liked to send “HeilHitler” a lot. Using the word weather “wetter” as example, when trying to lineup the possible word with the encrypted message, we can quickly eliminateplaintext 1 and 3, because they have a same letter at the same spot as theencrypted message. encrypted message A A T A W N V G possible plaintext 1 W E T T E R possible plaintext 2 W E T T E R possible plaintext 3 W E T T E R So the machine Alan Turing designed,Bombe, was based on this idea of cracking.
So we figured that “WETTER” wasencrypted into “ATAWNV”. Turing was able to get a chain of letter from it: Wà(rotor rotate 0 times)àAà(rotor rotate 2 times)àTà(rotor rotate 0 times)àWLet’s take a look at whathappened after W is entered. Wà(plugboard)àunknown letter u1 à(rotors)àunknown letter u2 à(plugboard) à AThen we can image thereare three Enigma machines form the letter chain “WATW”: Wà(plugboard)à u1 à(rotor 0 times)à u2à(plugboard) àAà(plugboard)àu2à(rotor rotate 2 times)à u3à(plugboard) àTà(plugboard)àu3à(rotor rotate 0 times)à u4à(plugboard)àWWe don’t know much aboutthe unknown letters, but we know that since Enigma is reversible, u1 must equalto u4.
Also, since u2 was changed to A by plugboard, when it enters the secondmachine, the same plugboard setting is going to set it back to u2. So we don’t reallyneed to know about the inner mechanism of the three machines. Having a letterchain in hand, we just need to check if u1==u4. Enter each possibility of u1, ifthey turn out equal, then the setting of the Enigma machines might be thecorrect setting. If not, we just need to keep searching. Here is a pseudo code: for u1 in range (A to Z): run through three Enigmamachine, obtain letter u4 if u1==u4: machinenotifies recorder to write down the key (initial position of rotors); recordersends the signal to keep going This is a picture of Bombe.
Every rotating drums in thebox is a rotor. And three of them makes an Enigma machine. After figuring out theletter chain, Turing set the column of three into groups. For example, theexample we had “WATW” needs three machines. And they would be set into a samekey. Every set of three machines has a different setting of key, and all ofthem do the pseudo program above at the same time.
After a lot of waiting,Turing and his recorders would have several possible sets of keys. What theyneeded to do was brutally try the different combinations on plugboards. Until themoment someone pressed W then A was lit up, they had no choice but keep going. So this was the fall of unbreakable Enigma machine. Inspiredby Rejewski’s method, Alan Turing came up with this machine to detour the plugboardand the concrete letters in the chain. One amazing thing that I learned fromthe invention and cracking of Enigma machine is that how human is able tobreakdown the millions of possible combinations into pieces and grasp itsessence, which in this case was the relative relation between letters. And thenthey applied it into building another machine turning against Enigma.
It was a well proof of the infinity of humanintelligence. This is what machine can’t simulate, at least for now. Notation:1. P(n,m) is permutation, meaning ways ofarrange m random items from n items in order.C(n,m) iscombination, meaning ways of choosing m random items from n items, don’t careabout the order. References: All the pictures are from google, don’t own them https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#British_bombe https://en.
wikipedia.org/wiki/Enigma_machine https://en.wikipedia.
org/wiki/Marian_Rejewski http://www.pbs.org/wgbh/nova/military/how-enigma-works.html https://plus.maths.org/content/exploring-enigma http://enigma.
louisedade.co.uk/index.
html The German Enigma cipher machine: beginnings, success,and ultimate failure by Winkel,Brian J. So here’s some thoughtsafter I wrote this research paper. I’m studying Math andLinguistics, so cryptography has been kind of my interest. The Imitation Game (2014) was my inspiration to do this. I triedmy best to write down my understanding, hoped this is something worthy to readfor people who are interested to this amazing topic.
And also considering thelength of the paper and possible losing interest of the reader, I didn’t putthe exact Math method that Rejewski used cracked that early version of Enigmamachine. It was also pretty cool but it was also more abstract and involves alot of algebra.
