Why is the complexity of RSA-1024 80 bit and not 86 bit? 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?
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.