href="#fb3_img_img_fd94de72-51ed-51df-93e7-f9284279e8b2.png" alt="p comma q comma e"/> 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 findingis 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
