Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
The security of an RSA key is hidden in the modulus. Attacking the key means (as far as we now) factoring the modulus. When you have factored the modulus, any public exponent with this modulus is broken. –  Paŭlo Ebermann Aug 30 '13 at 16:18
add comment

3 Answers 3

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.

share|improve this answer
    
Does a strength of 80 bit mean you need to bruteforce through 2^80 possibilities? –  user129789 Aug 31 '13 at 16:21
add comment

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.

share|improve this answer
1  
"in practice, we may generally assume it to be negligible"; actually, I do not believe that we know that, for the modulus sizes we are interested in practice, whether that $o(1)$ term is actually negligible. We do know that it tends toward 0 as $n \rightarrow \infty$, however that tells us nothing about the values of $n$ we are interested in. –  poncho Aug 30 '13 at 15:39
    
@poncho: That's correct. What I was driving at was more that, if the $o(1)$ term (assuming it's not just a mistake) was significant for typical values of $n$, one would expect it to be included explicitly in the formula, or at least to be mentioned in the article. –  Ilmari Karonen Aug 30 '13 at 15:53
2  
Actually, I believe it's included because no one knows what its form actually is; the exact value depends on the behavior of certain prime distributions, and no one knows exactly what that is. If it was known to be insignificant, we'd just omit it. –  poncho Aug 30 '13 at 15:56
    
Could I be mistaken that the modulus size is twice the length of the key sizes? –  user129789 Aug 30 '13 at 19:12
    
Somewhat obvious, but worth noting, on the topic of rounding, that all the key strength sizes list are an integral multiple of 8, aka an even byte length. Byte lengths are very convenient for implementations, so it naturally makes sense to use those as notable strength size increments. –  B-Con Aug 31 '13 at 2:03
show 2 more comments

Not sure. My two guesses would be

  1. There exists an algorithm that can factor a modulus faster than brute force.
  2. They are rounding, and always round down.

And why does it say RSA modolus size? Shouldn't it be RSA key size instead?

Unlike AES, where the key is just a bunch of bytes, there are multiple ways of storing an RSA private key. For example, you can store d, e, and n, or you can store p and q. 'key size' would be ambiguous.

share|improve this answer
1  
Actually, it's not that ambiguous; when we talk about the RSA key size, we always mean 'modulus size'. Imagine someone claiming to have a '2048 bit RSA key' that's made up of a 1024 bit modulus and a 1024 bit public exponent; people would (rightly) conclude that such an individual is completely clueless... –  poncho Aug 30 '13 at 16:01
    
@poncho Don't try to confuse people with that statement, please. –  user129789 Aug 30 '13 at 19:05
    
@user129789: I'm sorry, but what's confusing about that statement? About a "2048" bit key with a 1024 bit modulus? I thought I made it clear that idea was silly... –  poncho Aug 30 '13 at 20:44
1  
@poncho If you're writing a standards document, you want it to be as clear as possible, even to people unfamiliar with public key cryptography. –  Nick ODell Aug 30 '13 at 20:56
    
@poncho Did you just claim that a "2048" bit RSA key does not have a 2048 bit Modulus? And you really NEED a 1024 bit public component for a "2048" bit RSA key? I guess '65537' is not 1024 bit. –  user129789 Aug 31 '13 at 16:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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