2 ms·

RSA-1024 seems to be about 8 million times better than RSA-512, so cracking that would be $64 million in compute. Not NSA-proof, but should be more than enough

by GuB-42 2y ago

RSA-1024 seems to be about 8 million times better than RSA-512, so cracking that would be $64 million in compute. Not NSA-proof, but should be more than enough to keep spammers out, especially considering that DKIM is just one layer of protection.

zahlman 2y ago
512 extra bits of key only gets you 23 bits of entropy?
- GuB-42 2y ago
  Yep, the formula is a bit complicated, it comes from the general number field sieve (GNFS) algorithm, you can find some equivalences online between symmetric key algorithms and RSA and 23 bits seems about right. I have also seen lists where they give RSA-512 64 bits and RSA-1024 80 bits, just a 16 bit difference, but it looks a bit arbitrary to me. I think the NIST doesn't even look at RSA-512 anymore, as it is definitely broken, it only starts at 1024. A RSA key is the product of two primes, not any number, so you need a lot more bits to get equivalent security to, say, AES. That's also a reason for elliptic-curve cryptography, which needs a lot less bits than RSA for the same level of security.
  - Dylan16807 2y ago
    > A RSA key is the product of two primes, not any number, so you need a lot more bits to get equivalent security This explanation doesn't seem right to me. For 1024 bit numbers, about 0.14% are prime. So that difference only loses a handful of bits. There are more than 2^2000 usable RSA-2048 keys, and simply guessing and dividing would require more than 2^1000 guesses. Those few bits lost to the prime number restriction aren't why the level of security is so low.
- deleted 2y ago
  [deleted]
upofadown 2y ago
That's just the extra compute required. There is a large increase in required memory that needs to be quickly accessible in a particular way. One estimate I saw claimed that breaking 1024 bit RSA would take more than 2 billion dollars over a period of years.

by GuB-42 2y ago

zahlman 2y ago

512 extra bits of key only gets you 23 bits of entropy?

GuB-42 2y ago
Yep, the formula is a bit complicated, it comes from the general number field sieve (GNFS) algorithm, you can find some equivalences online between symmetric key algorithms and RSA and 23 bits seems about right. I have also seen lists where they give RSA-512 64 bits and RSA-1024 80 bits, just a 16 bit difference, but it looks a bit arbitrary to me. I think the NIST doesn't even look at RSA-512 anymore, as it is definitely broken, it only starts at 1024. A RSA key is the product of two primes, not any number, so you need a lot more bits to get equivalent security to, say, AES. That's also a reason for elliptic-curve cryptography, which needs a lot less bits than RSA for the same level of security.
- Dylan16807 2y ago
  > A RSA key is the product of two primes, not any number, so you need a lot more bits to get equivalent security This explanation doesn't seem right to me. For 1024 bit numbers, about 0.14% are prime. So that difference only loses a handful of bits. There are more than 2^2000 usable RSA-2048 keys, and simply guessing and dividing would require more than 2^1000 guesses. Those few bits lost to the prime number restriction aren't why the level of security is so low.
deleted 2y ago
[deleted]

upofadown 2y ago

That's just the extra compute required. There is a large increase in required memory that needs to be quickly accessible in a particular way. One estimate I saw claimed that breaking 1024 bit RSA would take more than 2 billion dollars over a period of years.