3.1.5 How large a key should be used in the RSA cryptosystem?
The size of a key in the RSA algorithm typically refers to the size of the modulus n. The two primes, p and q, which compose the modulus, should be of roughly equal length; this makes the modulus harder to factor than if one of the primes is much smaller than the other. If one chooses to use a 768-bit modulus, the primes should each have length approximately 384 bits. If the two primes are extremely close1 or their difference is close to any predetermined amount, then there is a potential security risk, but the probability that two randomly chosen primes are so close is negligible.
The best size for a modulus depends on one's security needs. The larger the modulus, the greater the security, but also the slower the RSA algorithm operations. One should choose a modulus length upon consideration, first, of the value of the protected data and how long it needs to be protected, and, second, of how powerful one's potential threats might be.
A good analysis of the security obtained by a given modulus length is given by Rivest [Riv92a], in the context of discrete logarithms modulo a prime, but it applies to the RSA algorithm as well. A more recent study of RSA key-size security can be found in an article by Odlyzko [Odl95]. Odlyzko considers the security of RSA key sizes based on factoring techniques available in 1995 and on potential future developments, and he also considers the ability to tap large computational resources via computer networks. In 1997, a specific assessment of the security of 512-bit RSA keys shows that one may be factored for less than $1,000,000 in cost and eight months of effort [Rob95c]. Indeed, the 512-bit number RSA-155 was factored in seven months during 1999 (see Question 2.3.6). This means that 512-bit keys no longer provide sufficient security for anything more than very short-term security needs.
RSA Laboratories currently recommends key sizes of 1024 bits for corporate use and 2048 bits for extremely valuable keys like the root key pair used by a certifying authority (see Question 126.96.36.199). Several recent standards specify a 1024-bit minimum for corporate use. Less valuable information may well be encrypted using a 768-bit key, as such a key is still beyond the reach of all known key breaking algorithms. Lenstra and Verheul [LV00] give a model for estimating security levels for different key sizes, which may also be considered.
It is typical to ensure that the key of an individual user expires after a certain time, say, two years (see Question 188.8.131.52). This gives an opportunity to change keys regularly and to maintain a given level of security. Upon expiration, the user should generate a new key being sure to ascertain whether any changes in cryptanalytic skills make a move to longer key lengths appropriate. Of course, changing a key does not defend against attacks that attempt to recover messages encrypted with an old key, so key size should always be chosen according to the expected lifetime of the data. The opportunity to change keys allows one to adapt to new key size recommendations. RSA Laboratories publishes recommended key lengths on a regular basis.
Users should keep in mind that the estimated times to break the RSA system are averages only. A large factoring effort, attacking many thousands of moduli, may succeed in factoring at least one in a reasonable time. Although the security of any individual key is still strong, with some factoring methods there is always a small chance the attacker may get lucky and factor some key quickly.
As for the slowdown caused by increasing the key size (see Question 3.1.2), doubling the modulus length will, on average, increase the time required for public key operations (encryption and signature verification) by a factor of four, and increase the time taken by private key operations (decryption and signing) by a factor of eight. The reason public key operations are affected less than private key operations is that the public exponent can remain fixed while the modulus is increased, whereas the length of the private exponent increases proportionally. Key generation time would increase by a factor of 16 upon doubling the modulus, but this is a relatively infrequent operation for most users.
It should be noted that the key sizes for the RSA system (and other public-key techniques) are much larger than those for block ciphers like DES (see Section 3.2), but the security of an RSA key cannot be compared to the security of a key in another system purely in terms of length.
1 Put m = [(p+q)/ 2]. With p < q, we have 0 £ m- Ön £ [((q-p)2)/( 8p)]. Since p = m ±Ö[(m2-n)], the primes p and q can be easily determined if the difference p-q is small.