rel="nofollow" href="#fb3_img_img_6e526cfc-c043-519e-9784-cc23fa133695.png" alt="left-bracket bold-italic u bold-italic comma bold-italic v right-bracket"/>means 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. Thus, the private key is sometimes defined as the triple.
Another example of the RSA algorithm
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
rel="nofollow" href="#fb3_img_img_6e526cfc-c043-519e-9784-cc23fa133695.png" alt="left-bracket bold-italic u bold-italic comma bold-italic v right-bracket"/>means the remainder when 