Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

, using a method related to the Euclidean Algorithm (see Chapter 19), since Bob knows which are the factors of . There may be other deciphering indices that are easier to work with (see Remark 3.1 part 2 and a more general method in item 3 of the formal algorithm overleaf).

      Bob puts the numbers and in a public directory under his name. He keeps secret the primes and : is Bob's private key and the pair is Bob's public key.

Now, Alice has a secret message to transmit to Bob. Alice converts to a number between 1 and represented in binary (which we also denote by ). If is too large, Alice breaks into blocks, each of which is less than . Let us assume, for simplicity, that is less than . Then, Alice enciphers by calculating the cipher text . Note that Remmeans the remainder when is divided by , so in other words Alice multiplies by itself times and gets the remainder upon division by . This can be done quickly using the “repeated squaring” method and the principle described earlier. Note that can be any positive integer relatively prime to and . However, suppose . Then it can be shown that , and so we may as well assume that .

      When Bob receives , he in turn multiplies by itself times and gets the remainder upon division by . As explained in our earlier example, the calculation can be simplified. This remainder is in fact equal to , the original message.

      Let us formalize the procedure.

      The RSA Algorithm.

      1 Bob chooses in secret two large primes with and sets .

      2 Bob chooses bigger than 1 with relatively prime to and to , and with .

      3 Bob calculates the decryption index , where is such that the remainder of on division by is 1. More generally, Bob calculates a decryption index , where is such that the remainder of on division by is 1. Here, is any number divisible by both and .

      4 Bob announces his public key and keeps his private key secret.

      5 Alice wishes to send a secret message and represents as a number between 0 and . Alice then encrypts the message as the remainder of upon division by and transmits to Bob.

      6 Bob decrypts by calculating the remainder of upon division by : this gives the original secret message .

      Remark 3.2

      If are odd, then are even, and so each is divisible by 2. So by choosing to be the least common multiple of and , we get that .

      Remark 3.3

It is beneficial for Bob to also store and rather than just . The reason is that some decryption algorithms work faster if he makes use of and rather than just