Comment by userbinator | Hacker News Reader

Comment by userbinator | Hacker News Reader

Parent Full thread

We think properly created RSA keys couldn't possibly have such tiny factors because they were created by sophisticated algorithms, presumably would be two very large primes, and yet... this happens.

Dumb-and-stupid trial division by the first 1000 or so primes wouldn't take much time and could've easily caught this. I see this as a nice precautionary tale that we may sometimes think too highly of sophisticated algorithms that we trust them blindly, and miss looking for the bloody obvious. It's like an "is it plugged in?" sort of thing.

If I deliberately generated a public key that was divisible by 3, I wonder how long it would take for someone to notice...

I also entertain the (admittedly very slim) possibility that he did this deliberately to see what would happen.

I have seen the source code for some large prime generation algos... and they all have a test / verify stage which checks for divisibility by primes upto about a million (or billion), and the prime is then tested against the Miller-Rabin test.

My first reaction after reading this article was that, either they are using a bad version of a self authored prime generation algo, or keys are corrupted.

The guys who wrote the large prime generating algos are very well aware of your concerns (and share them too). I think you should not be too hasty in doubting these 'sophisticated algorithms'. One should probably verify that such issues exist in the prime generating algo, before we start calling one of our best mathematicians/programmers as incompetent.

> If I deliberately generated a public key that was divisible by 3

This is already well known:

> When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m < n1/e) the result of me is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.

https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...

Reply on news.ycombinator.com