Number Theory Il 3.4 Breaking Turing s Code- Again German weather reports were not encrypted with the highly-secure Enigma system. After all, so what if the allies learned that there was rain off the south coast of Iceland? But amazingly, this practice provided the British with a critical edge in the Atlantic naval battle during 1941 The problem was that some of those weather reports had originally been transmitted from U-boats out in the Atlantic. Thus, the British obtained both unencrypted reports and the same reports encrypted with Enigma. By comparing the two, the British were able to determine which key the germans were using that day and could read all other Enigma-encoded traffic Today, this would be called a known-plaintext attack Let's see how a known-plaintext attack would work against Turing s code. Suppose that the nazis know both m and m' where m≡mk(modp) Now they can comput mP.m*=mp-(mk rem p)(mod p (def. of m") mP-2·mk(modp) (part 2 of Lemma 2) ≡m-1k(modp) (simplification) ≡k(modp) Now the Nazis have the secret key k and can decrypt any message This is a huge vulnerability, so Turings code has no practical value. Fortunately, Tur ing got better at cryptography after devising this code; his subsequent cracking of Enigma surely saved thousands of lives if not the whole of Britain 4 Postscrip A few years after the war, Turings home was robbed. Detectives soon determined that a former homosexual lover of Turing s had conspired in the robbery. So they arrested him that is, they arrested alan turing. Because at that time, homosexuality was a crime in Britain, punishable by up to two years in prison. Turing was sentenced to a humiliating hormonal"treatment"for his homosexuality: he was given estrogen injections. He began to develop breasts Three years later, Alan Turing the founder of computer science, was dead. His mother explained what happened in a biography of her own son. Despite her repeated warnings, Turing carried out chemistry experiments in his own home. Apparently, her worst fear was realized: by working with potassium cyanide while eating an apple, he poisoned10 Number Theory II 3.4 Breaking Turing’s Code— Again German weather reports were not encrypted with the highly­secure Enigma system. After all, so what if the Allies learned that there was rain off the south coast of Iceland? But, amazingly, this practice provided the British with a critical edge in the Atlantic naval battle during 1941. The problem was that some of those weather reports had originally been transmitted from U­boats out in the Atlantic. Thus, the British obtained both unencrypted reports and the same reports encrypted with Enigma. By comparing the two, the British were able to determine which key the Germans were using that day and could read all other Enigma­encoded traffic. Today, this would be called a known­plaintext attack. Let’s see how a known­plaintext attack would work against Turing’s code. Suppose that the Nazis know both m and m∗ where: m∗ ≡ mk (mod p) Now they can compute: mp−2 m∗ ≡ mp−2 · (mk rem p) (mod p) (def. of m∗ · ) ≡ mp−2 · mk (mod p) (part 2 of Lemma 2) ≡ mp−1 · k (mod p) (simplification) ≡ k (mod p) (Fermat’s Theorem) Now the Nazis have the secret key k and can decrypt any message! This is a huge vulnerability, so Turing’s code has no practical value. Fortunately, Tur￾ing got better at cryptography after devising this code; his subsequent cracking of Enigma surely saved thousands of lives, if not the whole of Britain. 4 Postscript A few years after the war, Turing’s home was robbed. Detectives soon determined that a former homosexual lover of Turing’s had conspired in the robbery. So they arrested him; that is, they arrested Alan Turing. Because, at that time, homosexuality was a crime in Britain, punishable by up to two years in prison. Turing was sentenced to a humiliating hormonal “treatment” for his homosexuality: he was given estrogen injections. He began to develop breasts. Three years later, Alan Turing, the founder of computer science, was dead. His mother explained what happened in a biography of her own son. Despite her repeated warnings, Turing carried out chemistry experiments in his own home. Apparently, her worst fear was realized: by working with potassium cyanide while eating an apple, he poisoned himself