Working and decryption of the Enigma machine

Since Antiquity and through the centuries, the encryption of messages has played an important role in both the political and military world. We can go back until the Antiquity between the X and VII century BCE in Greece where the Greeks were coiling a piece of paper around a wooden stick, write on it and then uncoiling. After that the message was sent to the receiver and he had just to coil it on the identical wooden stick to read the message. Although this technique was hiding the message for curious eyes, this is not strictly speaking an encryption technique.

The first “real” encryption technique was the Caesar Code, this technique is quite simple to use, you just have to move the alphabet for let’s say 4, so an A is now an E, a B is now an F and so it goes. If we want to encrypt “Alan Turing” by 4 with the Caesar Code, we get: “Eper Xyvmrk” and for the decryption of the message you just have to do the same thing but in reverse. This encryption is called a monoalphabetic encryption, this mean that every letter is shifted by the same number, in our case 4. This method was kept uncracked for many centuries, but around the IX century CE, an Arab scholar, Al-Kindi developed the cryptanalysis and with this technique he was able to decrypt every monoalphabetic code. The cryptanalysis is a technique that consist of using what it commonly called frequency analysis, frequency analysis is a table that record the frequency of apparition of every letter on a large quantity of examples. (put a table for clearer explanation). But this technique also uses what we can call particularity of language like the fact that the word “the” is frequently used so we can deduce that at least one time in the all text. The cryptanalysis also required a good knowledge of the language and a logical and systematic thinking to achieve the decryption of the message.

Through the following centuries, the knowledge of Al-Kindi spread through Europe and made unsafe for powerful empire, kingdom and republic to communicate with classical encryption. In this time period new method of encryption were created but a few of them were having a different approach on encryption, until 1586 when Blaise de Vigenère exposed his new encryption technique, his technique was not like all the other, a monoalphabetic encryption

but instead a polyalphabetic encryption. He wasn’t the first one to use polyalphabetic encryption but Blaise de Vigenère provided an easier technique that all the previous one with still the same level of security. He technic consists by encoding the text with an encoding word, to encrypt the text you change every letter of the encoding word by doing so, A=1, B=2, C=3, etc. After that, you write the encoding word in number under each letter and repeat the sequence of number until you have been to the end of the text. For each number you look on the Vigenère square to see in what the letter is changed (put a picture of the Vigenère square). Let’s make an example, this time we are going to encrypt: “Alan Turing is an English mathematician” with the word: “Enigma”. We get: “Eyit Fuvvvm us ea Mtslmfp smtlrugfigvit”. The Vigenère code was kept uncracked for nearly three centuries but in 1854, Charles Babbage, a British mathematician and inventor, had successfully cracked the Vigenère code that was kept uncracked for centuries. Babbage idea was quite simple on a sufficiently long encrypted text some sequences of letters would be repeated with this observation there’s only two possibilities. The first hypothesis is that the same sequence of letters is the same word or part of it encrypted by the same letters or the second hypothesis is that this is just a coincidence that those sequence is identical. To minimize the risk of having the second hypothesis to happen Babbage technic will only take in count sequences that are at least 4 letters long by doing this the chance of coincidence is of only 1 over 17,576. We can calculate this statistic by doing the following operation:
“take n as the number of letters in the word and then do 1 over 26(n-1)” by doing this operation we can see that the percentage for a three letters sequence is of 0.1479% and it drops with a four letters sequence to 0.0057%. After reporting sequences of the encrypted text. You take the number between the last letter of the first time the sequence appears and the same letter in the second time the sequence appears. You repeat this action for every other sequence. After reporting all the numbers, you check which divider they have in common, we can omit 1 as a divider because that would only be a Caesar code and could be easily decrypted with frequency analysis. One of these dividers will be the length of the encoding word. In our case, we have 2, 3 & 6. After you have those number, you fragment the text by taking one letter out of 6 if you assume that the encoding word is of a length of 6. For time reason, I’ve only fragmented the text by 6 because it is the actual length of the encoding word but if you don’t know the length, you have to do it with every length. With the fragmentation you will have six groups of letters. The fragmentation had for effect that every group is encoded by the same letter, so we can undergo frequency analysis with every group and find every letter of the encoding word to decrypt the message. To see the full decryption of the text, see the first Appendix.

The next breakthrough in cryptography that has been made is the mechanisation of the encryption but more precisely with the invention of the Enigma machine in 1919 by Arthur Schrebius. The Enigma machine was at the beginning commercialised so that company could encrypt theirs messages but because of its high cost. The Enigma machine didn’t sell well but in 1926 the German marine and in 1929 the German army have adopted Enigma as an encoding system and later on by the Axis forces such as Italy and Japan during the second world war.

The Enigma machine and its encryption:

History of the machine:

