Why is the complexity of RSA-1024 80 bit and not 86 bit?

Question

Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit?

Here is the complexity for the GNFS (pulled from the linked Wikipedia article):

$$\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

Security strength of RSA in relation with the modulus size

PS: Why is there an 'o(1)' in the formula? And why does it say RSA modolus size? Shouldn't it be RSA key size instead?

Answer 1

Presumably, it's because they rounded it down to a nice round number of bits. Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible.

Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, if someone finds a better algorithm to attack RSA then all bets are off. All we can really say with any confidence is that, using the best algorithms publicly known today, cracking a 1024-bit RSA key is about as hard as cracking an 80 to 90 bit symmetric (e.g. AES) key. Which is a pretty wide margin (adding 10 bits to the symmetric key length makes it about 1000 times harder to crack), but that just reflects how hard it is to estimate these things.

Actually, I think Reid already answered the first part of your question pretty well in his comment, so let me just quote him here:

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

---

As for your other questions, the $o(1)$ in the complexity formula for GNFS that you quoted is little-o notation. Basically, it means that there's an unknown term there that tends to zero as $n$ tends to infinity. Of course, the little-o notation, on its own, doesn't really tell us anything about how big the unknown term might be for any given finite value of $n$, but in practice, we may generally assume it to be negligible.

(Actually, the $o(1)$ term doesn't seem to appear in the reference cited by the Wikipedia article for the formula. It might just be a mistake in Wikipedia. Looking at the edit history of the article, it seems to have been inserted in this edit, which removed an earlier $O(\cdot)$ from around the entire expression.)

As for why it says "modulus size" instead of "key size", you're right that those two terms are often used interchangeably for RSA. However, technically, an RSA key consists of two parts: the modulus $n = pq$ (which is common to the public and private keys) and either the public exponent $e$ or the private exponent $d \equiv e^{-1} \bmod n$. Using the word "modulus" instead of "key" makes it clear that we don't want to include the length of those exponents (since they don't affect the difficulty of factoring the modulus) in the number, even though they're technically part of the key.

Answer 2

I'll expand on the comment I left on my answer.

The purpose of Part 2 of NIST SP 800-57 is to "[provide] guidance on policy and security planning requirements for U.S. government agencies". Keeping that in mind, the table on page 64, i.e. the table from whence the numbers in that question came, includes more than just RSA key sizes. Namely, it includes some symmetric-key algorithms and other forms of asymmetric cryptography.

Usage goes as follows: a user first decides on a minimum security level required for the application at hand. Once the user has determined such a level, they then reference the tables presented in Part 2 to determine the appropriate key length(s).

It would be quite inconvenient if the NIST had separate rows for the RSA algorithms. If the user wanted 112 bits of security, they would pick 3DES, which fits that security level almost exactly. Why have another table, or another line on the table, saying that RSA-2048 offers around 116 bits instead of 112?

The point of a standard is simplicity for the user. Decide on requirements, get key sizes. Done.

Further, directly evaluating asymptotic expressions is really quite imprecise. Asymptotic expressions are true "in the limit", i.e. as the number in question approaches infinity. Plus, I evaluated the expression at $2^b$, which only approximates the time required to factor a $b$-bit integer. So, it wasn't as though I generated a 2048-bit RSA key and decided to use that key's modulus in the expression. $2^{2048}$ is somewhere "pretty close" to a real 2048-bit modulus, but it's not an exact number by any means.

Another point is that the GNFS complexity is only heuristic in nature. We don't currently have a rigorous proof that the currently-accepted complexity is the "real one". See Lenstra et al.'s The number field sieve, page 5/section 3, for an extended discussion of the difficulties surrounding a formal asymptotic analysis. My point is that on top of evaluating an asymptotic expression at a number that's roughly somewhere around a real RSA modulus, the very expression we're evaluating is heuristic in nature.

Ultimately, as you can see, all of the discussion here is based on assumptions and estimations. The $o(1)$ notation you ask about is just another artifact of this: it is the asymptotic part of the GNFS complexity, and it tends to $0$ as $n \to \infty$. Does it make a difference in the value? Absolutely! It was ignored because of the inaccuracies already present in the discussion, but it's still an extremely relevant value. Unfortunately, we don't know too much about what exactly that value is.

So, then, with all of that in mind, it shouldn't be much of a surprise that we boil down the figure to "around 80 bits". Simply put, knocking off those six bits is mostly irrelevant given all of the other hand-waving. Couple that with the fact that we're putting this in that table for others, and well, there you go.