Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 62

A (=Alice) wants to send a secret message to B (=Bob). Bob has already chosen two large unequal prime¹ numbers and . Bob multiplies and together to get . Bob also chooses some integer bigger than 1. The integer ( for enciphering) must have no factors in common with and no factors in common with . In other words, the greatest common divisor of and is 1 (and similarly for and ). In symbols, we write and . Thus, the only number dividing both and is 1, and the only number dividing both and is 1. We say also that is relatively prime to and to . It follows that .

Because of the conditions imposed on , namely that is relatively prime to , there exists a unique integer ( for deciphering) which is greater than 1 but less than and is such that the remainder of when divided by is 1. It is easy for Bob to calculate , 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 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.