Shortly after the first world war, a German engineer named Arthur Scherbius began to design a machine that could encrypt messages with a higher level of security that all the others technic at this time. In 1923, Scherbius began to sell its machine called Enigma trough the firm Scherbius & Ritter that he had co-founded. At first the machine was selling for a commercial use but due to its high price (Inserer prix £), the machine was a huge commercial flop. But its success came when the German Navy and just after by Its Army and Air Force adopted the Enigma machine as they official encryption technic, but with few modifications. Since the beginning of the Enigma machine, it had a lot of different models but only a few added a real upgrade. The first one arrived with the third commercial model called Enigma C in 1926, this model added the reflector as you will see later it will facilitate the decryption. The second one arrived with the second military model called Wehrmacht Enigma I in 1930, for this second upgrade, it’s the plugboard that was added. This upgrade added an extra layer of security to the encryption. In 1938 came the last major upgrade to the Enigma machine, this time it didn’t came with a new model. This upgrade was first adopted by the German Army and them by the Navy, it added two more rotors to choose from so now was of five but only three of them will be used as it used to be before they added the extras rotors. Shortly after this upgrade the German Navy decided to add another three more rotors to the set becoming a set of eight rotors. Other upgrades were added afterwards such as the replacement of the reflector with a thinner one and an extra rotor, but this upgrade was only adopted by the German Navy or the addition of even more rotors. For the following of my EPQ, I will focalise on the military mode Wehrmacht Enigma I with a set of five rotors and a plugboard with ten wires.

Description and working of the machine:

The Enigma machine is composed of 5 main parts: rotors, a reflector, a plugboard, a keyboard and a lampboard. The Enigma machine is also composed of other parts, but they don’t influence the encryption, so I’ve decided to don’t do their descriptions.

The keyboard is a German keyboard with two keys that were moved probably to use less space. The only difference between a German keyboard and an English one is that Y and Z are inversed. The tow adjustment that was probably made for space reason are that P was changed with the slash ( / ) and L with the comma ( , ).

The plugboard is a feature that wasn’t in the original design of the Enigma machine but was added when the German military adopted the Enigma machine as their official encrypting system, but it wasn’t possible for a commercial use machine to have a plugboard. On the plugboard there is two holes that are called a jack socket for each letter that is on the keyboard. There is also wires that on each end of it have two jack plug that can go in the jack sockets of the letters. By connecting two letters on the plugboard with the wire it has for effect to switch them before the electrical signal passes through the rotors and after it has passed through. At the beginning there was only seven wires so only seven pairs of letters could be switch, then the German added three more pairs of wires.

The rotor also sometimes called scrambler, as its other name can let us guess the rotor function is to change letters to another one with wiring inside it, we can compare one rotor to a monoalphabetic substitution. The arrangement of rotors works like an odometer that exists in car for example. When a key is typed the first rotor turns for a 1/26th of turn and after a full turn the second rotors turn also for a 1/26th of turn and it will do the same with the third rotor, when the second one does a full turn. At the beginning of the Enigma machine there was three rotors ( labelled I, II, III ) that could be change order between them. Just before the beginning of the second world war, the German army and navy added two more rotors ( labelled IV, V ) but kept three slots for the rotors.

The reflector is like a rotor but only from outside. The main purpose of the reflector is very important not to the encryption but to the decryption. When the current has pass through the three rotor the reflector makes the current pass again in the three rotors. This addition doesn’t affect at any point the encryption. The reason why the reflector is really useful for decryption is that by making the current pass through the three rotors again it is when there is the same setting a letter let’s say for example M is encrypted by another one like A, A will be encrypted by M. So, to decrypt a message you just need to have the setting of the machine when the message was encrypted, and you typed the encrypted message in it, and you will have the message decrypted. This feature also made impossible to encrypt a letter by itself, that feature will by a flaw that Alan Turing will use to decrypt the Enigma machine.

The lampboard It is a panel with the same disposition as the keyboard and light up a key is pressed the lamp that lights up is the letter encoded.

Influence of every part of the machine on the encryption:

The keyboard, reflector and lampboard don’t have any influence over the encryption. But the rotors and the plugboard are the two only parts that influences the encryption.

For the rotor two factor influences the encryption, the order of the rotors and the number of rotors with the numbers of letter over it.

With the numbers of rotors with the number of letters over it. We’ve got logically twenty-six letters on each rotor and with three rotors we can calculate 26×26×26 = 26^3 =17,576 different alphabets of substitution.

For the order of the rotors, we’ve can calculate the numbers of possibility to arrange the rotors with the following equations (r_1 !)/(r_2 !) with “r1” the total number of rotors and “r2” the number of rotors unused. So, with five rotors and two that are unused. With that we can calculate
5!/2! =60 different possibility to arrange

So, for the total of every different alphabets of substitution that the rotors produced are equals to 60 × 17,576 =1,054,560.

