47
$\begingroup$

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?)

$\endgroup$
5
  • $\begingroup$ The numbers on the left are symmetric keys of corresponding strength. I.e. a symmetric key of 80 bits provides roughly as much security as a 1024-bit RSA key. For posterity, I'll mention that the table is on page 62 of the linked NIST document. $\endgroup$
    – pg1989
    Jun 11, 2013 at 17:26
  • $\begingroup$ Related question for ECC: crypto.stackexchange.com/questions/31439/… $\endgroup$ Dec 21, 2015 at 16:02
  • $\begingroup$ Backlink: stackoverflow.com/q/8453529/632951 $\endgroup$
    – Pacerier
    Apr 12, 2016 at 15:02
  • $\begingroup$ keylength.com gives a comprehensive overview for the key lengths, using multiple methods. $\endgroup$
    – user94293
    Jun 2, 2016 at 21:31
  • 1
    $\begingroup$ I surmise that a comparison between asymmetric and symmetric encryption algorithms could under circumstances be analogous to one between nuclear and non-nuclear power generations and such numerical figures shouldn't be taken in a pedantic manner. I conjecture that the differences in the ways of using these two classes of encryption algorithms in the practice (including the modes of operations used) could possibly effect certain non-trivial influences on the comparison in scenarios in reality. $\endgroup$ Jun 3, 2016 at 8:46

4 Answers 4

47
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ Could you explain why the strength is 80 and not 86 for RSA-1024? $\endgroup$
    – user129789
    Aug 30, 2013 at 13:35
  • $\begingroup$ "The value of k is commonly considered to be the key size." See page 64 of NIST SP 800-57 $\endgroup$
    – user129789
    Aug 30, 2013 at 13:46
  • 7
    $\begingroup$ @user129789: First, directly evaluating asymptotic expressions is quite imprecise. But more importantly, the NIST is an administrative organization, and their purpose in that table was to define a set of key sizes for various primitives that give a specific level of security. The intent is that you might decide 112 bits of security is enough for your application, then use the key sizes/algorithms suggested in the table. So they picked commonly-used key sizes that were slightly above the desired security level. The extra margin also gives you a bit of leeway in terms of Moore's law. $\endgroup$
    – Reid
    Aug 30, 2013 at 14:01
  • 2
    $\begingroup$ @mikemaccana: The $o(1)$ is little-o notation. As $n \to \infty$, the value $o(1)$ tends toward 0. $\endgroup$
    – Reid
    Apr 2, 2015 at 22:07
  • 2
    $\begingroup$ @mikemaccana: Indeed it does! Otherwise it would not be there. :) However, we're not sure of the value of $o(1)$ for values of $n$ that we care about. The complexity of the GNFS is heuristic. I recommend looking at this question and its answers/comments for some more discussion. $\endgroup$
    – Reid
    Apr 2, 2015 at 22:12
7
$\begingroup$

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
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.