Engines of Our Ingenuity

No. 2666
ALAN TURING

by Krešimir Josić

Today codes, ciphers and Alan Turing. The University of Houston Mathematics Department presents this program about the machines that make our civilization run, and the people whose ingenuity created them.

We have to keep military communications secret in any war. Many codes have been used to do so. Simple substitution ciphers have been around for more than 2500 years. To encrypt information with such ciphers simply replace one letter of the alphabet with another. For instance, we can replace all letters A in a message with the letter Z, and all Bs with Ys. The recipient has our list of substitutions, and simply reverses them.

The World War II German military used the most sophisticated codes of that time. Their Enigma machine also replaced each letter by another letter. However, depressing a key on an Enigma machine moved several internal rotors. This caused the substitution of each letter to depend on the sequence of letters that preceded it. As a result, the letter A would not always be replaced by the same letter. Moreover, the setting of the machines was changed daily. The Germans were certain that their communications were secure. They thought the Enigma Machine would allow them to pass secret war plans right under the Allies’ noses.

Yet, a British team of code breakers, led by the 29 year-old Alan Turing, achieved the impossible. Even if you captured a German machine you couldn’t yet break the code. As Germans changed the settings daily, the code needed to be broken anew, and quickly! Humans are too slow for the task. Using insights provided by Polish intelligence, Turing devised an electro-mechanical machine that could rapidly crack the code.

electromechanical machine

The war of wits between the sides continued until the British won it decisively. Without the secrets they uncovered, German U-Boats would’ve choked the lifeline that stretched across the Atlantic. Churchill told King George VI that their work was instrumental in winning the war. However, their contributions remained largely secret until the ‘90s.

German submarine U-Boat hit
A hit and sinking German U-Boat

Alan Turing was the father of computer science. His automation of the code-breaking effort inspired his ideas about intelligent machines. His work on computation has shaped computer science ever since. Computer scientists have named their highest award, their version of the Nobel, the Turing Award.

Alan TuringTuring’s story has a tragic ending. After he admitted to being a homosexual, he was charged under the same statute as Oscar Wilde half a century earlier. His security clearance was revoked, and he was forced to undergo damaging physical treatments. He ended his life by eating a cyanide laced apple at the age of 41. In 2009, the British Prime Minister, Gordon Brown, apologized for this abominable treatment.

Alan Turing was one of the greatest minds of the 20th century. His insights were fundamental in the development of automated computing. They also help us understand the workings of our own minds. Tragically, his contributions were cut short by a very human shortcoming — prejudice.

This is Krešimir Josić at the University of Houston, where we are interested in the way inventive minds work.

(Theme music)


Gordon Brown’s apology to Alan Turing is discussed here http://news.bbc.co.uk/2/hi/
technology/8249792.stm
.

Andrew Hogdes, the author of Alan Turing: The Enigma, also maintains a website devoted to Turing at http://www.turing.org.uk/turing/. It contains a short biography.

Here is a description of the Enigma machine, and the discussion of its complexity http://www.nsa.gov/about/_files/cryptologic_heritage/publications/wwii/
engima_cryptographic_mathematics.pdf
.

Here is a recording of a nice lecture about Turing and his contributions at MIT http://mitworld.mit.edu/video/423.

All images are in the Creative Commons library.

After this episode aired, Mr. Jarek Garlinski wrote to clarify the Polish contribution to the breaking of the Enigma code. He notes that their contributions in breaking the Enigma were crucial. However, it is also important to note that Alan Turing devised completely new approaches for the breaking of the naval Enigma, as well as the Lorenz, and other ciphers.

Quoting Mr. Garlinski:

In 1932, a team of Polish cryptanalysts, working for Polish Military Intelligence, including the mathematician Marian Rejewski and his colleagues Henryk Zygalski and Jerzy Rózycki, succeeded in breaking the German Enigma coding machine. The Poles had been working for some time on breaking German codes, approaching the problem from its mathematical side. Earlier than most, the Polish Intelligence Service had recognised the need to employ in their code-breaking organisations mathematicians and engineers, as opposed, for instance, to classicists, linguists or crossword puzzle experts, as did the British.

Then, in late 1938, the Polish team came up with the idea of mechanising the process by creating an electro-mechanical device, that they called a ‘bombe’ (bomba in Polish and supposedly named after an ice cream bombe), which was in essence the equivalent of six Enigma machines connected in pairs in order to speed up the laborious process of examining every permutation of the rotors. This work formed the basis of Turing’s subsequent work and he even adopted the name ‘bombe’, as the photograph above shows.

The Poles then went on to produce an Enigma machine and in July 1939, just before the outbreak of the Second World War, they presented two copies of this machine, one to the British and one to the French. The French did little with theirs, while the British, to their credit, did a great deal. However, it is only at this stage, and not before, that Turing and his team of Cambridge mathematicians enter the picture. Turing’s great achievement was to build on these earlier conceptual breakthroughs and to devise electro-mechanical machinery which could run through the possible permutations at a high enough speed to allow the resulting intelligence product to be still relevant. In simple terms, there was little point in breaking encoded transmissions on U-boat deployments, for example, three weeks after the fact!

The British were stunned by the Polish breakthrough and freely admitted that, without the vital insights of the Zygalski team, their own work would have been delayed by some years. Dillwyn Knox, one the British cryptanalysts to whom the Poles presented an Enigma machine in Poland in July 1939,


The Engines of Our Ingenuity is Copyright © 1988-2010 by John H. Lienhard.