For the plugboard only the wiring can influence the encryption. We can calculate the numbers of different possibility of wiring the plugboard with the following equation 26!/(w! × u! × 2^w ) with “w” the numbers of wire and “u” the numbers of letter that are kept unconnected with a wire. If we have ten wires, so we are kept with six letters that are un connected. We get the numbers of permutation possible that equals to 26!/(10! × 6! × 2^10 ) = 150,738,274,937,250.

At the end we get 150,738,274,937,250 × 1,054,560 =158,962,555,217,826,360,000 (~159 quintillion) different alphabets of substitution.

How does the encryption work :

Before even beginning the encryption, the German modified part of the text by replacing punctuation, spaces or even some word by a letter that we rarely use like X or Y or combination of letter. The Wehrmacht, the Luftwaffe and the Kriegsmarine use different letter or word to replace punctuations, spaces or words.

After the text was “prepared”, the Enigma operator had to put the right settings in the machine like the plugboard setting, the rotor arrangement, the rotor orientation also called day-key, the ring setting and the message key. The first four of them where given a book that gives the plugboard setting, the rotor arrangement, the ring setting and the rotor orientation for every day of the month, a new book was issued for every month with different settings for the machine. Those books were only given to Enigma operator and the Army, Navy and Air force had a different one.

The plugboard setting were given as pair of letters that must be switch like M/A or J/B. The numbers of pair depended of the numbers of wires and every wire must be used so if there were 10 wires, you will have 10 pairs of letters to switch.

For the rotor arrangement, the instructions were quite simple, it tells them which rotor to use and in which order form left to right like III-V-I or II-IV-III.

For the ring setting, it was how the ring were the numbers were written over it was position as it can be turn.

For the rotor orientation, or day-key, it was also quite simple and straight forward, it gives three numbers between 1 and 26, that how the rotor must be orientated like 08-07-16 as you can see it one the picture.

For the message-key, it’s three letter that were randomly chosen by the Enigma operator. Those three letters were typed two time so if the letters were MAJ, the operator would type MAJMAJ in the Enigma machine with the day-key and we would get a group of six letters like WFUNGQ. The rest of the message rest of the message would be encrypted with this message-key. The message-key would give the rotor orientation of the message by having A =1, B = 2, …, Z = 26. In our case we would have 13-01-10 as our rotor orientation. Around 1940, German cryptologist realised that the repetition of the message-key was a flaw of the uses of the Enigma machine.

Every time a key is pressed, an electrical signal is sent and then one letter of the lampboard illuminates. If we get more in depth, the signal pass first in the plugboard then in the first, second and third rotors to get into the reflector. The reflector is redirecting the signal in the rotors but this time through the third, second and first one to again pass through the plugboard and then turn one light bulb on the lampboard that indicate in which letter was encrypted the letter that you pressed one the key

But when. You release the key the light bulb will turn off and the first rotor as said before will do a 1/26th of turn and after it had made a full turn it will make the second turn for a 1/26th of turn and the second one will do the same with the third one. As Marian Rejewski, a polish mathematician that was the first to succeed at decrypting the Enigma machine, writes in its Applicaciones Mathematicae 16, No. 4. We can write the working of the machine encryption (T)with the following equation: T = SNMLRL^(-1) M^(-1) N^(-1) S^(-1).

For an example of what a message looks like we it’s encrypted go and see Appendix 2.

The decryption of the machine:

History of the decryption:

Around 1926, a new type of messages was received by the British cryptanalyst. Those messages had the particularity that it was completely encrypted and there was no known technique to decipher it. Those messages were in fact encrypted with the Enigma machine that the German army had recently adopted has them principal encryption technique. It’s at this precise time period that the race against the Enigma machine had begun for the Allies. No country was able to decrypt the Enigma code neither the French or the English or even the Americans cryptanalyst were able to any single message. The allies rapidly lost any hope to decrypt the Enigma machine, but that wasn’t a big problem as they were in a dominant position over Germany that had just lost the first World War a decade ago. But that wasn’t the case for a country that had just establish itself as an independent nation after the second World War, Poland. Poland was threatened by a direct invasion of Germany. It’s with fear and determination that the polish cryptanalyst also known as the Biuro Szyròw begun the cryptanalysis of the Enigma machine. No great advance in the cryptanalysis was made until a German spy named Hans-Thilo Schmidt sold highly secret about the Enigma machine to the French in 1931. The French gave to Poland all the intel that they had in they possession. Theses intels helped the polish cryptanalyst to break the Enigma code. At the end of 1932, the Enigma machine was successfully decrypted by the Biuro Szyròw, mostly by the mathematician Marian Rejewski. We will get more in detailed how he did it later on. The polish decrypted improved they technique by mechanising it, with the invention of the polish Bomba. But as the second World War begun, the polish prior to the invasion by Germany gave all they research and technique to decrypt the Enigma machine with a replica of it and blueprints of the Bomba. After that incident, it’s the English that took the relay of the cryptanalysis of the Enigma machine in Bletchley Park. A team was created, most of the people in there were mathematician an was led by Alan Turing. Truing and his team improved the polish technique and also developed they own technique if the flaws that the polish used to decrypt the Enigma machine. Which happened in 1940, the German modified its technique, but the English cryptanalyst responded with its Turing-Welchman Bombe and decrypted German messages until the end of the second World War.

