alt="d"/>, 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 whenis 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
Ifare odd, thenare even, and so each is divisible by 2. So by choosingto be the least common multiple ofand, we get that.
Remark 3.3
It is beneficial for Bob to also storeandrather than just. The reason is that some decryption algorithms work faster if he makes use ofandrather than just
