3
$\begingroup$

I was checking for authoritative sources to back up my recommendation of a minimum RSA key length of 1024 and was shocked to find that NIST 800-56Br1 and FIPS 186-4 both recommend at least 2048 bits with 3072 bits for TOP SECRET data. I found that other sources have similarly high recommendations based on expected lifetime of the key.

These recommendations seem excessive in light of what I can find about attacks against RSA encryption. As far as I can find, the most recent attempt to factor RSA numbers was the successful factoring of the 756 bit RSA number. That was in 2009 and required, roughly, two years of effort with 100 computers and a team of mathematicians. Those researchers noted that their methods would not scale to significantly larger RSA numbers, so other [and unknown] methods would need to be developed.

Given that each additional bit doubles the number of values, 1024 bits would have $2^{256}$ times as many possible values. Even given very sparse utilization of that immense field, the effort required to attack a 1024 bit RSA key appears very far outside the reach of current capabilities.

Have I missed some more recent attacks? I note that some of the recommendations I have found predate the 2009 paper. Why would cryptanalysts believe that 1024 bit RSA keys would be insufficient when no one had even attacked the 756 bit key, which is vastly easier than 1024?

Can anyone point me to cryptanalytic work that demonstrates the risk to 1024 bit RSA?

Improve this question
$\endgroup$
3
  • $\begingroup$ This announces the factorization of a larger number. ​ ​ $\endgroup$
    – user991
    Commented Feb 18, 2016 at 5:17
  • $\begingroup$ @RickyDemer, that is the paper I referenced in my the last paragraph of my question. In that paper, the researchers call-out limitations in their methodology that prevent it from scaling well. If that is the strongest and most recent work on the subject, than the 1024 bit RSA number is still quite secure. $\endgroup$
    – JaimeCastells
    Commented Feb 18, 2016 at 14:05
  • $\begingroup$ The biggest paragraph in your question refers to a smaller number. ​ ​ $\endgroup$
    – user991
    Commented Feb 18, 2016 at 14:10

2 Answers 2

Reset to default
6
$\begingroup$

RSA, and to a somewhat similar extent Diffie-Hellman, bases its security on the difficulty of factoring large numbers into primes. While a scheme like AES can use all 2n numbers, in order to break RSA, you need to guess prime numbers.

As there are far fewer prime numbers and the factors can be better guessed, we need far larger prime numbers than other schemes like AES. So each additional bit doesn't double the difficulty of brute forcing it. If you want to venture into the math, you can check out the Wikipedia page on RSA.

While no one (we know of) has managed to break 1024, it is always important to stay ahead of the curve. And since brute force isn't exactly 2256 times more difficult,we pick higher primes. Who knows what future improvements in mathematics could break 1024-bit keys.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ And if you're interested in a paper that attacks 1024 DHE, check out the Logjam attack where it claims a reasonable amount of computation could break commonly used configurations. weakdh.org $\endgroup$
    – Azarinak
    Commented Feb 17, 2016 at 22:19
  • $\begingroup$ I suppose what's bothering me here is that these are all "soft" arguments and seem to amount to little more than F.U.D. No one has demonstrated successful factoring of 800 bit RSA numbers, which is much harder than 768 bit. The methods used to factor the 768 bit number are known to not scale well and no better alternatives are documented, to my knowledge. $\endgroup$
    – JaimeCastells
    Commented Feb 18, 2016 at 14:32
  • $\begingroup$ Certainly primes are sparsely distributed, roughly .04% of numbers on the order of 2^1024 I believe. None the less, going from a field of 2^768 to a field 2^256 times as large provides very many indeed. In fact the sparseness is utterly dwarfed by the exponential multiplication in the size of the field. I believe the number of primes is increased by roughly 2^242 times. $\endgroup$
    – JaimeCastells
    Commented Feb 18, 2016 at 14:34
  • 1
    $\begingroup$ @JaimeCastells, On the contrary, it is well known that the algorithm scales "well" compared to raw size. See the duplicate and this question. The main reason nothing larger than 768 bits has been (publicly) factored may be that 1024 bits is the next "standard" size and one wouldn't expect it to have been factored just yet (on an academic budget). $\endgroup$
    – otus
    Commented Feb 18, 2016 at 18:35
-1
$\begingroup$

With number field sieve and quadratic field sieve, it is easy now to break RSA keys less than 1024 bit and more so the concepts of quantum cryptography will break all myths of unbreakable security. So graduating to higer bit security is obvious choice. ECDH and EC RSA still give some respite in present times.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "the concepts of quantum cryptography will break all myths of unbreakable security" is funny! It is mixing quantum cryptography (which attempts to make communications secure without relying on the unproven difficulty of mathematical problems) and quantum computers (which attempt to solve said problems faster than conventional computers do). The commonalities between the two are: being based on quantum physics, and yielding dubious practical achievements. $\endgroup$
    – fgrieu ♦
    Commented Feb 18, 2016 at 7:37

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