The Polish cryptanalysis:

The information that was given by the German spy only told how it was working not how it was built and the inner circuit. So, the Polish had to recreate a working Enigma machine and decrypted it. The Polish successfully recreated an Enigma machine with the help of an intercepted commercial model who helped a lot the Polish cryptanalyst. The most difficult part to recreate the machine was that they didn’t knew how the wires were connected in each rotor. The number of possible arrangements was huge
26! = 403,291,461,126,605,635,584,000,000 Rejewski and its team succeed to find them. Now that the recreation of the Enigma machine was completed, the Polish cryptanalyst could focus on the decryption of it. Rejewski found out that the message key was a flaw to the security of the Enigma machine. The fact that the message key was repeated twice and encrypted later one, Marian Rejewski could, on an amount of approximately 100 messages, find the cycle of transposition, as the first and the fourth letter were the same, the second was the same as the fifth and the third is the same as the sixth. For all the following mathematical demonstrations and examples will be taken from Stephanie Faint university thesis “The Enigma History and Mathematics” or Marian Rejewski “Applicationes Mathematicae. 16, No.4”.

The rotors wiring :
If we take back the equation for the encryption T = SNMLRL^(-1) M^(-1) N^(-1) S^(-1). In this is missing the entry drum as it had no effect over encryption an Rejewski just made two guess about it and the second was the good one, I will not come over it. To this equation the permutation of the first rotor

A = SPNP^(-1) MLRL^(-1) M^(-1) 〖PN〗^(-1) P^(-1) S^(-1)
B= SP^2 NP^(-2) MLRL^(-1) M^(-1) P^2 N^(-1) P^(-2) S^(-1)
C= SP^3 NP^(-3) MLRL^(-1) M^(-1) P^3 N^(-1) P^(-3) S^(-1)
D= SP^4 NP^(-4) MLRL^(-1) M^(-1) P^4 N^(-1) P^(-4) S^(-1)
E= SP^5 NP^(-5) MLRL^(-1) M^(-1) P^5 N^(-1) P^(-5) S^(-1)
F= SP^6 NP^(-6) MLRL^(-1) M^(-1) P^6 N^(-1) P^(-6) S^(-1)

Around 1932 Marian Rejewski was hand out sheets with daily setting of the machine, so now the plugboard connections (S) are known and we can simplify MLRL^(-1) M^(-1) to Q, so we get:

SAS^(-1)=PNP^(-1) Q〖PN〗^(-1) P^(-1)
SBS^(-1)= P^2 NP^(-2) QP^2 N^(-1) P^(-2)
SCS^(-1)= P^3 NP^(-3) QP^3 N^(-1) P^(-3)
SDS^(-1)= P^4 NP^(-4) QP^4 N^(-1) P^(-4)
SES^(-1)= P^5 NP^(-5) QP^5 N^(-1) P^(-5)
SFS^(-1)= P^6 NP^(-6) QP^6 N^(-1) P^(-6)

Because P is a known permutation we shift it to the left side and get:

P^(-1) SAS^(-1) P=NP^(-1) Q〖PN〗^(-1)
P^(_2) SBS^(-1) P^2= NP^(-2) QP^2 N^(-1)
P^(-3) SCS^(-1) P^3= NP^(-3) QP^3 N^(-1)
P^(-4) SDS^(-1) P^4= NP^(-4) QP^4 N^(-1)
P^(-5) SES^(-1) P^5= NP^(-5) QP^5 N^(-1)
P^(-6) SFS^(-1) P^6= NP^(-6) QP^6 N^(-1)

This set of equation can be simplified to :

U=NP^(-1) Q〖PN〗^(-1)
V= NP^(-2) QP^2 N^(-1)
W= NP^(-3) QP^3 N^(-1)
X= NP^(-4) QP^4 N^(-1)
Y= NP^(-5) QP^5 N^(-1)
Z= NP^(-6) QP^6 N^(-1)

If we multiply them, we them got:

UV=NP^(-1) (QP^(-1) 〖QP)PN〗^(-1)
VW=NP^(-2) (QP^(-1) 〖QP)P^2 N〗^(-1)
WX=NP^(-3) (QP^(-1) 〖QP)P^3 N〗^(-1)
XY=NP^(-4) (QP^(-1) 〖QP)P^4 N〗^(-1)
YZ=NP^(-5) (QP^(-1) 〖QP)P^5 N〗^(-1)

