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

Читать онлайн книгу.

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


Скачать книгу
alt="d"/>, using a method related to the Euclidean Algorithm (see Chapter 19), since Bob knows p comma q which are the factors of upper N. 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 e and upper N left-parenthesis equals p q right-parenthesis in a public directory under his name. He keeps secret the primes p and q: d is Bob's private key and the pair left-bracket upper N comma e right-bracket is Bob's public key.

      When Bob receives upper C equals upper M Superscript e, he in turn multiplies upper C by itself d times and gets the remainder upon division by upper N. As explained in our earlier example, the calculation can be simplified. This remainder is in fact equal to upper M, 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 p comma q are odd, then p minus 1 comma q minus 1 are even, and so each is divisible by 2. So by choosing t to be the least common multiple of p minus 1 and q minus 1, we get that t less-than-or-equal-to left-parenthesis p minus 1 right-parenthesis left-parenthesis q minus 1 right-parenthesis slash 2.

      Remark 3.3