William Thomas Tutte (; 14 May 1917 – 2 May 2002) was an English and Canadian code breaker and mathematician. During the Second World War, he made a fundamental advance in cryptanalysis of the Lorenz cipher, a major Nazi German cipher system which was used for top-secret communications within the Wehrmacht High Command.
The high level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages specifically, contributed greatly, and perhaps even decisively, to the defeat of Nazi Germany. He also had a number of significant mathematical accomplishments, including foundational work in the fields of graph theory and matroid theory.
Tutte's research in the field of graph theory proved to be of remarkable importance. At a time when graph theory was still a primitive subject, Tutte commenced the study of matroids and developed them into a theory by expanding from the work that Hassler Whitney had first developed around the mid-1930s. Even though Tutte's contributions to graph theory have been influential to modern graph theory and many of his theorems have been used to keep making advances in the field, most of his terminology was not in agreement with their conventional usage and thus his terminology is not used by graph theorists today. "Tutte advanced graph theory from a subject with one text (D. Kőnig's) toward its present extremely active state."
Tutte was born in Newmarket in Suffolk. He was the younger son of William John Tutte (1873–1944), an estate gardener, and Annie (née Newell; 1881–1956), a housekeeper. Both parents worked at Fitzroy House stables where Tutte was born. The family spent some time in Buckinghamshire, County Durham, and Yorkshire before returning to Newmarket, where Tutte attended Cheveley Church of England primary school in the nearby village of Cheveley. In 1927, when he was ten, Tutte was awarded a scholarship to the Cambridge and County High School for Boys. He took up his place there in 1928.
In 1935, he won a scholarship to study natural sciences at Trinity College, Cambridge, where he specialized in chemistry and graduated with first-class honours in 1938. He continued with physical chemistry as a graduate student, but transferred to mathematics at the end of 1940. As a student, Tutte and three of his friends were one of the first to solve the problem of squaring the square, and the first to solve the problem without a squared subrectangle. Together the four created the pseudonym Blanche Descartes, under which Tutte published occasionally for years.
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 Hagelin cipher that was being used by the Italian Navy. This was a 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.
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 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 SZ machines and the traffic that they enciphered.
Telegraphy used the 5-bit International Telegraphy Alphabet No. 2 (ITA2). Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12-letter 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. Tutte's breakthroughs led eventually to bulk decrypting of Tunny-enciphered messages between the German High Command (OKW) in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany.
On 31 August 1941, two versions of the same message were sent using identical keys, which constituted a "depth". This allowed John Tiltman, Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a Vernam cipher which uses the 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".
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. 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 factors 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".
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
(chi1). 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
(psi1). The same applied for each of the five impulses (
{\displaystyle \chi _{1}\chi _{2}\chi _{3}\chi _{4}\chi _{5}}
{\displaystyle \psi _{1}\psi _{2}\psi _{3}\psi _{4}\psi _{5}}
). So for a single character, the whole key K consisted of two components:
{\displaystyle K=\chi \oplus \psi }
At Bletchley Park, mark impulses were signified by x and space impulses by •. For example, the letter "H" would be coded as ••x•x. 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 •.