Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

this mostly isn't true. for much smaller keys there were risks of "weak primes", but as general purpose factoring algorithms got better and pushed keys bigger a higher and higher percent of primes end up safe. with 2048 bit primes, the odds of your prime being significantly weaker than average drop to something like 1 in 2^1024


What is a "weak prime" here (i.e. by which properties is such a prime number characterized)?


Suppose that p-1 has no large prime factors, eg suppose p-1 divides 10000!, then you can factor N by calculating something like x = random() ^ (10000!) % N. Then x will be 1 mod p (or rarely 0, if x was) but probably not mod q unless q has the same property. Then gcd(x-1,N) = p, and you've factored N. A similar trick works with Lucas sequences if p+1 has no large prime factors. So instead of attacking your key with a very expensive algorithm that doesn't care about special properties of p,q, they might gamble that your key is weak and try a cheaper algorithm first. So folks would avoid keys where p+1 or p-1 was "smooth" in this way.

However, we don't care much about this attack anymore for two reasons. One is that N must now be big enough to resist attack by the Number Field Sieve (and not just the Quadratic Sieve). At least if there are only two primes in the RSA key, this means that p,q must be big enough for these attacks to be very unlikely to work. But just as importantly, it turns out that you can do the above attack with exponentiation on a random elliptic curve instead of regular exponentiation / Lucas sequences. This is how most math libraries implement factor(). It's slightly slower but since the random elliptic curve will have a random order instead of exactly p+1 or p-1, it is equally likely to work with any p,q of a given size, regardless of special properties they might have.

In other words, an attacker can re-randomize how weak or strong a key is by using elliptic curves. So there's not much point in avoiding ones that look weak at first glance.


A prime pair that’s easily factorable




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: