Number Theory Il For example, suppose that the secret key is the prime number k= 22801763489 and the message m is"victory". Then the encrypted message is: =2209032015182513·22801763489 50369825549820718594667857 There are a couple questions one might naturally ask about Turings code 1. How can the sender and receiver ensure that m and k are prime numbers, as re- uired? The general problem of determining whether a large number is prime or compos ite has been studied for centuries, and reasonably good primality tests were known even in Turing s time. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Sax ena announced a primality test that is guaranteed to work on a number n in about (log n)steps. This definitively placed primality testing in the class of"easy"com- putational problems at last. Amazingly, the description of their breakthrough algo- rithm was only thirteen lines long! 2. Is Turings code secure? The Nazis see only the encrypted message m=m-k, so recovering the original mes- sage m requires factoring m*. Despite immense efforts, no really efficient factoring algorithm has ever been found. It appears to be a fundamentally difficult problem, though a breakthrough someday is not impossible. In effect, Turing s code puts to practical use his discovery that there are limits to the power of computation. Thus, provided m and k are sufficiently large, the Nazis seem to be out of luck! This all sounds promising, but there is a major flaw in Turings code 1.2 Breaking Turings Code Let's consider what happens when the sender transmits a second message using Turings code and the same key. This gives the Nazis two encrypted messages to look at: m1=m1·k and m2=m2·k The greatest common divisor of the two encrypted messages, mi and mp, is the secret key k. And, as weve seen, the gcd of two numbers can be computed very efficiently. So after the second message is sent, the Nazis can read recover the secret key and read every It is difficult to believe a mathematician as brilliant as Turing could overlook such glaring problem. One possible explanation is that he had a slightly different system mind, one based on modular arithmeticNumber Theory II 3 For example, suppose that the secret key is the prime number k = 22801763489 and the message m is “victory”. Then the encrypted message is: m∗ = m k· = 2209032015182513 · 22801763489 = 50369825549820718594667857 There are a couple questions one might naturally ask about Turing’s code. 1. How can the sender and receiver ensure that m and k are prime numbers, as re￾quired? The general problem of determining whether a large number is prime or compos￾ite has been studied for centuries, and reasonably good primality tests were known even in Turing’s time. In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Sax￾ena announced a primality test that is guaranteed to work on a number n in about (log n)12 steps. This definitively placed primality testing in the class of “easy” com￾putational problems at last. Amazingly, the description of their breakthrough algo￾rithm was only thirteen lines long! 2. Is Turing’s code secure? The Nazis see only the encrypted message m∗ = m·k, so recovering the original mes￾sage m requires factoring m∗. Despite immense efforts, no really efficient factoring algorithm has ever been found. It appears to be a fundamentally difficult problem, though a breakthrough someday is not impossible. In effect, Turing’s code puts to practical use his discovery that there are limits to the power of computation. Thus, provided m and k are sufficiently large, the Nazis seem to be out of luck! This all sounds promising, but there is a major flaw in Turing’s code. 1.2 Breaking Turing’s Code Let’s consider what happens when the sender transmits a second message using Turing’s code and the same key. This gives the Nazis two encrypted messages to look at: m∗ = m1 · k and m∗ 1 2 = m2 · k The greatest common divisor of the two encrypted messages, m∗ and m∗ 2, is the secret 1 key k. And, as we’ve seen, the gcd of two numbers can be computed very efficiently. So after the second message is sent, the Nazis can read recover the secret key and read every message! It is difficult to believe a mathematician as brilliant as Turing could overlook such a glaring problem. One possible explanation is that he had a slightly different system in mind, one based on modular arithmetic