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

Let us formalize the procedure.

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 .

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 .

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 . Thus, the private key is sometimes defined as the triple .

In the example below, we also briefly indicate how more sophisticated number theory can shorten the calculations.

Suppose Bob chooses the primes and . So , and . A valid choice for is 7, as . Using the Euclidean Algorithm, Bob can also calculate (see Chapter 19). Bob announces his public key and finds . Bob keeps secret. When Alice wants to send to Bob, she computes using the repeated squaring method to find that . Alice then transmits in public, and when Bob receives it, he can either compute directly using the repeated squaring technique, or take a more efficient approach, as follows: Bob calculates and , then uses the Chinese Remainder Theorem (of Chapter 19) to combine them to find . Since , Bob knows that , and by a theorem due to Fermat 2 this is equal to . Similarly, . Bob then combines and to find .