Editing Cryptanalysis of the Enigma (section)

==Polish breakthroughs==
{{Main|Cipher Bureau (Poland)}}
{{Tone|date=November 2023|section}}
[[File:Marian Rejewski 1932 small.jpg|thumb|160px|[[Marian Rejewski]] {{Circa|1932}}, when he first broke [[Enigma machine|Enigma]]]]

In the 1920s the German military began using a 3-rotor Enigma, whose security was increased in 1930 by the addition of a plugboard.<ref>{{Harvnb|Wilcox|2001|p=2}}</ref> The [[Polish Cipher Bureau]] sought to break it because of the threat that Poland faced from Germany, but the early attempts did not succeed. Mathematicians having earlier rendered great services in breaking Russian ciphers and codes, in early 1929 the Polish Cipher Bureau invited mathematics students at Poznań University – who had a good knowledge of the German language due to the area having belonged to Germany before being awarded to Poland after World War I – to take a course in cryptology.<ref>The course began on 15 January 1929. A letter dated "Warsaw, 29 January 1929, To Professor [[Zdzisław Krygowski|Z. Krygowski]], in [[Poznań]], ul. Głogowska 74/75", and signed by the "[[Chief of the General Staff (Poland)|Chief of the General Staff]], ''Piskor'' [i.e., [[Tadeusz Piskor]]], ''[[generał dywizji|Generał Dywizji]]''", reads: "I hereby thank ''Pan Profesor'' for his efforts and assistance given to the General Staff in organizing the cipher [i.e., cryptology] course opened in Poznań on 15 January 1929." The letter is reproduced in Stanisław Jakóbczyk and Janusz Stokłosa, ''Złamanie szyfru Enigma'' (The Breaking of the Enigma Cipher), 2007, p. 44.</ref>

After the course, the Bureau recruited some students to work part-time at a Bureau branch set up in Poznań. On 1 September 1932, 27-year-old mathematician [[Marian Rejewski]] and two fellow [[Poznań University]] mathematics graduates, [[Henryk Zygalski]] and [[Jerzy Różycki]], were hired by the Bureau in Warsaw.<ref>{{Harvnb|Rejewski|Woytak|1984b|p=231}}</ref> Their first task was reconstructing a four-letter German naval code.<ref>{{harvnb|Kozaczuk|1984|pp=10–12}}</ref>

Near the end of 1932 Rejewski was asked to work a couple of hours a day at breaking the Enigma cipher. His work on it may have begun in late October or early November 1932.<ref>{{Harvnb|Kozaczuk|1984|p=232}}.</ref>

===Rejewski's characteristics method===
Marian Rejewski quickly spotted the Germans' major procedural weaknesses of specifying a single indicator setting (''Grundstellung'') for all messages on a network for a day, and repeating the operator's chosen ''message key'' in the enciphered 6-letter indicator. Those procedural mistakes allowed Rejewski to decipher the message keys without knowing any of the machine's wirings. In the above example of ''DQYQQT'' being the enciphered indicator, it is known that the first letter ''D'' and the fourth letter ''Q'' represent the same letter, enciphered three positions apart in the scrambler sequence. Similarly with ''Q'' and ''Q'' in the second and fifth positions, and ''Y'' and ''T'' in the third and sixth. Rejewski exploited this fact by collecting a sufficient set of messages enciphered with the same indicator setting, and assembling three tables for the 1,4, the 2,5, and the 3,6 pairings. Each of these tables might look something like the following:
{| class="wikitable" | border=1 style="margin: 1em auto 1em auto"
|-
! First letter
| A||B||C||D||E||F||G||H||I||J||K||L||M||N||O||P||Q||R||S||T||U||V||W||X||Y||Z
|-
! Fourth letter
| N||S||Y||Q||T||I||C||H||A||F||E||X||J||P||U||L||W||R||Z||K||G||O||V||M||D||B
|}
A path from one first letter to the corresponding fourth letter, then from that letter as the first letter to its corresponding fourth letter, and so on until the first letter recurs, traces out a [[cycle graph (algebra)|cycle group]].<ref>Also referred to as a ''box shape'' or a ''chain''. See {{Harvnb|Alexander|c. 1945}} Ch. II Para. 4</ref> The following table contains six cycle groups.<!-- (ydqwvougc)(ket)(nplxmjfia)(zbs)(r)(h) -->
{| class="wikitable" style="margin: 1em auto 1em auto"
|-
! Cycle group starting at A (9 links)
| (A, N, P, L, X, M, J, F, I, A)
|-
! Cycle group starting at B (3 links)
| (B, S, Z, B)
|-
! Cycle group starting at C (9 links)
| (C, Y, D, Q, W, V, O, U, G, C)
|-
! Cycle group starting at E (3 links)
| (E, T, K, E)
|-
! Cycle group starting at H (1 link)
| (H, H)
|-
! Cycle group starting at R (1 link)
| (R, R)
|-
|}

