Number Theory II ness of number theory. He forsaw that preserving military secrets would be vital in the coming conflict and proposed a way to encrypt communications using number theory. This is an idea that has ricocheted up to our own time. Today, number theory is the basis for numerous public-key cryptosystems, digital signature schemes, cryptographic hash functions, and digital cash systems. Every time you buy a book from Amazon, check your grades on WebsIs, or use a PayPal account, you are relying on number theoretic algorithms Soon after devising his code, Turing disappeared from public view, and half a centur ould pass before the world learned the full story of where he'd gone and what he did there. Well come back to Turings life in a little while; for now, let's investigate the code Turing left behind. The details are uncertain, since he never formally published the idea so well consider a couple possibilities 1.1 Turing s Code(version 1.0) The first challenge is to translate a text message into an integer so we can perform math ematical operations on it. This step is not intended to make a message harder to read, so the details are not too important. Here is one approach: replace each letter of the message with two digits(A=01, B=02,C=03, etc. and string all the digits together to form one huge number. For example, the message""could be translated this way c t o 90320151825 Turings code requires the message to be a prime number, so we may need to pad the result with a few more digits to make a prime. In this case, appending the digits 13 gives the number 2209032015182513, which is prime Now here is how the encryption process works. In the description below, m is the unencoded message(which we want to keep secret), m* is the encrypted message(which the Nazis may intercept), and k is the key Beforehand The sender and receiver agree on a secret key, which is a large prime k Encryption The sender encrypts the message m by computing m=m·k Decryption The receiver decrypts m* by computing k-m2 Number Theory II ness of number theory. He forsaw that preserving military secrets would be vital in the coming conflict and proposed a way to encrypt communications using number theory. This is an idea that has ricocheted up to our own time. Today, number theory is the basis for numerous public­key cryptosystems, digital signature schemes, cryptographic hash functions, and digital cash systems. Every time you buy a book from Amazon, check your grades on WebSIS, or use a PayPal account, you are relying on number theoretic algorithms. Soon after devising his code, Turing disappeared from public view, and half a century would pass before the world learned the full story of where he’d gone and what he did there. We’ll come back to Turing’s life in a little while; for now, let’s investigate the code Turing left behind. The details are uncertain, since he never formally published the idea, so we’ll consider a couple possibilities. 1.1 Turing’s Code (Version 1.0) The first challenge is to translate a text message into an integer so we can perform math￾ematical operations on it. This step is not intended to make a message harder to read, so the details are not too important. Here is one approach: replace each letter of the message with two digits (A = 01, B = 02, C = 03, etc.) and string all the digits together to form one huge number. For example, the message “victory” could be translated this way: “v i c t o r y” → 22 09 03 20 15 18 25 Turing’s code requires the message to be a prime number, so we may need to pad the result with a few more digits to make a prime. In this case, appending the digits 13 gives the number 2209032015182513, which is prime. Now here is how the encryption process works. In the description below, m is the unencoded message (which we want to keep secret), m∗ is the encrypted message (which the Nazis may intercept), and k is the key. Beforehand The sender and receiver agree on a secret key, which is a large prime k. Encryption The sender encrypts the message m by computing: m∗ = m k· Decryption The receiver decrypts m∗ by computing: m∗ m k = · = m k k