following principle to get the remainder of a product of two numbers.
Principle 2Calculate 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 worksin the present case. We first express 23 as a sum of powers of 2. Thus,. So ifis any number, we have. Each number in this product is the square of the previous number except forwhich is the square of the square of the previous number.
Let us calculateand 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 calculatingby squaring, we need only calculateand 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 forare 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 calculateand 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. Thenand B ends up recovering the message which is 6. Note that in the example above,is the productof two distinct primes and withand. Theenciphering indexis 7, M is 6, the cipher textis 41, and thedeciphering indexis 23.
1 The fact that B deciphers to recover the message by simply using the deciphering algorithm explained above is proved in Chapter 19.
2 Having found a decryption index by the official (hard) way, let us find an easier method. All we need is the unique integer, let us call it , between 1 and 20, such that gives a remainder of 1 when divided by 20. Why 20? Well, instead of using , we can use any positive integer divisible by both and . With and , we choose the number 20, and get . Then it is easy to check that the remainder of upon division by 55 is 6. It is much easier to use the decryption index 3 instead of the decryption index 23.
3 The security of RSA rests on the mathematically unproven assumption that, even given , , , an individual (other than B) cannot recover in a reasonable amount of time if and are large.
In technical language, the problem of recovering is said to be computationally infeasible (= infeasible) or intractable. The enciphering function transforming is conjectured to be a one‐way function, i.e. it is easy to calculate given , but it is impossible to undo this calculation.
Given and the two factors of it is easy to calculate and thus to obtain from (see Chapter 19). Thus, if one can solve the problem of factoring quickly one can calculate quickly and thus
СКАЧАТЬ
