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

Скачать книгу

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 upper M from upper C by calculating d: 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 upper M cannot be obtained from upper C in a reasonable amount of time by some method or another. We point out also that given d we can find p comma q, even when d is chosen so that Rem left-bracket e d comma t right-bracket equals 1, where left-parenthesis p minus 1 right-parenthesis divides t and left-parenthesis q minus 1 right-parenthesis divides t. (See Buchmann [Buc04]). Thus, the problem of finding dis 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 upper N. Let the message be some number upper M between 0 and upper N minus 1, i.e. 0 less-than-or-equal-to upper M less-than-or-equal-to upper N minus 1. Our enciphering algorithm now reads: “increase upper M by 7 and get the cipher text upper C by calculating the remainder upon division by upper N.” For example if upper N is 55 and upper M equals 50, then upper C equals 2. 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 upper C,” i.e. “add the inverse of 7 to upper C.” We do this now. First, we must get the additive inverse of 7 modulo upper N i.e., the inverse of 7 modulo 55 (see Chapter 19). In other words, we must find d such that d plus 7 leaves a remainder 0 when divided by 55. In this case, d is 48. Then, to decipher upper C, we increase upper C left-parenthesis equals 2 right-parenthesis 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)
bulletB selects in private two large primes p, q with p not-equals q and sets upper N equals p q. bulletA and B publicly choose any positive integer upper N.
bulletA chooses a message upper M, 0 less-than-or-equal-to upper M less-than-or-equal-to upper N minus 1. bulletA chooses a message upper M, 0 less-than-or-equal-to upper M less-than-or-equal-to upper N minus 1.
bulletB chooses any positive enciphering index e with gcd left-parenthesis e comma left-parenthesis p minus 1 right-parenthesis left-parenthesis q minus 1 right-parenthesis right-parenthesis equals 1 and 1 less-than-or-equal-to e less-than left-parenthesis p minus 1 right-parenthesis left-parenthesis q minus 1 right-parenthesis. bulletA and B secretly agree on an enciphering indexe between 0 and upper N minus 1.
bulletA forms the cipher text upper C, where upper C is the remainder when Скачать книгу