As we have seen, d can be the reciprocal of e, modulo (p-1)(q-1). Where p and q are two large primes, neither one is equal to 2, and so p-1 and q-1 will have 2 as a common factor. Thus, the reciprocal of e modulo (p-1)(q-1)/2 will also work. If p-1 and q-1 have other common factors, then they too can be divided out before the reciprocal of e is calculated. Using values of p and q such that p-1 and q-1 have many common factors creates a risk that raising an encrypted plaintext to the e power again a few times will yield the original plaintext, since when there are common factors to remove from (p-1)(q-1), the result is a smaller number.
This is one reason to choose 'strong' primes. Even if the current fastest methods of factoring do not benefit from having a prime that is not strong, weak primes benefit other attacks on RSA.
A common choice for e (or d in the case of a signature key; for whichever exponent is made public) is one of the following numbers: 3, 5, 17, 257, or 65537, to make exponentiation (the procedure for which is discussed in the next section) particularly speedy and convenient, since to raise a number to the power of one of these exponents, one simply needs to multiply the number by the result of squaring it one or more times.
If p and q have been specifically chosen to both be of the form 2r+1, where r is another large prime, then if e is any small prime (other than 2) there will be no problem with it not being relatively prime to (p-1)(q-1)/2. Otherwise, that e and this modulus are relatively prime will have to be checked. This can be done using Euclid's algorithm.
It turns out that when e is tested against a modulus using Euclid's algorithm, the information needed to find d is generated. But d itself isn't produced unless extra steps are taken to put that information to use. And so the procedure for testing if e is relatively prime to (p-1)(q-1)/2 will be carried out even when it is already known that they are relatively prime, in order to obtain d, the decryption exponent.
Euclid's algorithm for finding the greatest common divisor of two numbers works like this:
First, let b be the larger of the two numbers, and s the smaller. (In this particular case, (p-1)(q-1)/2 will be the starting value of b, and e will be the starting value of s.)
Divide b by s, and note the remainder, r. The new b will be the old s, and the new s will be r. Repeat until r is zero; the value of r in the preceding step will be the greatest common divisor. If r becomes one, you can stop early, knowing that the two numbers had 1 as their greatest common divisor, since dividing any integer by 1 will produce a remainder of zero, which means they were relatively prime.
If two numbers are successfully proven to be relatively prime, the reciprocal of the original s modulo the original b can be obtained as follows from the intermediate values encountered in performing Euclid's algorithm:
It is desired to find an equation of the form 1=s(0)*d-b(0)*n, where s(0)=e and b(0)=(p-1)(q-1)/2, and n is an arbitrary integer.
If it is in step i that dividing b by s yields 1 as the remainder, then that means that b(i)-s(i)*q(i)=1, where q(i) is the quotient of the division at step i. So, when we use Euclid's algorithm to determine inverses, we will need to retain not just the values of b and s for each step, but also the quotient at each step, in an array that we will treat like a stack.
From the outline of Euclid's algorithm above, s(i-1)=b(i); r(i-1)=s(i); and b(i-1)-s(i-1)*q(i-1)=r(i-1).
Therefore,
(1) b(i)-s(i)*q(i)=1
yields
(2) s(i-1)-r(i-1)*q(i)=1
by substituting the previous names for the values. Using the equation for the previous division step,
(3) b(i-1)-s(i-1)*q(i-1)=r(i-1)
to replace r(i-1) in equation (2), we obtain
(4) s(i-1)-(b(i-1)-s(i-1)*q(i-1))*q(i)=1
Collecting terms, equation (4) then becomes
(5) -q(i)*b(i-1)+(1+q(i)*q(i-1))*s(i-1)=1
Using s(i-2)=b(i-1), r(i-2)=s(i-1), and b(i-2)=s(i-2)*q(i-2)=r(i-2), we can again substitute in the equation to obtain 1 as the sum of a multiple of b(i-2) and s(i-2), and we repeat the process going back to b(0) and s(0) to find our answer. But it is necessary to work with the equations; the formulas above are only valid for i being the number of the step yielding 1 as the remainder, they are not recurrence relations.
Next
Chapter Start
Skip to Next Section
Table of Contents
Home Page