Скачать книгу
alt="d"/>
. 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 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 Fermat2 this is equal to . Similarly, . Bob then combines and to find .
Remark 3.4
Note in the above that is divisible by .
In general, suppose are not divisible by , and assume that is divisible by . Then . Therefore, upon multiplying both sides by .
Remark 3.5
Instead of using 461047 as the deciphering index, Bob can calculate that the least common multiple of and is . Then he can find that the remainder of when divided by is 1, where , and use this for a deciphering index instead.
It is conceivable that the RSA problem of obtaining from is easier than the factoring problem. For some methods of obtaining from that work in special cases, we refer to the problems. The factoring problem is to obtain given . Once
Скачать книгу
