3 ms·

Zero. If you're using anything with 800-bit security, you're probably a time traveler from the 90s. The more fun academic contribution to this is they found a

Zero. If you're using anything with 800-bit security, you're probably a time traveler from the 90s. The more fun academic contribution to this is they found a faster sieve, here http://cado-nfs.gforge.inria.fr http://cado-nfs.gforge.inria.fr. It's very neat stuff, I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. As with the original list, it's just unsolved problems that may help reveal more and more efficient ways to find/generate primes.

DuskStar 7y ago
> I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. Are you sure? My reading was "in 70% of the the time it took to crack RSA-768, using their hardware, we cracked RSA-240" - this would match up relatively well with the fact that the expected difficulty increase was x2.25 and then they say "Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records." Collaborating this, the previous record took ~4000+1500+900+200=6600 core years and the current one 4000. The Xeon Gold 6130 used has a single thread passmark of 1754 while the Xeon E5-2660 used in the RSA-768 factorization scored 1471, from [0]. Normalizing for passmark, the new RSA-240 factorization took 72.3% as much compute as the RSA-768 factorization. I would not be at all surprised if their software saw smaller gains through the generations than Passmark did, and it wouldn't take much to bring 72.3% to 70%. 0: https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs-Intel-Xeon-E5-2660/3126vs1219 https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs...
- SethTro 7y ago
  I agree, this was 3x faster than expected. Note: Factoring RSA-240 only took 900 core-years the additional 3100 core-years were on the discrete log. RSA 240 is 8 digits longer, it takes ~2x as much work for each 5.5 additional digits so this should have taken 2.7x as much compute.
  - deleted 7y ago
    [deleted]
svat 7y ago
Small nitpick, finding/generating primes is already very efficient/easy, e.g. if you want a 1000-digit prime, then in that range about one in every 2300 is prime (by standard heuristics based on the prime number theorem), so if you try a few thousand random numbers and test them for primality (which is fast too), you'll have found a prime with high probability -- and this is even without trying to avoid obviously non-prime numbers like multiples of 2 or 3. What is hard is factoring, i.e. finding the precise two primes p and q that were multiplied to result in pq. (In fact RSA relies on being able to pick two random primes easily, but which are hard to recover from their product.)
- pvg 7y ago
  It's more than a small nitpick since if we depended on factorization to find primes, RSA wouldn't be a practical cryptosystem to begin with.

DuskStar 7y ago

> I think they claim 30% less CPU years using the identical hardware to crack RSA-768, when applying this same software to RSA-768. Are you sure? My reading was "in 70% of the the time it took to crack RSA-768, using their hardware, we cracked RSA-240" - this would match up relatively well with the fact that the expected difficulty increase was x2.25 and then they say "Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records." Collaborating this, the previous record took ~4000+1500+900+200=6600 core years and the current one 4000. The Xeon Gold 6130 used has a single thread passmark of 1754 while the Xeon E5-2660 used in the RSA-768 factorization scored 1471, from [0]. Normalizing for passmark, the new RSA-240 factorization took 72.3% as much compute as the RSA-768 factorization. I would not be at all surprised if their software saw smaller gains through the generations than Passmark did, and it wouldn't take much to bring 72.3% to 70%. 0: https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs-Intel-Xeon-E5-2660/3126vs1219 https://www.cpubenchmark.net/compare/Intel-Xeon-Gold-6130-vs...

SethTro 7y ago
I agree, this was 3x faster than expected. Note: Factoring RSA-240 only took 900 core-years the additional 3100 core-years were on the discrete log. RSA 240 is 8 digits longer, it takes ~2x as much work for each 5.5 additional digits so this should have taken 2.7x as much compute.
- deleted 7y ago
  [deleted]

svat 7y ago

Small nitpick, finding/generating primes is already very efficient/easy, e.g. if you want a 1000-digit prime, then in that range about one in every 2300 is prime (by standard heuristics based on the prime number theorem), so if you try a few thousand random numbers and test them for primality (which is fast too), you'll have found a prime with high probability -- and this is even without trying to avoid obviously non-prime numbers like multiples of 2 or 3. What is hard is factoring, i.e. finding the precise two primes p and q that were multiplied to result in pq. (In fact RSA relies on being able to pick two random primes easily, but which are hard to recover from their product.)

pvg 7y ago
It's more than a small nitpick since if we depended on factorization to find primes, RSA wouldn't be a practical cryptosystem to begin with.