Description of the RSA Algorithm

THE RSA ALGORITHM

The pioneering paper by Diffie and Hellman [DIFF76b] introduced a new approach to cryptography and, in effect, challenged cryptologists to come up with a crypto- graphic algorithm that met the requirements for public-key systems. A number of algorithms have been proposed for public-key cryptography. Some ofthese, though initially promising, turned out to be breakable.4

One of the first successful responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978 [RIVE78].5 The Rivest-Shamir-Adleman (RSA) schemehas since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption.

The RSA scheme is a block cipher in which the plaintext and ciphertext are integers between 0 and n - 1 forsome n. A typical size for n is 1024 bits, or 309 dec- imal digits. That is, n is less than 21024. We examineRSA in this section in some detail, beginning with an explanation of the algorithm. Then we examine some of the computational and cryptanalytical implications of RSA.

Description of the Algorithm

RSA makes use of an expression with exponentials. Plaintext is encrypted in blocks, with each blockhaving a binary value less than some number n. That is, the block size must be less than or equal to log2(n)+ 1; in practice, the block size is i bits, where 2i 6 n £ 2i+1. Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C.

C  =  Me mod n

M  = Cd mod n  = 1Me  d mod n  = Med mod   n

Both sender and receiver must know the value of n. The sender knows the value of e, and only thereceiver knows the value of d. Thus, this is a public-key encryption algorithm with a public key of PU ={e, n} and a private key of PR = {d, n}. For this algorithm to be satisfactory for public-key encryption, the following require- ments must be met.

1.                                                                   It is possible to find values of e, d, n such that Med mod n = M for all M <  n.

2.                                                                   It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n.

3.                                                                   It is infeasible to determine d given e and n.

For now, we focus on the first requirement and consider the other questions later. We need to find a relationship of the form

Med mod n = M

The  preceding relationship holds if  e  and  d  are  multiplicative inverses  modulo

ϕ(n), where ϕ(n) is the Euler totient function. It is shown in Chapter 8 that for p, q prime, ϕ (pq) = (p - 1)(q - 1). The relationship between e and d can be expressed as

ed mod ϕ(n) = 1 (9.1)

This is equivalent to saying

That is, e and d are multiplicative inverses mod ϕ(n). Note that, according to the rules of modular arithmetic, this is true only if d (and therefore e) is relatively prime to ϕ(n). Equivalently, gcd(ϕ(n), d) = 1. SeeAppendix 9A for a proof that Equation (9.1) satisfies the requirement for RSA.

We are now ready to state the RSA scheme. The ingredients are the following:

p, q, two prime numbers               (private, chosen)

n = pq                                           (public, calculated)

e, with gcd(ϕ(n), e) = 1; 1 < e < ϕ(n)        (public, chosen)

d K e-1 (mod ϕ(n))                        (private, calculated)

The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A has published its public key and that user B wishes to send the message  M to A. Then B calculates C = Me mod n and transmits C. On receipt of this cipher- text, user A decrypts by calculating M = Cd mod  n.

Figure 9.5 summarizes the RSA algorithm. It corresponds to Figure 9.1a: Alice generates a public/private keypair; Bob encrypts using Alice’s public key; and Alice decrypts using her private key. An example from[SING99] is shown in Figure 9.6. For this example, the keys were generated as follows.

1.                                     Select two prime numbers, p = 17 and q = 11.

2.                                     Calculate n = pq = 17 ´ 11 = 187.

3.  Calculate ϕ(n) = (p - 1)(q - 1) = 16 ´ 10 = 160.

4.                  Select e such that e is relatively prime to ϕ(n) = 160 and less than f(n); we choose e = 7.

5.                  Determine d such that de K 1 (mod 160) and d < 160. The correct value is d = 23, because 23 ´ 7 = 161 =(1 ´ 160) + 1; d can be calculated using the extended Euclid’s algorithm (Chapter 4).

The resulting keys are public key PU = {7, 187} and private key PR = {23, 187}. The example shows the use ofthese keys for a plaintext input of M = 88. For encryp- tion, we need to calculate C = 887 mod 187. Exploiting the properties of modular arithmetic, we can do this as follows.

887 mod 187 = [(884 mod 187) ´ (882 mod 187)

´ (881 mod 187)] mod 187

881 mod 187 = 88

882 mod 187 = 7744 mod 187 =  77

884 mod 187 = 59,969,536 mod 187 =  132

887 mod 187 = (88 ´ 77 ´ 132) mod 187 = 894,432 mod 187 =   11

