RSA key lengths
When you create an RSA key pair, you specify a key length in bits, as generally
you would for other algorithms. Specifically, the key length of an RSA key
specifies the number of bits in the modulus. In our
RSA encryption example, we specified a key length
of 2048 bits. But in practice, what RSA key length should we choose?
First the short answer:
- a RSA key length of 1024 bits is sufficient for many medium-security purposes
such as web site logins;
- for high-security applications1 or for data that needs to remain
confidential for more than a few years, you should use at least a 2048-bit key,
and consider having a contingency plan for migrating to larger key sizes;
- to keep data confidential for more than the next two decades,
RSA recommends a key size larger than 2048 bits (see below).
So, why not just make the key much longer, say 4096 bits or even 8192 bits?
Well, as usual, there's no such thing as a free lunch. A larger key increases
the maximum number of bytes that we can encrypt at once, and also the
security of the encryption. But it has a serious problem in practice:
With every doubling of the RSA key length, decryption is 6-7 times times slower.
Figure 1 shows how decryption time increases with modulus length. The timings
were made on a 2GHz Pentium.
Figure 1: RSA decryption time by key length.
The key length also affects the speed of encryption, but it's usually the
speed of decryption that we're more concerned about because (a) that's
the part that takes place on the server, and (b) decryption is much much slower
than encryption, because the decryption exponent is huge (whereas the encryption
exponent is typically small).
If we use a 4096-bit modulus, it takes around a second of CPU time to decrypt a
block of data. Even if you were able to sacrifice this amount of CPU to every log on,
it leaves us with the problem that an attacker can effectively burn a second of CPU
time on our server by firing some random data at it. With a 1024-bit key length,
decryption takes just 25 milliseconds; with suitable restrictions on the rate of
login attemps (and thus decryptions) we allow per remote client, protecting against
a "CPU burn" attack is more feasible.
How secure is an n-bit RSA key?
As ever, judging the security of a key of a given size is a complex issue.
With current knowledge, "breaking" an RSA key by brute force effectively means
factoring the modulus. The largest number that has been factored publically to date is
RSA-640, a 640-bit number put up as a challenge by RSA and factored in 2005.
This number took "only" around 350 CPU hours (using a cluster of 80 2.2 GHz Opterons).
Put another way, you can rent that CPU time from Amazon for about 50 dollars.
This is a simplistic view: it doesn't take into account memory and data transfer
requirements. And the experimental software used by the team isn't exactly a "plug and play
RSA cracker": it surely requires considerable configuration by somebody well versed
in number theory.
Factoring RSA 512-bit keys is now squarely within the reach of anyone who is
determined enough. As testimony to this, several 512-bit RSA keys used to sign the operating systems of
Instruments calculators were recently factored, reportedly within "several months".
So what about 1024-bit keys? Generally, this size will keep your
data safe now from an adversary with modest resources. But it's
not sufficient for keeping data confidential much into the future, or for
keeping it secret from an adversary prepared to devote a few million dollars
to the problem. To see why, we'll look below at some estimates on the difficulty of
breaking 1024-bit RSA encryption.
One estimate is made by Shamir & Tromer (2003)
in their hypothetical TWIRL device.
They suggested that for "a few dozen million US dollars", a hardware device could
be built to break a 1024-bit RSA key within around a year. Franke et al (2005)
similarly estimate a cost of 200 million dollars2 for a machine to factorise
a 1024-bit number in one year. If these cost estimates are accurate, it's safe
to assume that the NSA has built such a machine (unless they have another way
of breaking RSA more efficiently). And by Moore's Law alone, we'd assume that
their machine takes considerably less than a year.
Based on Shamir & Tromer's estimate, Kaliski (2003)—
see reference in footnote 1—
recommends the following RSA key lengths depending on how long data is intended to
|Lifetime of data||RSA key size|
|Up to 2010||1024 bits|
|Up to 2030||2048 bits|
Recommended RSA key sizes depending on lifetime of confidential data.
|Up to 2031 onwards||3072 bits|
Shamir & Tromer considered hardware because they estimated that a solution in software
would not scale beyond around 500 bits. Thorsten Kleinjung (one of the tem that broke RSA-640)
estimates that around 8.4 million CPU years are needed to factorise a 1024-bit
number in software3 (his estimate is specifically 8.4 million
uniprocessor PCs, taking into account memory and data transfer requirements). Using my
favourite crude approximation, that's a million or so dollars of rented CPU time in 2009.
It's not clear if and how this would scale to, say, several thousand 256-core machines
(bearing in mind that that could be a fairly modest botnet by, say, 2020).
Ferguson & Schneier (2003) in Practical Cryptography
are actually more conservative than the RSA recommendations:
"The absolute minimum size for n is 2048 bits or so if you want to protect your data for 20 years.
[...] If you can afford it in your application, let n be 4096 bits long, or as close
to this size as you can get it." (p. 233)
They also recommend checking that your software supports keys up to 8192 bits, "just in case".
To my knowledge, Sun's RSA implementation does in principle support this size, but at present it is
1. RSA recommend 1024-bit keys for "enterprise keys"
and 2048-bit keys for "root keys" (used for signing). See,
for example, Kaliski, B. (2003), TWIRL and RSA Key size.
2. Franke, J. et al (2005), SHARK: A Realizable Special Hardware Sieving Device for Factoring 1024-Bit Integers in Cryptographic Hardware and Embedded Systems � CHES 2005, Springer.
3. See Kleinjung, T. Estimates for factoring 1024-bit integers