Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 60

How do we know that is unique? Maybe there are two possible values?

Go back to Eq. (3.5), and suppose we have two solutions with being positive and and both lying between 0 and 54. So we have

(3.8)

(3.9)

Then . Now, if it follows that . So assume that . Call the larger one , so .

We now have . Since is at least 1 bigger than , we get that the left side is at least 55. Since and are between 0 and 54, we see that the right side is at most 54. Since , we conclude that the assumption leads to a contradiction. Thus, (and so also ): 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 is divisible by 55.

Getting back to our main narrative, A transmits the cipher text to B having calculated this from the message . How does B recover from 41? B knows that . 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 ”: this gives the cipher text 41. B calculates the deciphering index as follows.

There is a unique positive integer between 1 and 39 such that gives a remainder of 1 when divided by 40. In this case, it turns out that (more on this later) since and 161 leaves a remainder of 1 on division by 40. Here, 40 comes from the fact that and 5, 11 are the factors of .

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 is divisible by 55.

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

Principle 2 Calculate the product of the two individual remainders and then get its remainder, if necessary.

If we calculate – or in general any – on a calculator or a computer, we run into overflow problems. To avoid them, we use this principle, combined with the repeated squaring method. Here is how this method works in the present case. We first express 23 as a sum of powers of 2. Thus, . So if is any number, we have . Each number in this product is the square of the previous number except for which is the square of the square of the previous number.

Let us calculate and get the remainder upon division by 55.

In detail, , nothing more to do. Then, gives a remainder of 31 when divided by 55. Proceeding, instead of calculating by squaring , we need only calculate and get the remainder on division by 55 which is 26. Now, to get the next term in the product (namely ) instead of squaring – to get – and then squaring again to get – we 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 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 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 and B ends up recovering the message which is 6. Note that in the example above, is the product of two distinct primes and with and . The enciphering index is 7, M is 6, the cipher text is 41, and the deciphering index is 23.

Several remarks are in order.