Editing W. T. Tutte (section)

==Second World War==
{{See also|Cryptanalysis of the Lorenz cipher}}
[[File:SZ42-6-wheels-lightened.jpg|right|upright=1.8|thumbnail|The Lorenz SZ machines had 12 wheels each with a different number of cams (or "pins").
{| class="wikitable" | border=1  style="margin: 1em auto 1em auto"
|-
!Wheel number
|1||2||3||4||5||6||7||8||9||10||11||12
|-
! BP wheel name<ref name = "GRoT11B6">{{Harvnb|Good|Michie|Timms|1945|p=6}} in ''1. Introduction: German Tunny''</ref>
| style="text-align:center;"| <math>\psi_1</math>
| style="text-align:center;"| <math>\psi_2</math>
| style="text-align:center;"| <math>\psi_3</math>
| style="text-align:center;"| <math>\psi_4</math>
| style="text-align:center;"| <math>\psi_5</math>
| style="text-align:center;"| <math>\mu</math>37
| style="text-align:center;"| <math>\mu</math>61
| style="text-align:center;"| <math>\chi_1</math>
| style="text-align:center;"| <math>\chi_2</math>
| style="text-align:center;"| <math>\chi_3</math>
| style="text-align:center;"| <math>\chi_4</math>
| style="text-align:center;"| <math>\chi_5</math>
|-
! Number of cams (pins)
|43||47||51||53||59||37||61||41||31||29||26||23
|}
]]

Soon after the outbreak of the [[Second World War]], Tutte's tutor, Patrick Duff, suggested him for war work at the [[Government Code and Cypher School]] at [[Bletchley Park]] (BP). He was interviewed and sent on a training course in London before going to Bletchley Park, where he joined the Research Section. At first, he worked on the [[Boris Hagelin|Hagelin]] cipher that was being used by the Italian Navy. This was a [[Rotor machine|rotor cipher]] machine that was available commercially, so the mechanics of enciphering was known, and decrypting messages only required working out how the machine was set up.<ref>{{Harvnb|Tutte|2006|pp=352–353}}</ref>

