3 ms·

Because it means that some RSA keys may be weaker than others. Without diving too far into the mathematics of it, the RSA cryptosystem (and indeed, many asymmet

Because it means that some RSA keys may be weaker than others. Without diving too far into the mathematics of it, the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is incredibly hard. This conjecture, if true, means that for some gigantic non-prime numbers, it is easier than expected (even if only slightly so) to figure out which two prime numbers were used.

AlexCoventry 9y ago
OK, but very few primes satisfy this hypothesis, so why's it a big deal? Is some generalization of the conjecture conjectured?
- wybiral 9y ago
  Not every key generated with the recently discovered ROCA vulnerability was easily factored either. But there are lots of keys out there... And an important key might be one of the vulnerable ones. Any kind of weakness like this is bad. Especially if more vulnerabilities like this exist it gets even worse.
  - AlexCoventry 9y ago
    OK, but the probability of choosing a prime satisfying this hypothesis is infinitesimal. Unless there's some bias in the way primes are chosen for RSA keys?
    - mabbo 9y ago
      There's two problems as I see it. #1- What if an attacker was able to modify how you pick your RSA keys? You could prove that hey, this RSA key is safe, and it's roots are prime, and I just generated it. But unbeknownst to you, your attacker is cracking your RSA key as soon as you start using it. The NSA is probably already trying to attack this way. #2- What if this isn't an isolated case, but the first discovery in an entire class of prime numbers? What if there's a whole spectrum of 'strength' of every prime and we had no idea? We need to research this topic more to find out for sure.
      - sliken 9y ago
        See above, there's already 1000s of weak keys on github and other places, significantly more than you'd expect if they were randomly generated. Problem is that it's hard to tell the difference between poor implementations and sabotaged implementations.
        tptacek 9y ago
        We're generally able to trace those weak keys back to specific implementation faults. All it takes is one widespread RSA implementation to do primegen badly for us to get hundreds more weak keys on Github.
        deleted 9y ago
        [deleted]
- wbl 9y ago
  You could use any abelian variety with CM to try something similar but I haven't worked out the details. But you probably will only get special forms very few primes fit.
  - AlexCoventry 9y ago
    What is CM?
    - wbl 9y ago
      Complex multiplication, which for historical reasons is used to refer to extra endomorphisms. CM is why the point has an easily findable order.
tptacek 9y ago
He's asking why, if you only have a 2^-730 chance of generating one of these primes at random, would you care about that risk? Single-bit memory or computation faults can devastate the security of cryptographic operations, and they're multiple orders of magnitude more likely to recur in a single computation than generating those particular primes.
- baby 9y ago
  In addition to tptacek's comment, we already know a bunch of ways where the RSA primes would be weak. And we don't check for them when generating RSA primes because they have almost no chance of occurring.
- peoplewindow 9y ago
  Because it lets you ship crypto-systems with keys that appear to be strong on inspection but which are actually weak (if you deliberately want to ship backdoored crypto).
  - tptacek 9y ago
    There are lots of ways to ship those systems without a "backdoor" that involves keys that will never occur once in the wild, let alone repeatedly. Why would they use an elaborate scheme that screams tampering?
wolfgke 9y ago
> the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is incredibly hard. While it is true that if we can factor a number that is a composite of two primes is sufficient to break RSA, the security of RSA is based on a weaker property (cf. https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=805975016#Integer_factorization_and_RSA_problem https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem...): Given two prime number p,q >= 3, let n := p * q. Let lambda(n) = lcm(p-1, q-1) (Carmichael's totient function). A public key then is (n,e), where 1 < e < lambda(n). If one knows p,q one can compute the corresponding private key (n,d), where d * e = 1 mod lambda(n) (which is considered to be a hard problem if one does not know p,q). The RSA problem asks that given a c \in {0, ..., n-1}, find an m \in {0, ..., n-1} such that c = m^e mod n. It is easy to check how this problem becomes simple if we can factor n (then we simply can find the private key). But it is an open problem whether solving the RSA problem is as hard as factoring or not.

AlexCoventry 9y ago

OK, but very few primes satisfy this hypothesis, so why's it a big deal? Is some generalization of the conjecture conjectured?

wybiral 9y ago
Not every key generated with the recently discovered ROCA vulnerability was easily factored either. But there are lots of keys out there... And an important key might be one of the vulnerable ones. Any kind of weakness like this is bad. Especially if more vulnerabilities like this exist it gets even worse.
- AlexCoventry 9y ago
  OK, but the probability of choosing a prime satisfying this hypothesis is infinitesimal. Unless there's some bias in the way primes are chosen for RSA keys?
  - mabbo 9y ago
    There's two problems as I see it. #1- What if an attacker was able to modify how you pick your RSA keys? You could prove that hey, this RSA key is safe, and it's roots are prime, and I just generated it. But unbeknownst to you, your attacker is cracking your RSA key as soon as you start using it. The NSA is probably already trying to attack this way. #2- What if this isn't an isolated case, but the first discovery in an entire class of prime numbers? What if there's a whole spectrum of 'strength' of every prime and we had no idea? We need to research this topic more to find out for sure.
    - sliken 9y ago
      See above, there's already 1000s of weak keys on github and other places, significantly more than you'd expect if they were randomly generated. Problem is that it's hard to tell the difference between poor implementations and sabotaged implementations.
      - tptacek 9y ago
        We're generally able to trace those weak keys back to specific implementation faults. All it takes is one widespread RSA implementation to do primegen badly for us to get hundreds more weak keys on Github.
        deleted 9y ago
        [deleted]
wbl 9y ago
You could use any abelian variety with CM to try something similar but I haven't worked out the details. But you probably will only get special forms very few primes fit.
- AlexCoventry 9y ago
  What is CM?
  - wbl 9y ago
    Complex multiplication, which for historical reasons is used to refer to extra endomorphisms. CM is why the point has an easily findable order.

tptacek 9y ago

He's asking why, if you only have a 2^-730 chance of generating one of these primes at random, would you care about that risk? Single-bit memory or computation faults can devastate the security of cryptographic operations, and they're multiple orders of magnitude more likely to recur in a single computation than generating those particular primes.

baby 9y ago
In addition to tptacek's comment, we already know a bunch of ways where the RSA primes would be weak. And we don't check for them when generating RSA primes because they have almost no chance of occurring.
peoplewindow 9y ago
Because it lets you ship crypto-systems with keys that appear to be strong on inspection but which are actually weak (if you deliberately want to ship backdoored crypto).
- tptacek 9y ago
  There are lots of ways to ship those systems without a "backdoor" that involves keys that will never occur once in the wild, let alone repeatedly. Why would they use an elaborate scheme that screams tampering?

wolfgke 9y ago

> the RSA cryptosystem (and indeed, many asymmetric-key cryptosystems) is based on the notion that multiplying two gigantic prime numbers together to get another gigantic non-prime number is easy; but taking a gigantic non-prime number and figuring out which two prime numbers were multiplied together is incredibly hard. While it is true that if we can factor a number that is a composite of two primes is sufficient to break RSA, the security of RSA is based on a weaker property (cf. https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem)&oldid=805975016#Integer_factorization_and_RSA_problem https://en.wikipedia.org/w/index.php?title=RSA_(cryptosystem...): Given two prime number p,q >= 3, let n := p * q. Let lambda(n) = lcm(p-1, q-1) (Carmichael's totient function). A public key then is (n,e), where 1 < e < lambda(n). If one knows p,q one can compute the corresponding private key (n,d), where d * e = 1 mod lambda(n) (which is considered to be a hard problem if one does not know p,q). The RSA problem asks that given a c \in {0, ..., n-1}, find an m \in {0, ..., n-1} such that c = m^e mod n. It is easy to check how this problem becomes simple if we can factor n (then we simply can find the private key). But it is an open problem whether solving the RSA problem is as hard as factoring or not.