alt="0 less-than-or-equal-to upper M less-than-or-equal-to upper N minus 1"/>. 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 .
