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

Читать онлайн книгу.

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


Скачать книгу
Thus, y 1 equals y 2 (and so also z 1 equals z 2): end of story. As a consequence, to check Eq. (3.5) in the future all we need to do in the case above is to ensure that 279 936 minus z is divisible by 55.

      Getting back to our main narrative, A transmits the cipher text bold upper C equals 41 to B having calculated this from the message upper M equals 6. How does B recover upper M from 41? B knows that upper N equals 55 equals left-parenthesis 5 right-parenthesis left-parenthesis 11 right-parenthesis. Since we are using a public cryptosystem, the enciphering algorithm is public knowledge (in this particular example), the enciphering algorithm is “multiply the message by itself seven times and take the remainder on division by upper N”: this gives the cipher text 41. B calculates the deciphering index d as follows.

      There is a unique positive integer d between 1 and 39 such that 7 d gives a remainder of 1 when divided by 40. In this case, it turns out that d equals 23 (more on this later) since left-parenthesis 7 right-parenthesis left-parenthesis 23 right-parenthesis equals 161 and 161 leaves a remainder of 1 on division by 40. Here, 40 comes from the fact that left-parenthesis 11 minus 1 right-parenthesis left-parenthesis 5 minus 1 right-parenthesis equals 40 and 5, 11 are the factors of upper N equals 55.

      To recover the message, B multiplies the cipher text, namely 41, by itself 23 times, gets the remainder on division by 55, and this should give the original message, namely 6. So we are claiming that 4 1 Superscript 23 minus 6 is divisible by 55.

       We will use the following principle to get the remainder of a product of two numbers.

      Let us calculate 4 1 Superscript 23 and get the remainder upon division by 55.

      In detail, x Superscript 1 Baseline equals 41, nothing more to do. Then, x squared equals 4 1 squared equals 1681 gives a remainder of 31 when divided by 55. Proceeding, instead of calculating x Superscript 4 Baseline equals 168 1 squared by squaring x squared, we need only calculate 3 1 squared and get the remainder on division by 55 which is 26. Now, to get the next term in the product (namely x Superscript 16) instead of squaring x Superscript 4to get x Superscript 8and then squaring again to get x Superscript 16we need only square 26, get the remainder and square the remainder again and finally get the remainder on division by 55 which is 36. So the four remainders for x comma x squared comma x Superscript 4 Baseline comma x Superscript 16 are 41, 31, 26, 36. In principle, now we have to multiply 41 by 31 by 26 by 36 and get the remainder on division by 55. Again, we can take shortcuts using Principle 2. We can multiply 41 by 31 and get the remainder. We calculate left-parenthesis 26 right-parenthesis left-parenthesis 36 right-parenthesis and get the remainder (on division by 55). Multiplying the 2 remainders together, and getting the remainder, on division by 55, gives us the answer. The two remainders are 6 and 1. Then left-parenthesis 6 right-parenthesis left-parenthesis 1 right-parenthesis equals 6 and B ends up recovering the message which is 6. Note that in the example above, upper N is the product p q of two distinct primes p and q with p equals 11 and q equals 5. The enciphering index e is 7, M is 6, the cipher text upper C is 41, and the deciphering index Скачать книгу