Aiden A. Bruen - Cryptography, Information Theory, and Error-Correction

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 .

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 problemof 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 Atransmits the cipher text 2. Now, Bmust 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.