Now we can substitute them into each other’s, so we get:

VW=NP^(-1) N^(-1) (UV〖) NPN〗^(-1)
WX=NP^(-1) N^(-1) (VW〖)NPN〗^(-1)
XY=NP^(-1) N^(-1) (WX〖)NPN〗^(-1)
YZ=NP^(-1) N^(-1) (XY〖)NPN〗^(-1)

Theorem 1: Let α,β ∈S_n. The equation XαX^(-1)=β has a solution X∈S_n if and only if α and β the same decomposition cycle. Suppose that α(and β) is a product of m_1 1-cycles, m_2
2-cycles, m_3 3-cycles, …, m_n n-cycles, so that

n=∑_(i=1)^n▒〖i∙m_i 〗

Then the number of solutions to XαX^(-1)=β is

∏_(i=1)^n▒〖i^(m_i )∙(m_i !)〗

Now that we have all the possible solutions we just have to find when they are the same and the internal wiring of the first rotor is now known. As the German changed the rotors order on a regular basis, the Poles had just to do it again with the two left rotors. This task may seem long and exhausting, but it was necessary to be done and was only needed to be done once, since the internal wiring wouldn’t change.

The Message-key:

If we take the following four message-key as examples :

ajk gdi
grt pcn
psb ekf
eso ahf

Those four message-keys didn’t appear in this order they would be taken from a reasonably amount of message-key received throughout the day. As the first and the fourth letters are the same, we can put this in the following cycle a  g  p  e  a that can be written as (agpe). This cycle of a length of 4. If we continue to do this with the rest of message received during the day we can every cycle of permutations for the first and fourth letter, we will call them AD. Exactly the same can be done with the second and the fifth, that we will call BE and the third and the sixth, that will be name from now CF.

Theorem 2: Let G be the set of all elements g∈S_2n such that g is a product of n disjoint transpositions. Let α∈S_2n. The equation XY=α,X,Y∈G has a solution if and only if the cycle decomposition of α has an even number of disjoint cycles of each order.
If α as 2m_i i-cycles so that

2n=∑_(i=1)^n▒〖i∙2m_i 〗

Then the number of solutions is

∏_(i=1)^n▒(i^(m_i )∙((2m_i )!))/(m_i !∙2^(m_i ) )

Where i is the length of the cycle and m_i the numbers of pair that this cycle has and n is the numbers of letters in the alphabet divided by two (13). The results of the second can be seen in the third Appendix. With this Theorem 1 we can see that most of the times there is a reasonable number of solutions to be tested.

If we know this, we can, in most of the case, deduced the message key. If we take the set of message-keys in Appendix 3 we’ve got:
AD = (FGTENLYHA)(KJSRVMDXW)(CBU)(IQP)(O)(Z)
BE = (HGXFWPULY)(VJENOQIMZ)(KRA)(TDS)(B)(C)
CF = (GXCVLIERAQUY)(PMWDHSZFBJTK)(N)(O)
Because some of the German operator of the machine use logical message-keys following alphabetical order or patterns on the Enigma keyboard, some message-keys would appear more often, with that the Polish cryptanalyst could use it to find the message-key. In our case, some message-keys appear more often like CEH BNS, VCB MCJ, VKR MRA, VTW MDD and ZXN ZFN. Now that we have the message-keys that are repeated. We can look to the permutations AD, BF and CF. In those each cycle of the same length can be paired together, so in AD, (FGTENLYHA) goes with (KJSRVMDXW), (CBU) goes with (IQP)and (O) goes with (Z). We don’t know in which order they are paired because C can be I, Q or P, except that with O and Z, we know that if an O is written as the first or fourth letter, it will be equals to an Z and inversely. In BE, it’s B and C that are in the same position as O and Z. In CF, it’s N and O. With all this information we can go back to our repeated message-keys. Two of them can take profit of what is shown below, VCB MCJ and ZXN ZFN. First let’s take VCB MCJ, know that we know that we know that if an B is written as the first or fourth letter, it will be equals to an C and inversely. As the second letter is C, we can be sure that the second letter of the message-key is B, so we’ve got ?B? as message-key. Now, we look at what pattern we could find with B in the middle. We can either have ABC or VBN. As we know that a letter cannot be encrypted by itself the message-key VBN therefore cannot the one that we are searching for. That left us with ABC as a possible message-key. If we say that ABC is indeed the message-key, we can those cycle together in this order for the AD permutation :
(VMDXWKJSR)
(AHYLNETGF)
And in this order for the CF permutation :
(BJTKPMWDHSZF)
(CXGYUQAREILV)
Now that we have completed this, we can see that the CF permutation is in order so every third and sixth letter can now be found and some of the first letter can be found as well. So, for VTW MDD we have A?A, for CEH BNS we have ??E, for VKR MRA A?D and for ZXN ZFN we have O?O. So, we can fairly assume that the message-keys are AAA , ASD and OOO and therefore the following permutations can be order like this :
(TDS)
(ARK)
And
(XFWPULYHG)
(ONEJVZMIQ)
Now we only need to find the message-key from CEH BNS that is now ?WE, which is probably QWE, so we’ve got:
(CBU)
(QIP)
Now that all the cycles are put in the good order, we are able to decrypt every message-keys during all day.

