# Security strength of RSA in relation with the modulus size

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

-
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. – pg1989 Jun 11 '13 at 17:26
Related question for ECC: crypto.stackexchange.com/questions/31439/… – mikemaccana Dec 21 '15 at 16:02

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.

-
Could you explain why the strength is 80 and not 86 for RSA-1024? – user129789 Aug 30 '13 at 13:35
@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. – Reid Aug 30 '13 at 14:01
@mikemaccana: The $o(1)$ is little-o notation. As $n \to \infty$, the value $o(1)$ tends toward 0. – Reid Apr 2 '15 at 22:07
@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. – Reid Apr 2 '15 at 22:12
@mikemaccana: I'm glad to hear it! I'm unfortunately inactive on Twitter; the most I do is sometimes glance at other folks' pages. – Reid Apr 2 '15 at 22:27