In the summer of 1941, Tutte was transferred to work on a project called Fish. Intelligence information had revealed that the Germans called the wireless teleprinter transmission systems "Sägefisch" ('sawfish'). This led the British to use the code [[Fish (cryptography)|Fish]] for the German teleprinter cipher system.  The nickname Tunny (tunafish) was used for the first non-Morse link, and it was subsequently used for the [[Lorenz cipher|Lorenz SZ machines]] and the traffic that they enciphered.<ref>{{cite book |title=Codebreakers: the inside story of Bletchley Park |editor1=F.H. Hinsley |editor2=Alan Stripp |year=2001 |last=Hinsley |first=F.H. |chapter-url=https://books.google.com/books?id=j1MC2d2LPAcC&pg=PA141 |chapter=An Introduction to Fish |pages=141–148 |publisher=Oxford University Press |isbn=0-19-280132-5 |orig-year=1993}}</ref>

Telegraphy used the [[bit|5-bit]] [[ITA2|International Telegraphy Alphabet No. 2]] (ITA2). Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12-letter [[Cryptanalysis#Indicator|indicator]], which implied a 12-wheel rotor cipher machine. The first step, therefore, had to be to diagnose the machine by establishing the logical structure and hence the functioning of the machine. Tutte played a pivotal role in achieving this, and it was not until shortly before the Allied victory in Europe in 1945, that Bletchley Park acquired a Tunny Lorenz cipher machine.<ref name=Sale>{{Citation |last=Sale |first= Tony |author-link=Anthony Sale |title=The Lorenz Cipher and how Bletchley Park broke it |url=http://www.codesandciphers.org.uk/lorenz/fish.htm |access-date=21 October 2010}}</ref> Tutte's breakthroughs led eventually to bulk decrypting of Tunny-enciphered messages between the German High Command [[Oberkommando der Wehrmacht|(OKW)]] in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany.<ref name="Hinsley 1993 8"/><ref name="Brzezinski 2005 18"/>

===Diagnosing the cipher machine===
On 31 August 1941, [[Lorenz cipher#Code breaking|two versions of the same message]] were sent using identical keys, which constituted a "[[Cryptanalysis#Depth|depth]]". This allowed [[John Tiltman]], Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a [[Gilbert Vernam|Vernam cipher]] which uses the [[Exclusive or|Exclusive Or (XOR)]] function (symbolised by "⊕"), and to extract the two messages and hence obtain the obscuring key. After a fruitless period during which Research Section cryptanalysts tried to work out how the Tunny machine worked, this and some other keys were handed to Tutte, who was asked to "see what you can make of these".<ref>{{Harvnb|Tutte|2006|p=354}}</ref>
[[File:Lorenz-SZ42-2.jpg|right|280px|thumbnail|The Lorenz SZ42 machine with its covers removed. [[Bletchley Park]] museum]]
At his training course, Tutte had been taught the [[Kasiski examination]] technique of writing out a key on squared paper, starting a new row after a defined number of characters that was suspected of being the frequency of repetition of the key.<ref>{{Harvnb|Bauer|2006|p=375}}</ref> If this number was correct, the columns of the matrix would show more repetitions of sequences of characters than chance alone. Tutte knew that the Tunny indicators used 25 letters (excluding J) for 11 of the positions, but only 23 letters for the other. He therefore tried Kasiski's technique on the first impulse of the key characters, using a repetition of 25 × 23 = 575. He did not observe a large number of column repetitions with this period, but he did observe the phenomenon on a diagonal. He therefore tried again with 574, which showed up repeats in the columns. Recognising that the [[prime factor]]s of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses that was replete with repetitions".<ref>{{Harvnb|Tutte|2006|pp=356–357}}</ref>

It was clear, however, that the first impulse of the key was more complicated than that produced by a single wheel of 41 key impulses. Tutte called this component of the key <math>\chi_1</math> (''chi''<sub>1</sub>). He figured that there was another component, which was XOR-ed with this, that did not always change with each new character, and that this was the product of a wheel that he called <math>\psi_1</math> (''psi''<sub>1</sub>). The same applied for each of the five impulses {{nowrap|(<math>\chi_1 \chi_2 \chi_3 \chi_4 \chi_5</math> and <math>\psi_1 \psi_2 \psi_3 \psi_4 \psi_5</math>).}} So for a single character, the whole key '''K''' consisted of two components:
<math display="block">K = \chi \oplus \psi</math>

At Bletchley Park, mark impulses were signified by '''x''' and space impulses by '''•'''.{{refn|group=nb|In more recent terminology, each impulse would be termed a "[[bit]]" with a mark being binary 1 and a space being binary 0. Punched paper tape had a hole for a mark and no hole for a space.}} For example, the letter "H" would be coded as '''••x•x'''.<ref>{{Harvnb|Copeland|2006|pp=348, 349}}</ref> Tutte's derivation of the ''chi'' and ''psi'' components was made possible by the fact that dots were more likely than not to be followed by dots, and crosses more likely than not to be followed by crosses. This was a product of a weakness in the German key setting, which they later eliminated. Once Tutte had made this breakthrough, the rest of the Research Section joined in to study the other impulses, and it was established that the five ''chi'' wheels all advanced with each new character and that the five ''psi'' wheels all moved together under the control of two ''mu'' or "motor" wheels. Over the following two months, Tutte and other members of the Research Section worked out the complete logical structure of the machine, with its set of wheels bearing cams that could either be in a position (raised) that added '''x''' to the stream of key characters, or in the alternative position that added in '''•'''.<ref>{{Harvnb|Tutte|2006|p=357}}</ref>

Diagnosing the functioning of the Tunny machine in this way was a truly remarkable cryptanalytical achievement which, in the citation for Tutte's induction as an Officer of the [[Order of Canada]], was described as "one of the greatest intellectual feats of World War II".<ref name="MacTutorBiog">{{Harvnb|O'Connor|Robertson|2003}} <!-- {{cite web | url = http://www.codesandciphers.org.uk/lorenz/fish.htm | title = The Lorenz Cipher and how Bletchley Park broke it | publisher = Codesandciphers.org.uk | date=30 August 1941 | accessdate=26 October 2011 }}--></ref>

===Tutte's statistical method===
{{See also|Cryptanalysis of the Lorenz cipher#The "1+2 break in"|label 1=Tutte's "1+2 break in"}}
To decrypt a Tunny message required knowledge not only of the logical functioning of the machine, but also the start positions of each rotor for the particular message. The search was on for a process that would manipulate the ciphertext or key to produce a frequency distribution of characters that departed from the uniformity that the enciphering process aimed to achieve. While on secondment to the Research Section in July 1942, [[Alan Turing]] worked out that the XOR combination of the values of successive characters in a stream of ciphertext and key emphasised any departures from a uniform distribution. The resultant stream (symbolised by the Greek letter "delta" '''Δ''') was called the [[Cryptanalysis of the Lorenz cipher#Differencing|difference]] because XOR is the same as modulo 2 subtraction.

The reason that this provided a way into Tunny was that although the frequency distribution of characters in the ciphertext could not be distinguished from a random stream, the same was not true for a version of the ciphertext from which the ''chi'' element of the key had been removed. This was the case because where the plaintext contained a repeated character and the ''psi'' wheels did not move on, the differenced ''psi'' character (<math>\Delta\psi</math>) would be the null character ('<span style="font-size:140%;">'''/'''</span> ' at Bletchley Park). When XOR-ed with any character, this character has no effect. Repeated characters in the plaintext were more frequent both because of the characteristics of German (EE, TT, LL and SS are relatively common),<ref>{{Citation |last=Singh |first=Simon |author-link=Simon Singh |title=The Black Chamber |url=http://www.simonsingh.net/The_Black_Chamber/hintsandtips.html |access-date=28 April 2012}}</ref> and because telegraphists frequently repeated the figure-shift and letter-shift characters.<ref>[[Max Newman|Newman]] c. 1944 p. 387</ref>

To quote the General Report on Tunny:<blockquote>Turingery introduced the principle that the key differenced at one, now called '''ΔΚ''', could yield information unobtainable from ordinary key. This '''Δ''' principle was to be the fundamental basis of nearly all statistical methods of wheel-breaking and setting.<ref name="GRoT11B6"/></blockquote>

Tutte exploited this amplification of non-uniformity in the differenced values {{refn|group=nb|For this reason Tutte's 1 + 2 method is sometimes called the "double delta" method.}} and by November 1942 had produced a way of discovering wheel starting points of the Tunny machine which became known as the "Statistical Method".<ref>{{Harvnb|Tutte|1998|pp=7–8}}</ref> The essence of this method was to find the initial settings of the ''chi'' component of the key by exhaustively trying all positions of its combination with the ciphertext, and looking for evidence of the non-uniformity that reflected the characteristics of the original plaintext.<ref>{{Harvnb|Good|Michie|Timms|1945|pp=321–322}} in ''44. Hand Statistical Methods: Setting – Statistical Methods''</ref> Because any repeated characters in the plaintext would always generate '''•''', and similarly <math>\Delta\psi_1 \oplus \Delta\psi_2</math> would generate '''•''' whenever the ''psi'' wheels did not move on, and about half of the time when they did – some 70% overall.

As well as applying differencing to the full 5-bit characters of the ITA2 code, Tutte applied it to the individual impulses (bits).{{refn|group=nb|The five impulses or bits of the coded characters are sometimes referred to as five levels.}} The current ''chi'' wheel cam settings needed to have been established to allow the relevant sequence of characters of the ''chi'' wheels to be generated. It was totally impracticable to generate the 22 million characters from all five of the ''chi'' wheels, so it was initially limited to 41 × 31 = 1271 from the first two. After explaining his findings to [[Max Newman]], Newman was given the job of developing an automated approach to comparing ciphertext and key to look for departures from randomness. The first machine was dubbed [[Heath Robinson (codebreaking machine)|Heath Robinson]], but the much faster [[Colossus computer]], developed by [[Tommy Flowers]] and using algorithms written by Tutte and his colleagues, soon took over for breaking codes.<ref>{{Harvnb|Copeland|2011}}</ref><ref>{{cite web | url=https://uwaterloo.ca/combinatorics-and-optimization/about/professor-william-t-tutte/biography-professor-tutte#bletchley | title=Biography of Professor Tutte | date=August 2002 | first=Dan | last=Younger | work=CMS Notes | via=University of Waterloo | access-date=24 June 2018 }}</ref><ref>{{Citation | last = Roberts | first = Jerry | author-link = Jerry Roberts | title = Lorenz: Breaking Hitler's top secret code at Bletchley Park | place = Stroud, Gloucestershire | publisher = The History Press | year = 2017 | isbn = 978-0-7509-7885-9}}</ref>