8.8: Turing’s Code (Version 2.0)
- Page ID
- 48338
In 1940, France had fallen before Hitler’s army, and Britain stood alone against the Nazis in western Europe. British resistance depended on a steady flow of supplies brought across the north Atlantic from the United States by convoys of ships. These convoys were engaged in a cat-and-mouse game with German “U-boats” —submarines—which prowled the Atlantic, trying to sink supply ships and starve Britain into submission. The outcome of this struggle pivoted on a balance of information: could the Germans locate convoys better than the Allies could locate U-boats, or vice versa?
Germany lost.
A critical reason behind Germany’s loss was not made public until 1974: Germany’s naval code, Enigma, had been broken by the Polish Cipher Bureau,9 and the secret had been turned over to the British a few weeks before the Nazi invasion of Poland in 1939. Throughout much of the war, the Allies were able to route convoys around German submarines by listening in to German communications. The British government didn’t explain how Enigma was broken until 1996. When the story was finally released (by the US), it revealed that Alan Turing had joined the secret British codebreaking effort at Bletchley Park in 1939, where he became the lead developer of methods for rapid, bulk decryption of German Enigma messages. Turing’s Enigma deciphering was an invaluable contribution to the Allied victory over Hitler.
Governments are always tight-lipped about cryptography, but the half-century of official silence about Turing’s role in breaking Enigma and saving Britain may be related to some disturbing events after the war—more on that later. Let’s get back to number theory and consider an alternative interpretation of Turing’s code. Perhaps we had the basic idea right (multiply the message by the key), but erred in using conventional arithmetic instead of modular arithmetic. Maybe this is what Turing meant:
Beforehand The sender and receiver agree on a large number \(n\), which may be made public. (This will be the modulus for all our arithmetic.) As in Version 1.0, they also agree that some prime number \(k < n\) will be the secret key.
Encryption As in Version 1.0, the message \(m\) should be another prime in \([0..n)\). The sender encrypts the message \(m\) to produce \(\hat{m}\) by computing \(mk\), but this time modulo \(n\):
\[\hat{m} ::= m \cdot k (\mathbb{Z}_n) \]
Decryption (Uh-oh.)
The decryption step is a problem. We might hope to decrypt in the same way as before by dividing the encrypted message \(\hat{m}\) by the key \(k\). The difficulty is that \(\hat{m}\) is the remainder when \(mk\) is divided by \(n\). So dividing \(\hat{m}\) by \(k\) might not even give us an integer!
This decoding difficulty can be overcome with a better b understanding of when it is ok to divide by \(k\) in modular arithmetic.