How Large a Modulus (Key) Should be Used in RSA?

The best size for an RSA modulus depends on one's security needs. The larger the modulus, the greater the security, but also the slower the RSA operations. One should choose a modulus length upon consideration, first, of one's security needs, such as the value of the protected data and how long it needs to be protected, and, second, of how powerful one's potential enemies are.

Odlyzko's paper considers the security of RSA key sizes based on factoring techniques available in 1995 and the ability to tap large computational resources via computer networks. 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 in 1997 [Rob95d]. It is believed that 512-bit keys no longer provide sufficient security with the advent of new factoring algorithms and distributed computing. Such keys should not be used after 1997 or 1998. Recommended key sizes are now 768 bits for personal use, 1024 bits for corporate use, and 2048 bits for extremely valuable keys like the key pair of a certifying authority (see Question 123). A 768-bit key is expected to be secure until at least the year 2004.

The key of an individual user may expire after a certain time, say, two years (see Question 118). This gives an opportunity to change keys regularly and thus maintain a given level of security. Upon expiration, the user should generate a new key which is at least a few digits longer than the old key to reflect the speed increases of computers and factoring algorithms over the two years. Recommended key length schedules are published by RSA Laboratories on a regular basis.

Users should keep in mind that the estimated times to break RSA are averages only. A large factoring effort, attacking many thousands of RSA 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 that the attacker may get lucky and factor some key quickly.

As for the slowdown caused by increasing the key size (see Question 9), 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. (This assumes typical methods for RSA implementation, not "fast multiplication.") The reason that public-key operations are affected less than private-key operations is that the public exponent can remain fixed when the modulus is increased, whereas 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. (The impact of key size increases other than doubling can be calculated similarly.)