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

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 are known, it is easy to find the message from by calculating : this is what Bob does. Mathematically, nobody has been able to prove that the factoring problem cannot be solved in a reasonable amount of time. Similarly, it has not been shown that cannot be obtained from in a reasonable amount of time by some method or another. We point out also that given we can find , even when is chosen so that , where divides and divides . (See Buchmann [Buc04]). Thus, the problem of finding is equivalent to the factoring problem.

Let us return again to our example of symmetric key encryption where the enciphering algorithm was “add 7.” In order to avoid overflow and storage, we fix a large positive integer . Let the message be some number between 0 and , i.e. . Our enciphering algorithm now reads: “increase by 7 and get the cipher text by calculating the remainder upon division by .” For example if is 55 and , then . So A transmits the cipher text 2. Now, B must undo (or decrypt or decipher) 2 to get the original message. Before, our decryption algorithm read “subtract 7 from ,” i.e. “add the inverse of 7 to .” We do this now. First, we must get the additive inverse of 7 modulo i.e., the inverse of 7 modulo 55 (see Chapter 19). In other words, we must find such that leaves a remainder 0 when divided by 55. In this case, is 48. Then, to decipher , we increase by 48 and obtain the remainder upon division by 55. In this case, we obtain the number 50. This is the original message.

The kind of procedure just described seems remarkably similar to the RSA algorithm. A summary is as follows:

RSA Algorithm (Outline)	Symmetric Algorithm (Outline)
B selects in private two large primes , with and sets .	A and B publicly choose any positive integer .
A chooses a message , .	A chooses a message , .
B chooses any positive enciphering index with and .	A and B secretly agree on an enciphering index between 0 and .
A forms the cipher text , where is the remainder when is divided by .	A forms the cipher text , where is the remainder when is divided by .
Let be the multiplicative inverse of modulo , so that leaves a remainder of 1 upon division by . Then, to decipher, B raises to the power and gets the remainder of upon division by .	Let be the additive inverse of modulo . Then, to decipher, B adds to and gets the remainder of upon division by : this yields .