Zyglaski Sheets :

Other technique was used to decrypt the Enigma machine, but I won’t go over it due to the fact that they weren’t used for a long time period and didn’t have any impact over the evolution of the decryption of the machine. Since the change in how the message was encoded it was now impossible to reconstruct the AD, BE and CF cycle for the day as the ring setting changed for every message and was written in plain text at the start of the message. But the correlation between the first and the forth, the second and the fifth and the third and the sixth still remain. The Zygalski sheets took advantage of that so when the first and fourth or the second and fifth or even the third and the sixth happen this mean that for this letter, the cycle length was of 1, this was called fixed point of permutation or females. The Zygalski sheets took in account every female possible. Those sheets were composed of a grid of 51×51 that was decompose in 4 rectangles, the x-axis represented le middle rotor M and was marked from a-z and then form a-y and the y-axis represented le right rotor N and was marked from a-z and then form a-y. Every female was marked by a hole. All those four rectangles were replicating nearly the exact same pattern. Each sheet represented a position of the slow-moving rotor or left one (L) so to have a full set it will require 26 sheets. This set needed to be done six time in total because with three rotors at the time it was the numbers of possible arrangements. For how to use it I haven’t found anything very clear, the only things that goes quite close to explain it is in Marian Rejewski Applicationes Mathematicae. 16, No. 4 :”When the sheets, according to a prescribed program and in a proper sequence with proper relative position, were placed one upon another, the number of transparent holes diminished gradually. If a sufficient number of data was available, at the end a single hole remained corresponding probably to the good case, i.e. the solution. Frome the position the sequence of rotors and the position of the rings could be calculated so that, by comparing the letters of keys with the letters in the machine, the permutation of S (plugboard), thus the whole key, could also be derived”.

The polish Bombe :

The polish Bombe was a mechanisation of a technique of decryption. In fact, they were six Bombes working together one for each possible rotor order. It also used the occurrence of females to find the correct settings, it took around two hours to have a solution. But due to the invasion of Poland by the Germans. The Polish ciphers bureau had to destroy every machine and just kept blueprint of it to give them to the Allies. So, we don’t really know how the machine really worked. Even Marian Rejewski, the creator of the machine, couldn’t remember what the procedure was or how to build it. The only things that can be useful is a sketch of the machine made by Rejewski many years later with no indication on it working.

End of the polish cryptanalysis of the Enigma machine :

In 1939, when two more rotors were added. This modification changed from six possible order to arrange to sixty, therefore 54 new set of Zygalski sheets needed to be created and 54 new polish bombes. But with the growing risk of invasion of Poland by the Germans, the Polish had to share they secrets with the Allies. So, on 24th of July of the same year, French and British representatives came to Warsaw, were they discovered with surprise that the Poles had decrypted the Enigma codes for years. The representatives were hand out two Enigma replicas, blueprints for the polish bombe and the only two sets of Zygalski sheets that was usable with the increase of the numbers of rotors. Two weeks after this encounter, Poland was invaded by the German and marked the beginning of the second World War. The three main mathematicians were able to escape Poland and go to France. After that they didn’t had a huge role in the decryption of the machine. It was the English that took the relay.

The English cryptanalysis:

Right when England declared war to Germany, the Government Code and Cipher School (GC&CS) that just moved to Bletchley Park, hired Alan Turing. At first the English cryptanalyst began to master the Polish technique to decrypt the Enigma code with Zygalski sheets. But Turing knew that the flaws that the polish technique was using could disappear and that they couldn’t relay on it for the all duration of the war. So, Turing decided, around the beginning of 1940, improve the Polish Bombe but not by using the message-key but by using the known-plaintext attack or more so supposedly known-plaintext attack. A known-plaintext attack is a technique where a part of the message is known by the person that decrypts it or in the case of supposedly known-plaintext attack the part of the text is supposed. This part was called by the cryptanalysts team in Bletchley Park as “cribs”. One of the features of the machine is that a letter cannot be encrypted by itself, so, this helped Turing and is team to place the crib in compresence of the encoded text. The crib could consist as word that were frequently used or on a daily basis like wetter that means weather in German or heil Hitler because it was frequently used in the end of the message. The cribs could also be determined by the situation of the war field such as a number of tank or what the weather was like. Longest the crib was the more reliable it was. For this example, we will use Wettervorhersage as a crib, Wettervorhersage means weather forecast in German.

