RSA encryption in practice
There are numerous ways of speeding up RSA encryption and decryption in software and hardware implementations. Some of these techniques are covered in Chapter 14, including fast modular multiplication (§14.3), fast modular exponentiation (§14.6), and the use of the Chinese remainder theorem for faster decryption (Note 14.75). Even with these improvements, RSA encryption/decryption is substantially slower than the commonly used symmetric-key encryption algorithms such as DES (Chapter 7). In practice, RSA encryption is most commonly used for the transport of symmetric-key encryption algorithm keys and for the encryption of small data items.
The RSA cryptosystem has been patented in the U.S. and Canada. Several standards organizations have written, or are in the process of writing, standards that address the use of the RSA cryptosystem for encryption, digital signatures, and key establishment. For discussion of patent and standards issues related to RSA, see Chapter 15.
- 8.7 Note (recommended size of modulus) Given the latest progress in algorithms for factoring integers (§3.2), a 512-bit modulus n provides only marginal security from concerted attack. As of 1996, in order to foil the powerful quadratic sieve (§3.2.6) and number field sieve (§3.2.7) factoring algorithms, a modulus n of at least 768 bits is recommended. For longterm security, 1024-bit or larger moduli should be used.
- 8.8 Note (selecting primes)
- (i) As mentioned in §8.2.2(i), the primes p and q should be selected so that factoring n = pq is computationally infeasible. The major restriction on p and q in order to avoid the elliptic curve factoring algorithm (§3.2.4) is that p and q should be about the same bitlength, and sufficiently large. For example, if a 1024-bit modulus n is to be used, then each of p and q should be about 512 bits in length.
- (ii) Another restriction on the primes p and q is that the difference p - q should not be too small. If p - q is small, then p ss q and hence p as sfn. Thus, n could be factored efficiently simply by trial division by all odd integers close to фх. If p and q are chosen at random, then p — q will be appropriately large with overwhelming probability.
- (iii) In addition to these restrictions, many authors have recommended that p and q be strong prunes. A prune p is said to be a strong prime (cf. Definition 4.52) if the following three conditions are satisfied:
- (a) p — 1 has a large prime factor, denoted r;
- (b) p + 1 has a large prime factor; and
- (c) v — 1 has a large prime factor.
An algorithm for generating strong primes is presented in §4.4.2. The reason for condition (a) is to foil Pollard’s p— 1 factoring algorithm (§3.2.3) which is efficient only if n has a prime factor p such that p - 1 is smooth. Condition (b) foils the p + 1 factoring algorithm mentioned on page 125 in §3.12, which is efficient only if n has a prime factor p such that p + 1 is smooth. Finally, condition (c) ensures that the cycling attacks described in §8.2.2(vii) will fail.
If the prime p is randomly chosen and is sufficiently large, then both p — 1 and p+ 1 can be expected to have large prime factors. In any case, while strong primes protect against the p - 1 and p+1 factoring algorithms, they do not protect against their generalization, the elliptic curve factoring algorithm (§3.2.4). The latter is successful in factoring n if a randomly chosen number of the same size as p (more precisely, this number is the order of a randomly selected elliptic curve defined over Zp) has only small prime factors. Additionally, it has been shown that the chances of a cycling attack succeeding are negligible if p and q are randomly chosen (cf. §8.2.2(vii)). Tims, strong primes offer little protection beyond that offered by random primes. Given the current state of knowledge of factoring algorithms, there is no compelling reason for requiring the use of strong primes in RSA key generation. On the other hand, they are no less secure than random primes, and require only minimal additional running time to compute; thus there is little real additional cost in using them.
- 8.9 Note (small encryption exponents)
- (i) If the encryption exponent e is chosen at random, then RSA encryption using the repeated square-and-multiply algorithm (Algorithm 2.143) takes к modular squarings and an expected k/2 (less with optimizations) modular multiplications, where к is the bitlength of the modulus n. Encryption can be sped up by selecting e to be small and/or by selecting e with a small number of 1 ’s in its binary representation.
- (ii) The encryption exponent e = 3 is commonly used in practice; in this case, it is necessary that neither p— 1 nor q - 1 be divisible by 3. This results in a very fast encryption operation since encryption only requires 1 modular multiplication and 1 modular squaring. Another encryption exponent used in practice is e = 216 + 1 = 65537. This number has only two 1 ’s in its binary representation, and so encryption using the repeated square-and-multiply algorithm requires only 16 modular squarings and 1 modular multiplication. The encryption exponent e = 216 + 1 has the advantage over e = 3 in that it resists the kind of attack discussed in §8.2.2(ii), since it is unlikely the same message will be sent to 216 +1 recipients. But see also Coppersmith’s attacks mentioned on pages 313-314.