2 ms·
OK, but very few primes satisfy this hypothesis, so why's it a big deal? Is some generalization of the conjecture conjectured?
by 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 agoNot 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 agoOK, 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 agoThere'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 agoSee 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 agoWe'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 agoYou 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 agoWhat is CM?
- wbl 9y agoComplex multiplication, which for historical reasons is used to refer to extra endomorphisms. CM is why the point has an easily findable order.