Security strength of RSA in relation with the modulus size

Question

NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits:

Strength  RSA modulus size
  80        1024
 112        2048
 128        3072
 192        7680
 256       15360

This works out to approximately $s \approx 4 n^{0.43}$ (but I have no idea whether my extrapolation means anything; strengths up to 112 are indexed on DES while strengths 128 and above are indexed on AES, i.e. the strength is the difficulty of brute-forcing the corresponding symmetric algorithm with the specified key size).

What are these numbers based on? Do they come from the expected complexity of the best known factorization methods? Or are they extrapolation from the amount of computation in specific factorization efforts such as for RSA-768 (which “required more than $10^{20}$ operations”)?

(I'm asking for more precise information than Difficulty of breaking RSA for a given key size. How big an RSA key is considered secure today? has a nice history of RSA factorizations, but doesn't answer my question — is that what the strength estimates are based on?)

Answer 1

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica.

Here is the complexity for the GNFS (source):

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$

where $n$ is a number to factor. Evaluating the above expression at $2^b$ is a rough approximation of the the time needed to factor a $b$-bit integer. Here's a table showing the bit-length of the evaluation at $2^{1024},2^{2048},\dots$:

Strength  RSA modulus size   Complexity bit-length
  80        1024               86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

I generated these numbers with the following Mathematica code:

({#, N@Log2@gnfsComplexity[2^#]} &) /@ {1024, 2048, 3072, 7680, 15360}

where gnfsComplexity is defined as:

gnfsComplexity[n_] := Exp[(64/9 * Log[n])^(1/3) * (Log[Log[n]])^(2/3)]

which is not the prettiest thing I've ever written, but it seems accurate. (For those unfamiliar with Mathematica, the second code snippet defines a function that's a transliteration of the above GNFS complexity for a number $n$. The first code snippet evaluates that complexity at $n=2^{1024}, 2^{2048}$, etc., takes the logarithm base 2, and converts it to a numerical approximation — a decimal number — instead of an exact result like a fraction.)

As for the reasoning behind the larger key sizes for RSA, the explanation's not too difficult. If you look at the document in the question, you will notice that the "bits of security" for block ciphers correlate almost perfectly with the size (in bits) of the keys for that block cipher (with rare exceptions). This is because our best attack on a secure block cipher essentially is a brute-force search for the key, which on average takes $2^{n-1}$ time where $n$ is the bit-length of the key.

However, for RSA, our best line of attack is not to execute a brute-force search for the key; instead, we "simply" factor the (public) modulus, so the security of the scheme revolves around the efficiency of factoring. The GNFS has a sub-exponential but still super-polynomial time complexity, and one can use this time complexity to roughly approximate the security offered by the scheme. I believe that's what the NIST is doing here.

Answer 2

I have reformatted the above equation as a program for GNU bc (part of GNU coreutils, found on most Linux systems). GNU bc will be much easier to find than Mathematica (although it is quite eccentric).

Here is the code:

$ cat RSA-gnfs.bc 
#!/usr/bin/bc -l

scale = 14
a = 1/3
b = 2/3
#print "RSA Key Length? "
c = read()

t = l( l(2 ^ c) )
# if b < 1, then a^b == e (l(a) * b)
m = e( l(t) * b )
t = 64 / 9 * l(2 ^ c)
n = e( l(t) * a )
o = e( m * n )
p = l(o) / l(2)
print "Strength: ", p, "\n"
quit

Here are a few runs of the code, adding keysizes that were not included above:

$ for x in 1024 2048 3072 4096 7680 8192 15360 16384
do echo $x | ./RSA-gnfs.bc ; done

Strength: 86.76611925027707
Strength: 116.88381329581011
Strength: 138.73628085271660
Strength: 156.49695341791272
Strength: 203.01873594416484
Strength: 208.47248637388102
Strength: 269.38477262126889
Strength: 276.51840722076620

According to this equation, if you are using AES256 as your symmetric cipher, then this is the minimum RSA key size that will present the same strength:

$ echo 13547 | ./RSA-gnfs.bc 
256.00114520595064

Here is the minimum equivalence for "top secret" AES192:

$ echo 6707 | ./RSA-gnfs.bc 
192.00709600689071

Here is the minimum equivalence for AES128:

$ echo 2538 | ./RSA-gnfs.bc 
128.00922533664156

RFC-7525 specifies that "Implementations MUST NOT negotiate cipher suites offering less than 112 bits of security" - complying with this parameter yields a new minimum RSA key size:

$ echo 1853 | ./RSA-gnfs.bc 
112.00835107658348

Answer 3

The previous comment left a term out of the numerator.

$$x = \frac{1.923 \times \sqrt[3]{L \times ln(2)} {\sqrt[3]{[ln(L \times ln(2))]^2}} - 4.69}{ln(2)}$$

I find this formula on page 92 of the NIST document that was previously mentioned:

http://csrc.nist.gov/groups/STM/cmvp/documents/fips140-2/FIPS1402IG.pdf

The GNU bc code to implement this equation is:

$ cat RSA-NIST.bc 
#!/usr/bin/bc -l

scale = 14
a = 1/3
b = 2/3
#print "RSA Key Length? "
l = read()

t = l * l(2)
m = l(t)
# if b < 1, then a^b == e (l(a) * b)
n = e( l(m) * b )
o = e( l(t) * a )
p = (1.923 * o * n - 4.69) / l(2)
print "Strength: ", p, "\n"
quit

Rerunning with the previous batch inputs:

$ for x in 1024 2048 3072 4096 7680 8192 15360 16384
do echo $x | ./RSA-NIST.bc ; done
Strength: 79.99990535892915
Strength: 110.11760837749330
Strength: 131.97008244495367
Strength: 149.73076030162618
Strength: 196.25255668821560
Strength: 201.70630874277964
Strength: 262.61861313789943
Strength: 269.75224986273620

I will note a) this new equation runs considerably faster, and b) these numbers imply even lower strength.

According to this equation, if you are using AES256 as your symmetric cipher, then this is the minimum RSA key size that will present the same strength:

$ echo 14446 | ./RSA-NIST.bc
Strength: 256.00032964845911

Here is the minimum equivalence for "top secret" AES192:

$ echo 7295 | ./RSA-NIST.bc 
Strength: 192.00346260354399

Here is the minimum equivalence for AES128:

$ echo 2868 | ./RSA-NIST.bc 
Strength: 128.01675571278223

RFC-7525 specifies that "Implementations MUST NOT negotiate cipher suites offering less than 112 bits of security" - complying with this parameter yields a new minimum RSA key size:

$ echo 2127 | ./RSA-NIST.bc 
Strength: 112.01273358822347

Suprisingly, RSA-2048 does not appear compliant using NIST's equation - RSA-2127 should be their new minimum.

Answer 4

The security levels for RSA are based on the strongest known attacks against RSA compared to amount of processing that would be needed to break symmetric encryption algorithms.

The equation NIST recommends to compute approximate length for key is found in FIPS 140-2 Implementation Guidance Question 7.5.

It is:

$x = \frac{1.923 \times \sqrt[3]{L \times ln(2)} {\sqrt[3]{[ln(L \times ln(2))]^2}}}{ln(2)}$

This formula is based on the best currently known factoring mechanisms, i.e., , General Number Field Sieve, and the formula gives results very similar to formula for given in the other answers.

Key length Official Strength Result of Formula

RSA-1024 80 79.999

RSA-2048 112 110.118

RSA-3072 128 131.97

RSA-7680 192 196.253

RSA-15360 256 262.619

This same formula also applies to DSA group sizes (assuming subgroup is sufficiently large).