For decryption, we calculate M = 1123 mod 187:

1123 mod 187 = [(111 mod 187) ´ (112 mod 187) ´ (114 mod 187)

´ (118 mod 187) ´ (118 mod 187)] mod 187

111 mod 187 = 11

112 mod 187 = 121

114 mod 187 = 14,641 mod 187 =  55

118 mod 187 = 214,358,881 mod 187 =  33

1123 mod 187 = (11 ´ 121 ´ 55 ´ 33 ´ 33) mod 187 = 79,720,245 mod 187 =   88

We now look at an example from [HELL79], which shows the use of RSA to process multiple blocks ofdata. In this simple example, the plaintext is an alphanumeric string. Each plaintext symbol is assigneda unique code of two decimal digits (e.g., a = 00, A = 26).6 A plaintext block consists of four decimal digits, or two alphanumeric characters. Figure 9.7a illustrates the sequence   of events for theencryption of multiple blocks, and Figure 9.7b gives a specific example. The circled numbers indicatethe order in which operations are performed.

Computational Aspects

We now turn to the issue of the complexity of the computation required to use RSA. There are actually two issues to consider: encryption/decryption and key genera- tion. Let us look first at the process of encryptionand decryption and then consider key generation.

EXPONENTIATION IN MODULAR ARITHMETIC Both encryption and decryption in RSA involve raising aninteger to an integer power, mod n. If the exponentiation is done over the integers and then reduced modulon, the intermediate values would be gargantuan. Fortunately, as the preceding example shows, we can makeuse of a property of modular arithmetic:

[(a mod n) * (b mod n)] mod n = (a * b) mod n

Thus, we can reduce intermediate results modulo n. This makes the calculation practical.

Another consideration is the efficiency of exponentiation, because with RSA, we are dealing with potentially large exponents. To see how efficiency might be increased, consider that we wish to computex16. A straightforward approach requires 15 multiplications:

x16 = x * x * x * x * x * x * x * x * x * x * x * x * x * x * x * x

However, we can achieve the same final result with only four multiplications if we repeatedly take thesquare of each partial result, successively forming (x2, x4, x8, x16). As another example, suppose we wish tocalculate x11 mod n for some integers x and

n. Observe that x11 = x1+2+8 = (x)(x2)(x8). In this case, we compute x mod n, x2 mod n, x4 mod n, and x8 mod nand then calculate [(x mod n) ´ (x2 mod n) ´ (x8 mod n)] mod n.

More generally, suppose we wish to find the value ab with a and m positive integers. If we express b as a binary number bkbk-1. . . b0, then we   have

We can therefore develop the algorithm7 for computing ab mod n, shown in Figure 9.8. Table 9.4 shows anexample of the execution of this algorithm. Note that the variable c is not needed; it is included forexplanatory purposes. The final value of c is the value of the exponent.

EFFICIENT OPERATION USING THE PUBLIC KEY To  speed up the operation of the  RSA algorithm using the public key, a specific choice of e is usually made. The most common choice is 65537 (216 + 1); two other popular choices are 3 and 17. Each of these choices has only two 1 bits, so the number of multiplications required to perform  exponentiation  is minimized.

However, with a very small public key, such as e = 3, RSA becomes vulnerable to a simple attack. Supposewe have three different RSA users who all use the value e = 3 but have unique values of n, namely (n1, n2,n3). If user A sends the same encrypted message M to all three users, then the three ciphertexts are C1 = M3mod n1, C2 = M3 mod n2, and C3 = M3 mod n3. It is likely that n1, n2, and n3 are pairwise rela- tively prime.Therefore, one can use the Chinese remainder theorem (CRT) to com- pute M3 mod (n1n2n3). By the rules ofthe RSA algorithm, M is less than each of the ni; therefore M3 < n1n2n3. Accordingly, the attacker need only compute the cube root of M3. This attack can be countered by adding a unique pseudorandom bit string aspadding to each instance of M to be encrypted. This approach is discussed subsequently.

The reader may have noted that the definition of the RSA algorithm (Figure 9.5) requires that during keygeneration the user selects a value of e that is relatively prime to f(n).Thus, if a value of e is selected first andthe primes p and q are generated, it may turn out that gcd(f(n), e)  Z  1. In that case, the user must reject thep, q values and generate a new p, q pair.

Table 9.4   Result of the Fast Modular Exponentiation Algorithm for ab mod n, where a = 7,

b = 560 = 1000110000, and n = 561