Rejewski recognised that a cycle group must pair with another group of the same length. Even though Rejewski did not know the rotor wirings or the plugboard permutation, the German mistake allowed him to reduce the number of possible substitution ciphers to a small number. For the 1,4 pairing above, there are only {{math|1=1×3×9=27}} possibilities for the substitution ciphers at positions 1 and 4.

Rejewski also exploited cipher clerk laziness. Scores of messages would be enciphered by several cipher clerks, but some of those messages would have the same encrypted indicator. That meant that both clerks happened to choose the same three letter starting position. Such a collision should be rare with randomly selected starting positions, but lazy cipher clerks often chose starting positions such as "AAA", "BBB", or "CCC". Those security mistakes allowed Rejewski to solve each of the six permutations used to encipher the indicator.

That solution was an extraordinary feat. Rejewski did it without knowing the plugboard permutation or the rotor wirings. Even after solving for the six permutations, Rejewski did not know how the plugboard was set or the positions of the rotors. Knowing the six permutations also did not allow Rejewski to read any messages.

===The spy and the rotor wiring===
Before Rejewski started work on the Enigma, the French had a spy, [[Hans-Thilo Schmidt]], who worked at Germany's Cipher Office in Berlin and had access to some Enigma documents. Even with the help of those documents, the French did not make progress on breaking the Enigma. The French decided to share the material with their British and Polish allies. In a December 1931 meeting, the French provided [[Gwido Langer]], head of the Polish Cipher Bureau, with copies of some Enigma material. Langer asked the French for more material, and [[Gustave Bertrand]] of French Military Intelligence quickly obliged; Bertrand provided additional material in May and September 1932.<ref>{{harvnb|Sebag-Montefiore|2004|pp=22–23}}</ref> The documents included two German manuals and two pages of Enigma daily keys.<ref>{{Harvnb|Rejewski|Woytak|1984b|p=256}}</ref><ref>The documents were ''Instructions for Using the Enigma Cipher Machine'' and ''Keying Instructions for the Enigma Cipher Machine'', and the pages of Enigma keys were for September and October 1932 which fortunately had different rotor orders.</ref>

In December 1932, the Bureau provided Rejewski with some German manuals and monthly keys. The material enabled Rejewski to achieve "one of the most important breakthroughs in [[cryptology|cryptologic]] history"<ref>{{Harvnb|Kahn|1991|p=974}}</ref> by using the [[permutation group|theory of permutations and groups]] to work out the Enigma scrambler wiring.<ref>{{Harvnb|Wilcox|2001|p=5}}</ref><ref>{{Harvnb|Hodges|1983|p=170}}</ref>

Rejewski could look at a day's cipher traffic and solve for the permutations at the six sequential positions used to encipher the indicator. Since Rejewski had the cipher key for the day, he knew and could factor out the plugboard permutation. He assumed the keyboard permutation was the same as the commercial Enigma, so he factored that out. He knew the rotor order, the ring settings, and the starting position. He developed a set of equations that would allow him to solve for the rightmost rotor wiring assuming the two rotors to the left did not move.<ref>Solve save for an arbitrary rotation.</ref>

He attempted to solve the equations, but failed with inconsistent results. After some thought, he realised one of his assumptions must be wrong.

