The mathematician who won the War

“Mathematicians won the War.” So begins A Beautiful Mind, and it’s a commonly heard line. Of course it wasn’t really mathematicians who primarily won World War II. However, if any mathematician deserves some major credit, it’s Alan Turing.

This has been a big year for Turing fans. It’s the centenary of Alan Turing’s birth and he has been honoured far and wide for his stunning achievements: his brilliant work in mathematical logic (now available in Lego); his role in the birth of the computer; and yes, his winning the war.

During World War II Alan Turing was one of Britain’s leading cryptanalysts. He played a pivotal role in countering the famous Enigma machine, enabling the allies to decipher German communications. That was a decisive advantage in the battle for the Atlantic.

But what exactly did Turing do to crack the Enigma? We’ll try to give some indication of the astonishing difficulty of the task and how brilliant, and how mathematical, Turing and his colleagues were.

One of the simplest ways to encrypt a message is by what’s known as a substitution cipher. (Cryptanalyst fusspots frown upon using the word "code" here). For this cipher a substitution key is used to replace each occurrence of a letter by a new specified letter. For example, with the key

the word MATHEMATICS would be encrypted as OEPQLOEPVMS. To decrypt the word you simply apply the key in reverse.

Unfortunately (or fortunately, depending upon who’s doing the encrypting), substitution ciphers are very easy to crack. In common speech, different letters and letter combinations are used with predictably different frequencies. This makes it easy to make plausible guesses of how some letters or words are encrypted.

The Enigma machine was just a trifle more sophisticated, as indicated in the following diagram. 

Each of the three rotors has contacts on the left and right, which are connected by wires in a fixed but seemingly random manner; the effect is that each rotor provides a substitution cipher. As well, each rotor can be set to any of the 26 letters of the alphabet.

There were a number of versions of the Enigma machine. For the version pictured, the encrypter chose three rotors from the five available, all differently wired. That gave a total of

 5 x 4 x 3 x 26 x 26 x 26 = 1,054,560

possible starting positions for the rotors.

But wait, there’s more. On the plugboard, ten pairs of letters are connected by wires. It’s more involved to calculate but it turns out there are

 150,738,274,937,250

possible settings for the plugboard. Finally, we multiply the rotor and plugboard possibilities to give the astronomical number of ways to set up the Enigma machine:

 158,962,555,217,826,360,000

Every day, the Germans would switch their machines to a new setting. Messages were then encrypted by typing on the keyboard. As each letter was typed an electric current flowed from the letter through the plugboard, through the rotors, through some internal (but permanent) scrambling, back through the rotors in reverse order, and finally back through the plugboard again to a different letter on the keyboard. This final letter would light up on the lampboard, indicating the encrypted letter.

Although incredibly complicated, all this scrambling simply amounted to a substitution cipher. However, with every keystroke the right rotor shifted forward by one letter, resulting in a different substitution cipher. Similarly, the middle rotor advanced one letter with every 26 keystrokes, and the left rotor advanced one letter with every 26 x 26 keystrokes.

The result was that every letter of the message was encrypted with a different substitution cipher. But the Germans who received the message could decipher it simply by setting their Enigma machine to the same setting and typing in the enciphered text. Ingenious.

So how could the allies unravel such an insanely complicated encryption? The answer is that they couldn’t have.

Luckily, Turing and his colleagues were able to build upon the brilliant pre-war work of Polish cryptanalysts. The Polish had access to a commercial precursor of the Enigma. With this knowledge and by some incredibly involved deductions, they were then able to determine the mechanism of an early version of the Enigma, lacking a plugboard.

Consequently, the allies could replicate the workings of the Enigma. That meant that to decipher a message they only had to work through the different possible starting positions, to see which would spit out German text. Of course, with over a hundred quintillion starting positions to check, that was going to take some time.  

The allies built banks of Enigma machines that would run in parallel and could cycle through the million rotor settings in a few hours. But what to do about the 150 trillion plugboard settings that could be paired with each rotor setting?

That's when ingenuity took over from brute force. The British cryptanalysts found a brilliant method that would rule out almost all of the plugboard settings (for a given rotor setting) in an easy, mechanical manner.

A critical insight (also known to the Polish cryptanalysts) was the realisation that a letter never came out of the Enigma machine the same as it went in: whatever the setting, each letter was encrypted into something new. That doesn't seem like it would be a huge help, but it was paired with another natural and powerful idea.

Depending upon the source of an encrypted message, the allies always had a good idea of some of the words it contained. For example, if they had a report intercepted from a German weather station then it was a good bet that the German word WETTER (= weather) would appear at least once in the message. And, because every letter of the word had to be encrypted to something new, the word could only occur in certain parts of the encrypted message.

That was the set-up for a beautiful logical argument, a proof by contradiction. Supposing the rotors were in position AAA, the allies would consider the consequences of WETTER appearing at a certain spot in the encrypted text, say encrypted as ETRZYX. They knew how the rotors in position AAA scrambled the letters, and so the question was how the plugboard might be wired up.

The plugboard either left the letter W unchanged or it swapped W with a new letter. In either case, Turing and co. could chase the consquences of that assumption to see how W could have been converted into an E. 

That would then give a clue as to how the E (the second letter of Wetter) could be turned into T, and the T into R, and so on.

What they hoped for was to run into a dead-end, the chain of reasoning leading to a contradiction in the wiring of the plugboard. For example, as pictured, though it might have initially been assumed that W was to remain unchanged by the plugboard, the reasoning may have then led to the impossible conclusion that the plugboard also had to swap W and T. It would then instantly follow that zillions of plugboard configurations were impossible. Then the cryptanalysts could move onto consideration of rotor position AAB, then AAC and so on. 

It still appears that the decryption would involve the slow and painful checking of a huge number of possibilities. However the method was so beautifully simple and clear in its logic that it could all be done electronically: the checking was effectively done by clicking a switch. And it worked.

So, Alan Turing won the war, invented computers and lived happily ever after. What a heart-warming story.

Well, not quite. During his lifetime, Turing was never officially or publicly recognized for his work during the War. And, though it now seems unbelievable, in 1952 Turing was convicted of "gross indecency" for a homosexual relationship. He consequently suffered all manner of indignities.

Alan Turing died in 1954, possibly by suicide, 58 years short of his 100th birthday. A brilliant mathematician, and a truly tragic life.

Burkard Polster teaches mathematics at Monash and is the university's resident mathemagician, mathematical juggler, origami expert, bubble-master, shoelace charmer, and Count von Count impersonator.

Marty Ross is a mathematical nomad. His hobby is smashing calculators with a hammer.

www.qedcat.com

Copyright 2004-∞ All rights reserved.