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

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 directly using the repeated squaring technique, or take a more efficient approach, as follows: Bob calculates and , then uses the Chinese Remainder Theorem (of Chapter 19) to combine them to find . Since , Bob knows that , and by a theorem due to Fermat² this is equal to . Similarly, . Bob then combines and to find .