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

Чтение книги онлайн.

СКАЧАТЬ 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 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 . 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 СКАЧАТЬ