Cryptography: Theory and Practice:The RSA System and Factoring | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

4.2 More Number Theory

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.

4.2.1 The Euclidean Algorithm

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 r₀ and r₁, where r₀ > r₁. The Euclidean algorithm consists of performing the following sequence of divisions:

Then it is not hard to show that

Hence, it follows that gcd(r₀, r₁) = r_m.

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 r₀ = n and r₁ = b. However, it does not compute the value of the multiplicative inverse (if it exists).

Now, suppose we define a sequence of numbers t₀, t₁, . . ., t_m according to the following recurrence (where the q_j’s are defined as above):

Then we have the following useful result.

THEOREM 4.1

For 0 ≤ j ≤ m, we have that r_j ≡ t_jr₁ (mod r₀), where the q_j’s and r_j’s are defined as in the Euclidean algorithm, and the t_j’s 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(r₀, r₁) = 1. Then t_m = r₁^-1 mod r₀.

Now, the sequence of numbers t₀ , t₁, . . . t_m can be calculated in the Euclidean algorithm at the same time as the q_j’s and the r_j’s. 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 q_j’s, r_j’s and t_j’s, 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

Table of Contents