Encrypted text W S N M K G G S T Z Z U G A R L V E
Crib at Position P W E T T E R V O R H E R S A G E W=W impossible
Crib at Position P+1 W E T T E R V O R H E R S A G E Possible
Crib at Position P+2 W E T T E R V O R H E R S A G E E=E impossible

Operating system of the Bombe :

The operating system is based on contradiction. At first a hypothesis is made if a contradiction occurs, the machine passes to a new hypothesis and start again to stop when there is no contradiction. The only problem was that for the military Enigma machine with its plugboard was adding a tremendous number of possibilities. Going through every possible rotor position was still manageable. So the first idea that Alan Turing made was to begin with an hypothesis on a cable swapping and when a contradiction happens the Bombe would move to another hypothesis, but the interesting part comes when every possible swapping pair that were used in the false assumption would also being wrong, with this the numbers of possibility were decreasing quite rapidly. The problem was that a loop, also called cycle in the graph theory, in the crib was needed to find the right position, but it was still manageable. A first was build, it arrived at Bletchley Park on the 18 March 1940 and was called “Victory”. The machine was able to decode some of the German’s messages. After the first machine was build, Gordon Welchman, that recently arrived on Turing’s team, propose to add a piece that was called the “diagonal board”. In Turing blueprint of the machine, each letter swapping wouldn’t take in count it opposite. Let say that (MA) was the swapping, Turing’s Bombe wouldn’t take in count the (AM) swapping, but with the “diagonal board”, that was composed of a panel that was himself composed of 676 electrical terminal disposed in a 26×26 square, so now, with this could try out more possibility and the crib didn’t needed to form a loop.

How did the machine was used to find the proper solution ? :

This example will be taken from Magnus Ekhall and Fredrik Hallenberg “Turing Bombe Tutorial”

We need to create want is called a menu before it goes through the Bombe, for this we will have a rotor order of II/V/III and will use the crib that we used earlier:

Letter number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Clear text W E T T E R V O R H E R S A G E
Encrypted text S N M K G G S T Z Z U G A R L V

From this table we can apply the graph theory therefore we get that:

Because two graphs are in general not very easy to work with, we will not take in count the OTKM in count. We can also take out W from the as it doesn’t break any long chain an because a Bombe as 12 rotor per line and every edge will be assigned a rotor, it will make the solution easier to find. If we take in fact that the first permutation is ZZA , the second ZZB and etc, we will get :

Now that this is done, we will take the two following routes to have a bigger chance of success. The two routes are : U -> E -> G -> R -> A -> S -> V -> E -> N and H -> Z -> R -> G-> L. When this is done, we need to choose an input, it for this letter that the solution will be tested, the input must be a letter in the graphs that is central, in our case we will take G. And with all of this finished we will need to make a table with further information, this table is called a menu. So, on one side we will get what permutation is done between every letter so for U -> E, it will be labelled 1: ZZK and one other side we will get the connection between the letter so for U as it’s the first letter it will be written U: 1 in and for E is will be written E: (1 out, 2 in),
(7 out, 8 in). To finish this, we need to choose where the current will enter, this entry must be on one of the routes but mustn’t be the input or have a common edge with it, we will choose A.

1: ZZK U: 1 in
2: ZZE E: (1 out, 2 in), (7 out, 8 in)
3: ZZF G: (2 out, 3 in), (11 out, 12 in), input
4: ZZN R: (3 out, 4 in), (10 out, 11in)
5: ZZM A: (4 out, 5 in)
6: ZZG S: (5 out, 6 in)
7: ZZP V: (6 out, 7 in)
8: ZZB N: 8 out
9: ZZJ H: 9 in
10: ZZI Z: (9 out, 10 in)
11: ZZL L: 12 out
12: ZZO

Current entry at A

If this menu entered in the machine it will test for the hypothesis that A is connected to G on the plugboard. Even if this hypothesis is wrong the machine will indicate to us the right solution because it will get rid of a big amount of the will testing the hypothesis.

Now the menu must be entered in the Bomb. At first, we need to but every drum of the machine to its equivalent for the rotor. So, for the top line, the drums of the second rotor must be put, the middle line for the fifth one and for the bottom line the one for the third one. Now that the good drums are in place, we need to set them up. For that we have to look back at our menu, so for the first column of three rotors we will get from top to bottom ZZK and the same action must be done again for the other eleven ones.

