Hacker News Reader

Comment by AlexCoventry | Hacker News Reader

Why is this significant?

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.

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.

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.

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).

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?

> 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...):

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.

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

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.

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?

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.

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.

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.

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.

What is CM?

Complex multiplication, which for historical reasons is used to refer to extra endomorphisms. CM is why the point has an easily findable order.

It's not really significant for RSA at all. It is likely that no human (as far as we recognise the species) will ever generate RSA primes of this form randomly, if standard tools are used.

It's been known for a very long time that there are many extremely sparse classes of primes which general factoring algorithms will extract as factors very quickly.

For example, some general factoring algorithms will factor numbers of the form (a^m+b)(a^n+c) for small a, b and c and m and n fairly close. But this is an extremely sparse class.

You could generate billions of such sparse classes (and check them all by brute force), but it's still unfathomably unlikely you would find RSA primes in the wild of any of these forms, if they were generated by reasonable implementations.

It is... somewhat significant.

If i recall correctly, you need to generate two large prime numbers to get a key. There are already several caveats for the prime generation, so you cannot just take any two primes that are big enough. So for a proper key generation, you generate a lot of random numbers, verify that they are prime and that they are "proper" for RSA.

This discovery "just" means that there are some additional steps for verifying the properness of the prime, that every RSA implementor has to add. So for mitigation, there is work to do for implementors, but similar work has been necessary before...

Of course, this might have been used to generate backdoorable RSA keys, and giving them to people without their knowledge. If that happened, this issue becomes... more significant for all that have been backdoored.

This comment box is too small.

We keep learning about elliptic curves, and the more we learn, the more we glimpse the edges of a massive and deep symmetry which relates primes and polynomials (Fermat's Last Theorem, RSA, AES) with elliptic curves (Birch & Swinnerton–Dyer Conjecture, ECDSA, Ed25519) and modular forms and L-functions (Riemann Zeta Hypothesis). This is known as the Langlands programme [0].

The significance of this result is that it is yet another brick in the wall of the Langlands programme's immense and daunting blueprint; overall, it is only a tiny tiny fragment. The L-function database [1] is far more interesting if you want to get a good look at a collection of stuff that we know about the topic.

[0] https://en.wikipedia.org/wiki/Langlands_program [1] http://www.lmfdb.org/intro

Reply on news.ycombinator.com