Rejewski found that the connections between the military Enigma's keyboard and the entry ring were not, as in the commercial Enigma, in the order of the keys on a German typewriter. He made an inspired correct guess that it was in alphabetical order.<ref>{{Harvnb|Gaj|Orlowski|2003}}</ref> Britain's [[Dilly Knox]] was astonished when he learned, in July 1939, that the arrangement was so simple.<ref>{{Harvnb|Copeland|2004|p=234}}</ref><ref>{{Harvnb|Rejewski|Woytak|1984b|p=257}} citing {{citation |last=Fitzgerald |first=Penelope |author-link=Penelope Fitzgerald |year=1977 |title=The Knox Brothers |location=London |publisher=Macmillan |isbn=1-58243-095-0 |url=https://archive.org/details/knoxbrothers00pene}}</ref>

With the new assumption, Rejewski succeeded in solving the wiring of the rightmost rotor. The next month's cipher traffic used a different rotor in the rightmost position, so Rejewski used the same equations to solve for its wiring. With those rotors known, the remaining third rotor and the reflector wiring were determined. Without capturing a single rotor to reverse engineer, Rejewski had determined the logical structure of the machine.

The Polish Cipher Bureau then had some Enigma machine replicas made; the replicas were called [[Polish Enigma double|"Enigma doubles"]].

===The grill method===
The Poles now had the machine's wiring secrets, but they still needed to determine the daily keys for the cipher traffic. The Poles would examine the Enigma traffic and use the method of characteristics to determine the six permutations used for the indicator. The Poles would then use the [[grill (cryptology)|grill method]] to determine the rightmost rotor and its position. That search would be complicated by the plugboard permutation, but that permutation only swapped six pairs of letters{{snd}}not enough to disrupt the search. The grill method also determined the plugboard wiring. The grill method could also be used to determine the middle and left rotors and their setting (and those tasks were simpler because there was no plugboard), but the Poles eventually compiled a catalogue of the {{math|1=3×2×26×26={{#expr:3*2*26*26}}}} possible {{mvar|Q}} permutations (reflector and 2 leftmost rotor permutations), so they could just look up the answer.

The only remaining secret of the daily key would be the ring settings, and the Poles would attack that problem with [[brute-force attack|brute force]]. Most messages would start with the three letters "ANX" (''an'' is German for "to" and the "X" character was used as a space). It may take almost {{math|1=26×26×26={{#expr:26*26*26}}}} trials, but that was doable. Once the ring settings were found, the Poles could read the day's traffic.

The Germans made it easy for the Poles in the beginning. The rotor order only changed every quarter, so the Poles would not have to search for the rotor order. Later the Germans changed it every month, but that would not cause much trouble, either. Eventually, the Germans would change the rotor order every day, and late in the war (after Poland had been overrun) the rotor order might be changed during the day.

The Poles kept improving their techniques as the Germans kept improving their security measures.

===Invariant cycle lengths and the card catalogue===
[[File:Cyclometer4.png|thumb|175px|[[Cyclometer]], devised in the mid-1930s by Rejewski to catalogue the [[cyclic permutation|cycle]] structure of [[Enigma machine|Enigma]] [[permutation]]s. 1: Rotor lid closed, 2: Rotor lid open, 3: Rheostat, 4: Glowlamps, 5: Switches, 6: Letters.]]

Rejewski realised that, although the letters in the cycle groups were changed by the plugboard, the number and lengths of the cycles were unaffected—in the example above, six cycle groups with lengths of 9, 9, 3, 3, 1, and 1. He described this invariant structure as the ''characteristic'' of the indicator setting.{{dubious|Characteristic|reason=see following dubious. Confuses characteristic with catalogue hash code.|date=May 2015}} There were only 105,456 possible rotor settings.<ref>105,456 is the number of possible rotor settings (17,576) multiplied by the six ''wheel orders'' that were possible at this time. {{Harvnb|Singh|1999|p=131}}</ref><ref>The characteristic does not make the rings disappear; the rings can make the card catalog fail because stepped entries won't be there (a factor of 6 if only single steps are considered). The characteristic allows the actual letters (and therefore the plugboard permutation) to be ignored. Furthermore, Rejewski's notion of characteristic may be different: it may be the cycles rather than the cycle lengths. See Rejewski July 1981, Annals of Hist Computing, 3, 3, pp 217–218.</ref> The Poles therefore set about creating a [[card catalog (cryptology)|''card catalogue'']] of these cycle patterns.<ref>{{Harvnb|Alexander|c. 1945|loc=Ch. II Para. 4}}</ref>

The cycle-length method would avoid using the grill. The card catalogue would index the cycle-length for all starting positions (except for turnovers that occurred while enciphering an indicator). The day's traffic would be examined to discover the cycles in the permutations. The card catalogue would be consulted to find the possible starting positions. There are roughly 1 million possible cycle-length combinations and only 105,456 starting positions.<!-- expect 1, but some structures had thousands. A turnover indicator would not be found. --> Having found a starting position, the Poles would use an Enigma double to determine the cycles at that starting position without a plugboard. The Poles would then compare those cycles to the cycles with the (unknown) plugboard and solve for the plugboard permutation (a simple substitution cipher).<!-- No solution implies not the right starting position. --> Then the Poles could find the remaining secret of the ring settings with the ANX method.<!-- Rejewski claims they developed a faster method, but could not remember it. -->

The problem was compiling the large card catalogue.

Rejewski, in 1934 or 1935, devised a machine to facilitate making the catalogue and called it a ''[[cyclometer]]''. This "comprised two sets of rotors... connected by wires through which electric current could run. Rotor N in the second set was three letters out of phase with respect to rotor N in the first set, whereas rotors L and M in the second set were always set the same way as rotors L and M in the first set".<ref>{{Harvnb|Rejewski|1984e|p=285}}</ref> Preparation of this catalogue, using the cyclometer, was, said Rejewski, "laborious and took over a year, but when it was ready, obtaining daily keys was a question of [some fifteen] minutes".<ref name=RejewskiAppxC242>{{Harvnb|Rejewski|1984c|p=242}}</ref>

However, on 1 November 1937, the Germans changed the Enigma [[reflector (cipher machine)|reflector]], necessitating the production of a new catalogue&mdash;"a task which [says Rejewski] consumed, on account of our greater experience, probably somewhat less than a year's time".<ref name=RejewskiAppxC242/>

This characteristics method stopped working for German naval Enigma messages on 1 May 1937, when the indicator procedure was changed to one involving special codebooks (see [[#German Navy 3-rotor Enigma|German Navy 3-rotor Enigma]] below).<ref name=MahonP13>{{Harvnb|Mahon|1945|p=13}}</ref> Worse still, on 15 September 1938 it stopped working for German Army and Luftwaffe messages because operators were then required to choose their own ''Grundstellung'' (initial rotor setting) for each message. Although German army message keys would still be double-enciphered, the day's keys would not be double-enciphered at the same initial setting, so the characteristic could no longer be found or exploited.

===Perforated sheets===
[[File:Płachta Zygalskiego - decrypting Enigma.jpg|right|thumb|175px|[[Perforated sheets|Zygalski sheet]]]]
{{Main|Zygalski sheets}}
Although the characteristics method no longer worked, the inclusion of the enciphered message key twice gave rise to a phenomenon that the cryptanalyst Henryk Zygalski was able to exploit. Sometimes (about one message in eight) one of the repeated letters in the message key enciphered to the same letter on both occasions. These occurrences were called ''samiczki''<ref>{{Harvnb|Kozaczuk|1984|pp=54, 63}} note 2</ref> (in English, ''females''—a term later used at Bletchley Park).<ref>In {{Harvnb|Welchman|1997|p=72}} he suggests that this arose from the nomenclature for plugs (male) and sockets (female) because the success of this method depended on a number of overlying sheets having their apertures in register.</ref><ref>{{Harvnb|Sebag-Montefiore|2004|p=362}} cites [[Alfred Dillwyn Knox]], who attended the 25 July 1939 Warsaw conference, as having given a more frankly biological etymology, discreetly veiled in French.</ref>

Only a limited number of scrambler settings would give rise to females, and these would have been identifiable from the card catalogue. If the first six letters of the ciphertext were '''''S'''ZV'''S'''IK'', this would be termed a 1–4 female; if ''W'''H'''OE'''H'''S'', a 2–5 female; and if ''AS'''W'''CR'''W''''', a 3–6 female. The method was called ''Netz'' (from ''Netzverfahren'', "net method"), or the [[Zygalski sheets|Zygalski sheet method]] as it used perforated sheets that he devised, although at Bletchley Park Zygalski's name was not used for security reasons.<ref>Instead they were called [[John R. F. Jeffreys|Jeffreys]] sheets after the head of the Bletchley Park section that produced them.</ref> About ten females from a day's messages were required for success.

There was a set of 26 of these sheets for each of the six possible sequences ''wheel orders''. Each sheet was for the left (slowest-moving) rotor. The 51×51 matrices on the sheets represented the 676 possible starting positions of the middle and right rotors. The sheets contained about 1000 holes in the positions in which a female could occur.<ref>{{Harvnb|Welchman|1997|p=215}}</ref> The set of sheets for that day's messages would be appropriately positioned on top of each other in the [[perforated sheets|perforated sheets apparatus]]. Rejewski wrote about how the device was operated:

{{blockquote|When the sheets were superposed and moved in the proper sequence and the proper manner with respect to each other, in accordance with a strictly defined program, the number of visible apertures gradually decreased. And, if a sufficient quantity of data was available, there finally remained a single aperture, probably corresponding to the right case, that is, to the solution. From the position of the aperture one could calculate the order of the rotors, the setting of their rings, and, by comparing the letters of the cipher keys with the letters in the machine, likewise permutation S; in other words, the entire cipher key.<ref>{{Harvnb|Rejewski|1984e|p=289}}</ref>}}

The holes in the sheets were painstakingly cut with razor blades and in the three months before the next major setback, the sets of sheets for only two of the possible six wheel orders had been produced.<ref>{{Harvnb|Welchman|1997|p=216}}</ref>

===Polish ''bomba''===
{{Main|Bomba (cryptography)}}
After [[Marian Rejewski|Rejewski's]] characteristics method became useless, he invented an electro-mechanical device that was dubbed the [[bomba (cryptography)|''bomba kryptologiczna'']], 'cryptologic bomb'. Each machine contained six sets of Enigma rotors for the six positions of the repeated three-letter key. Like the Zygalski sheet method, the ''bomba'' relied on the occurrence of ''females'', but required only three instead of about ten for the sheet method. Six ''bomby''<ref>''Bomby'' is the plural of ''bomba''.</ref> were constructed, one for each of the then possible ''wheel orders''. Each ''bomba'' conducted an exhaustive (brute-force) analysis of the 17,576<ref>17,576=26<sup>3</sup>, since Enigma used 26 letters on each of 3 rotors.</ref> possible message keys.

Rejewski has written about the device: {{blockquote|The bomb method, invented in the autumn of 1938, consisted largely in the automation and acceleration of the process of reconstructing daily keys. Each cryptologic bomb (six were built in Warsaw for the Biuro Szyfrów Cipher Bureau before September 1939) essentially constituted an electrically powered aggregate of six Enigmas. It took the place of about one hundred workers and shortened the time for obtaining a key to about two hours.<ref>{{Harvnb|Rejewski|1984e|p=290}}</ref>}}

The cipher message transmitted the ''Grundstellung'' in the clear, so when a ''bomba'' found a match, it revealed the rotor order, the rotor positions, and the ring settings. The only remaining secret was the plugboard permutation.<!-- apparently easy to solve, but who said so? Alexander? -->

===Major setback===
On 15 December 1938, the German Army increased the complexity of Enigma enciphering by introducing two additional rotors (IV and V). This increased the number of possible ''wheel orders'' from 6 to 60.<ref name=Kozaczuk84p54>{{Harvnb|Kozaczuk|1984|p=54}}</ref> The Poles could then read only the small minority of messages that used neither of the two new rotors. They did not have the resources to commission 54 more bombs or produce 58 sets<!-- They had 2; they needed 58 other sets. --> of Zygalski sheets. Other Enigma users received the two new rotors at the same time. However, until 1 July 1939 the ''[[Sicherheitsdienst]]'' (SD)—the intelligence agency of the [[Schutzstaffel|SS]] and the [[Nazi Party]]—continued to use its machines in the old way with the same indicator setting for all messages. This allowed Rejewski to reuse his previous method, and by about the turn of the year he had worked out the wirings of the two new rotors.<ref name=Kozaczuk84p54/> On 1 January 1939, the Germans increased the number of plugboard connections from between five and eight to between seven and ten, which made other methods of decryption even more difficult.<ref name=RejewskiAppxC242/>

Rejewski wrote, in a 1979 critique of appendix 1, volume 1 (1979), of the official history of British Intelligence in the Second World War: {{blockquote|we quickly found the [wirings] within the [new rotors], but [their] introduction ... raised the number of possible sequences of [rotors] from 6 to 60 ... and hence also raised tenfold the work of finding the keys. Thus the change was not qualitative but quantitative. We would have had to markedly increase the personnel to operate the bombs, to produce the perforated sheets ... and to manipulate the sheets.<ref name=RejewskiHinsleyP80>{{Harvnb|Rejewski|1982|p=80}}</ref><ref>Also quoted in {{Harvnb|Kozaczuk|1984|p=63}}</ref>}}