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

Because of the conditions imposed on , namely that is relatively prime to , there exists a unique integer ( for deciphering) which is greater than 1 but less than and is such that the remainder of when divided by is 1. It is easy for Bob to calculate , 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.1part 2and 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 Rem means 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.