Nom that the front is done, let’s set up the back of the machine. To set up this part, we will need to look back on our menu where the letters are written. On the back on the machine there are two possible way to connect the board, first with what is called a “bridge”, a bridge is a connector that connect two sockets to become on. The second one is called a “cable”, the cable connect two sockets together in a “classical” way. So now that this is known every time a parenthesis appears on the menu a bridge must be put for the two connectors in question and after every letter must be connected to its entry. So, if we take our example, we connect S with the bridge that connects 5 out to 6 in. If a letter must be connected to multiple connector it will past through an intermediate state. The first letter will be connected to a socket that is called CO1 and the second in CO2 and so on. Those sockets will for effect to multiply the current to all the other sock to have the same name. So, if we take E a cable will be put in one of the CO1 socket and then a cable will be connected from another CO1 socket to the 1 out 2 in bridge and from another CO1 socket to the 7 out 8 in bridge. A final cable must be added, this cable will connect the current input, G in our example, to one of the sockets named CH, as we are using the first three lines, we will connect it to CH1. The back of the machine is now set up.

The last part of the machine to be set up is the right side but this one is quite straight forward. On the right side we have switches the one that need to be turned up are the chain 1 to on, because we are using the first three lines, the A switch in the first column, because we choose this as current entry and the switch carry to on, so, that the machine will continue after a result is found. Now the Bombe is completely set up. So, we can turn on the Bombe and wait until it stops to give its first result.

When the Bombe stops, on the middle row, on the ware right there are three drums, don’t appear on the two other rows. Those three drums will indicate the ring setting and on the right side a little panel will indicate a letter. This letter is the connection on the plugboard to the input so in this case G.

The Bombe stops for the first time , one the three yellow rotors SNY and D is indicated on the right side of the machine. If this is written somewhere the Bombe can start again from this place and carry on until it stops another time. Now that we have a possible solution, we have to test it, at Bletchley Park the cryptanalyst had modified a Typex, the English response to Enigma in encrypting system, to emulate an Enigma machine but without the plugboard. Now we adjust the checking machine as following, S will be the ring setting for the first rotor, N for the second one and Y for the third one.

Conclusion:

As a foreign student, I’ve discovered the incredible story of the decryption of the Enigma machine through the film “Imitation Game” by Morten Tyldum. In this film, only the English part of the decryption is covered. This EPQ made me discover all the incredible work done by the Polish Cipher Bureau and also how the technique used by Alan Turing was ingenious. This EPQ also showed that even if the machine was not exempt of any flaws but the one that were used to decrypt it and to make replicas, were due to either laziness of the German Enigma operator or due to rigour of the German procedure of encryption. This also shows that even if you have a good encrypting system, a really well though technique must be applied to the encryption to make the most of the encryption system. On my personal side, I also found it interesting to discover knew areas in mathematics such as cycle notation, but also challenging to do it on my own. Overall this project improved my curiosity towards people that worked in the shadows and their work that they had to keep for the greater good, even for the price of their own life, like the story of Alan Turing, who was accused of gross indecency and was condemn to chemical castration, which probably let to its death even if it is still debated nowadays if it was suicide.

Appendices:

Appendix 1: Decryption of a text encoded with the Vigenère square

HHTMHVHHRBVSXFFVTRHHXITUTEZVTGGXHCRKGLLTRJHPVZNJBMKIAZEUELGNXKLMRTPUJSVTWUELYUOYCGNTWUCTGNXJVWCRXIWBUKKYRTZGWIIMQNXLKPRUGFPANJGYJAVTMBVYHKXHJTVLXQRAGNTNJPRCBMYMQLHLRKUOEXSCGJBXEWGNTPVWAKHHVEVTMYILNEMBVYHKXHNIFJHCEOAKXXCMJUKENPVRXARHVTZILBUKKYSWAEPCELBCTNKPRTXQWIYRXHJVBCTVZZQLEYNJLZAYNQAJHQJBNXMFZVTZAYHCRKGUELFNXJIQPQXXYMELBHXMEGLCEOYKWLFXBLUFFWQLXFCWAZAYJVBCHOKAVJXBVZJOGXFENYLBVTBUDYUIGZAYSTBUWIEBUKLHFEFNXMRQQZHBVZFKEZFPUUPCNQFNMBRBVNTXRLNAZBKMEZAUKPNJLEZVNYPBZBRGLMEWJRBJJIFXXXRAORHIUIAJAUZZNYUFRKXGLYSWAE

Letter sequence Number between the sequence Dividers Common dividers
HCRKG 270 1; 2; 3; 5; 6; 9; 10; 15; 18; 27; 30; 45; 54; 90; 135 & 270 2; 3 & 6
YSWAE 264 1; 2; 3; 4; 6; 8; 11; 12; 22; 24; 33; 44; 66; 88; 132 & 264 2; 3 & 6
JVBC 90 1; 2; 3; 5; 6; 9; 10; 15; 18; 30; 45 & 90 2; 3 & 6
The encoding word length can therefore be 2, 3 or 6.

HHXHTGGHBEXPWOWXXKWXGGMXXTBHEBTHMMXHXKXZKPTXXTEAHMAGXXBLWUXAHXGLDAWLXHEPMTZALPLBXHAUL