EFFICIENT OPERATION USING THE PRIVATE KEY We cannot similarly choose a small constant value of d for efficient operation. A small value of d is vulnerable to a brute- force attack and to other forms ofcryptanalysis [WIEN90]. However, there is a way to speed up computation using the CRT. We wish to compute the value M = Cd mod n. Let us define the following intermediate results:

Vp  = Cd mod p    Vq  = Cd mod q

Following the CRT using Equation (8.8), define the quantities

Xp = q * (q - 1 mod p)  Xq = p * (p - 1 mod q)

The CRT then shows, using Equation (8.9), that

M  =  (Vp Xp  +  Vq Xq) mod n

Furthermore, we can simplify the calculation of Vp and Vq using Fermat’s theorem, which states that ap-1 K1 (mod p) if p and a are relatively prime. Some thought should convince you that the following are valid.

Vp = Cd mod p = Cd mod (p - 1) mod p        Vq = Cd mod q = Cd mod (q - 1) mod q

The quantities d mod (p - 1) and d mod (q - 1) can be precalculated. The end result is that the calculation isapproximately four times as fast as evaluating M = Cd mod n directly [BONE02].

KEY GENERATION Before the application of the public-key cryptosystem, each participant must generate a pair of keys. This involves the following tasks.

•                       Determining two prime numbers, p and q.

•                       Selecting either e or d and calculating the   other.

First, consider the selection of p and q. Because the value of n = pq will be known to any potential adversary, in order to prevent the discovery of p and q by exhaustive methods, these primes must be chosenfrom a sufficiently large set (i.e., p and q must be large numbers). On the other hand, the method used forfinding large primes must be reasonably efficient.

At present, there are no useful techniques that yield arbitrarily large primes, so some other means oftackling the problem is needed. The procedure that is generally used is to pick at random an odd number of the desired order of magni- tude and test whether that number is prime. If not, pick successive randomnumbers until one is found that tests prime.

A variety of tests for primality have been developed (e.g., see [KNUT98] for a description of a number ofsuch tests). Almost invariably, the tests are prob- abilistic. That is, the test will merely determine that agiven integer is probably prime. Despite this lack of certainty, these tests can be run in such a way as tomake the probability as close to 1.0 as desired. As an example, one of the more efficient and popularalgorithms, the Miller-Rabin algorithm, is described in Chapter 8. With this algorithm and most suchalgorithms, the procedure for test- ing whether a given integer n is prime is to perform some calculationthat involves n and a randomly chosen integer a. If n “fails” the test, then n is not prime. If n “passes”the test, then n may be prime or nonprime. If n passes many such tests with many different randomly chosen values for a, then we can have high confidence that n is, in fact, prime.

In summary, the procedure for picking a prime number is as follows.

1.                                     Pick an odd integer n at random (e.g., using a pseudorandom number generator).

2.                                     Pick an integer a < n at random.

3.                                     Perform the probabilistic primality test, such as Miller-Rabin, with a as a parameter. If n fails the test, reject thevalue n and go to step 1.

4.                                     If n has passed a sufficient number of tests, accept n; otherwise, go to step 2.

This is a somewhat tedious procedure. However, remember that this process is performed relatively infrequently: only when a new pair (PU, PR) is needed.

It is worth noting how many numbers are likely to be rejected before a prime number is found. A result fromnumber theory, known as the prime number theorem, states that the primes near N are spaced on the average one every (ln N) integers. Thus, on average, one would have to test on the order of ln(N) integers before a prime is found. Actually, because all even integers can be immediately rejected, the

correct figure is ln(N)/2. For example, if a prime on the order of magnitude of 2200 were sought, then about ln(2200)/2 = 70 trials would be needed to find a prime.

Having determined prime numbers p and q, the process of key generation is completed by selecting a value of e and calculating d or, alternatively, selecting a value of d and calculating e. Assuming the former, thenwe need to select an e such that gcd(f(n), e) = 1 and then calculate d K e-1 (mod f(n)). Fortunately, there isa single algorithm that will, at the same time, calculate the greatest common divisor of two integers and, if thegcd is 1, determine the inverse of one of the integers modulo the other. The algorithm, referred to as theextended Euclid’s algorithm, is explained in Chapter 4. Thus, the procedure is to generate a series ofrandom num- bers, testing each against f(n) until a number relatively prime to f(n) is found. Again, wecan ask the question: How many random numbers must we test to find a usable number, that is, a numberrelatively prime to f(n)? It can be shown easily that the probability that two random numbers are relativelyprime is about 0.6; thus, very few tests would be needed to find a suitable integer (see Problem 8.2).