![]() |
Cryptography: Theory and Practice
by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Before describing how RSA works, we need to discuss some more facts concerning modular arithmetic and number theory. Two fundamental results that we require are the Euclidean algorithm and the Chinese remainder theorem.
We already observed in Chapter 1 that is a ring for any positive integer n. We also proved there that
has a multiplicative inverse if and only if gcd(b, n) = 1, and that the number of positive integers less than n and relatively prime to n is φ(n).
The set of residues modulo n that are relatively prime to n is denoted . It is not hard to see that
forms an abelian group under multiplication. We already have stated that multiplication modulo n is associative and commutative, and that 1 is the multiplicative identity. Any element in
will have a multiplicative inverse (which is also in
). Finally,
is closed under multiplication since xy is relatively prime to n whenever x and y are relatively prime to n (prove this!).
At this point, we know that any has a multiplicative inverse, b-1, but we do not yet have an efficient algorithm to compute b-1. Such an algorithm exists; it is called the extended Euclidean algorithm.
First, we describe the Euclidean algorithm, in its basic form, which is used to compute the greatest common divisor of two positive integers, say r0 and r1, where r0 > r1. The Euclidean algorithm consists of performing the following sequence of divisions:
Then it is not hard to show that
Hence, it follows that gcd(r0, r1) = rm.
Since the Euclidean algorithm computes greatest common divisors, it can be used to determine if a positive integer b < n has a multiplicative inverse modulo n, by starting with r0 = n and r1 = b. However, it does not compute the value of the multiplicative inverse (if it exists).
Now, suppose we define a sequence of numbers t0, t1, . . ., tm according to the following recurrence (where the qjs are defined as above):
Then we have the following useful result.
THEOREM 4.1
For 0 ≤ j ≤ m, we have that rj ≡ tjr1 (mod r0), where the qjs and rjs are defined as in the Euclidean algorithm, and the tjs are defined in the above recurrence.
PROOF The proof is by induction on j. The assertion is trivially true for j = 0 and j = 1. Assume the assertion is true for j = i - 1 and i - 2, where i ≥ 2; we will prove the assertion is true for j = i. By induction, we have that
and
Now, we compute:
Hence, the result is true by induction.
The next corollary is an immediate consequence.
COROLLARY 4.2
Suppose gcd(r0, r1) = 1. Then tm = r1-1 mod r0.
Now, the sequence of numbers t0 , t1, . . . tm can be calculated in the Euclidean algorithm at the same time as the qjs and the rjs. In Figure 4.1, we present the extended Euclidean algorithm to compute the inverse of b modulo n, if it exists. In this version of the algorithm, we do not use an array to keep track of the qjs, rjs and tjs, since it suffices to remember only the last two terms in each of these sequences at any point in the algorithm.
In step 10 of the algorithm, we have written the expression for temp in such a way that the reduction modulo n is done with a positive argument. (We mentioned earlier that modular reductions of negative numbers yield negative results in many computer languages; of course, we want to end up with a positive result here.) We also mention that at step 12, it is always the case that tb ≡ r (mod n) (this is the result proved in Theorem 4.1).
Here is a small example to illustrate:
Example 4.1
Suppose we wish to compute 28-1 mod 75. The Extended Euclidean algorithm proceeds as follows:
Hence, 28-1 mod 75 = 67.
Figure 4.1 Extended Euclidean algorithm
Previous | Table of Contents | Next |