4 ms·

This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of

This take is rather naive. Those RSA factoring records were done by a large international team of researchers, using well established algorithms and decades of work on implementing those methods as fast as possible. The blog post says the paper mentions 8.4e10 operations for factoring, but I can't find that number in the paper anywhere. The post then states: "The 800-bit claims would be 36 bits of work." I don't know what that means. [edit]: the numbers are in the new version (https://eprint.iacr.org/2021/232 https://eprint.iacr.org/2021/232). I was looking at the old version uploaded yesterday.

contravariant 6y ago
It's in the abstract: >Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.
- AnimalMuppet 6y ago
  Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.
  - vitus 6y ago
    Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number. If true, it's still leaps and bounds ahead of anything we have today, though.
    - AnimalMuppet 6y ago
      Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".
  - ajarmst 6y ago
    Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)
    - rocqua 6y ago
      Thing is, RSA keys are rather 'sparse' because they are the product of two primes. There aren't that many primes, so there aren't that many numbers that only have two (proper) divisors. Hence, if you look at the strength of the currently best-known attack on RSA keys, you see that the key strength grows quite slowly as the keys get larger. This is purely from how sparse prime numbers are. From [1] which quotes NIST in 2015 we see (both collumns are in bits): Strength RSA modulus size 80 1024 112 2048 128 3072 192 7680 256 15360 > Because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. Technically the information is still there, it was just thought to be very hard to extract. This paper shows an easier way to extract it. [1] https://crypto.stackexchange.com/questions/8687/security-strength-of-rsa-in-relation-with-the-modulus-size https://crypto.stackexchange.com/questions/8687/security-str...
      - ajarmst 6y ago
        Thanks very much.
tgsovlerkhgsel 6y ago
2^36 "operations" can still take a lot of time if each operation is multiplying two giant numbers, unless the meaning of "operation" is somehow normalized to mean e.g. 64 bit integer operations.
- UncleOxidant 6y ago
  It didn't take long for custom ASICs for mining bitcoin to emerge. It wouldn't take long for custom ASICs to do these kinds of operations a lot faster than on a general purpose CPU to emerge.
- TacticalCoder 6y ago
  > 2^36 "operations" can still take a lot of time if each operation is multiplying two giant number It took me 3.3 years of actual computation time to do about 2^46 multiplication+modulo of two 2048 bit numbers on a Core i7. 2^36 of 2048 bit numbers should be doable in a day on an eight years old CPU. P.S: that was on a single core, for the problem I solved was explicitly created as to not be parallelizable.
libeclipse 6y ago
Supposing the paper does describe a more efficient factorisation algorithm, that does not imply that factoring a 800 bit prime (like the author of this article suggests) would be cheap.
- gowld 6y ago
  factoring a 800 bit prime is definitely cheap. ;-)
  - core-questions 6y ago
    In fact, I'll do it right now for you for only one dollar per bit.
titanomachy 6y ago
> The post states that 800-bit claims would be 36 bits of work. I don't know what that means. From the article: "Schnorr’s paper claims to factor ... 800-bit moduli in 8.4·10¹⁰ operations" 2^36 ~= 8.4·10¹⁰, so I guess "36 bits of work" means 2^36 operations. Analogous to how a password with 36 bits of entropy would require 2^36 guesses. My first time encountering the phrase "bits of work" as well, though.
- deleted 6y ago
  [deleted]

contravariant 6y ago

It's in the abstract: >Our accelerated strongprimal-dual reduction of [GN08] factors integers N≈2^400 and N≈2^800 by 4.2·10^9 and 8.4·10^10 arithmetic operations.

AnimalMuppet 6y ago
Increasing the length by a factor of 2^400 only increased the amount of work by a factor of 20? Staggering, if true in general.
- vitus 6y ago
  Actually, you're only increasing the length of the number by a factor of 2, since 2^400 is a 400-bit number. If true, it's still leaps and bounds ahead of anything we have today, though.
  - AnimalMuppet 6y ago
    Fair point. "Increasing the key [not the length of the key] by a factor of 2^400".
- ajarmst 6y ago
  Yeah, that's what got me. Doubling the length of the key only requires a single order of magnitude more work?. If that turns out to be true, I'm going to need to revise my beliefs about how the universe works. In particular, information theory and thermodynamics, because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. (Caveat: if the values of primes turn out to have a predictable pattern, that could provide the needed information. However, that would mean that the Riemann Hypothesis is false, and that'd be an even more astounding result.)
  - rocqua 6y ago
    Thing is, RSA keys are rather 'sparse' because they are the product of two primes. There aren't that many primes, so there aren't that many numbers that only have two (proper) divisors. Hence, if you look at the strength of the currently best-known attack on RSA keys, you see that the key strength grows quite slowly as the keys get larger. This is purely from how sparse prime numbers are. From [1] which quotes NIST in 2015 we see (both collumns are in bits): Strength RSA modulus size 80 1024 112 2048 128 3072 192 7680 256 15360 > Because multiplying two numbers together doesn't preserve information about what the factors were. Or at least pretty much everyone thought so. Technically the information is still there, it was just thought to be very hard to extract. This paper shows an easier way to extract it. [1] https://crypto.stackexchange.com/questions/8687/security-strength-of-rsa-in-relation-with-the-modulus-size https://crypto.stackexchange.com/questions/8687/security-str...
    - ajarmst 6y ago
      Thanks very much.

tgsovlerkhgsel 6y ago

2^36 "operations" can still take a lot of time if each operation is multiplying two giant numbers, unless the meaning of "operation" is somehow normalized to mean e.g. 64 bit integer operations.

UncleOxidant 6y ago
It didn't take long for custom ASICs for mining bitcoin to emerge. It wouldn't take long for custom ASICs to do these kinds of operations a lot faster than on a general purpose CPU to emerge.
TacticalCoder 6y ago
> 2^36 "operations" can still take a lot of time if each operation is multiplying two giant number It took me 3.3 years of actual computation time to do about 2^46 multiplication+modulo of two 2048 bit numbers on a Core i7. 2^36 of 2048 bit numbers should be doable in a day on an eight years old CPU. P.S: that was on a single core, for the problem I solved was explicitly created as to not be parallelizable.

libeclipse 6y ago

Supposing the paper does describe a more efficient factorisation algorithm, that does not imply that factoring a 800 bit prime (like the author of this article suggests) would be cheap.

gowld 6y ago
factoring a 800 bit prime is definitely cheap. ;-)
- core-questions 6y ago
  In fact, I'll do it right now for you for only one dollar per bit.

titanomachy 6y ago

> The post states that 800-bit claims would be 36 bits of work. I don't know what that means. From the article: "Schnorr’s paper claims to factor ... 800-bit moduli in 8.4·10¹⁰ operations" 2^36 ~= 8.4·10¹⁰, so I guess "36 bits of work" means 2^36 operations. Analogous to how a password with 36 bits of entropy would require 2^36 guesses. My first time encountering the phrase "bits of work" as well, though.

deleted 6y ago
[deleted]