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

As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)...

Correct.

they don't have high enough entropy and output duplicates ~0.2% of the time.

Almost correct: They don't have enough entropy at least 0.2% of the time. These results are consistent with all primes being generated with ~40 bits of entropy -- which would imply that all the keys are broken. Obviously we hope that this is not the case and instead it's just a small subset of primes which were generated with low entropy, but the data do not provide any evidence in either direction.



They do write:

the graph of the moduli contained in c distinct certificates consists, in an ideal world, of c disjoint connected components each consisting of two vertices joined by a single edge, for a total of 2c vertices and c edges ... tens of millions of [lab-]generated RSA moduli turned out to behave as expected based on the above assumption.

That implies that there is at least one (presumably common) method for generating RSA keys which does not frequently output duplicate primes.


Security requires more than "does not frequently output duplicate primes". It requires "primes have a large amount of entropy".




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

Search: