Hi, In a talk on #29c3 Dan Bernstein describes an algorithm to break weak RSA keys using a broken random number generator. The basic idea is that if two keys share a common prime, you can find that out with the greatest common divisor algorithm and you can use batch gcd to do it on a bunch of keys.
There are preliminary video recordings of the talk https://www.youtube.com/watch?v=N5Wn6ZBLjgU and here's the basic algorithm described http://facthacks.cr.yp.to/batchgcd.html Now the obvious question: Has anyone already tried to do this on the ssl observatory data? Is it feasible on home-hardware? (In the talk sounds like it would be feasible, but I'm unsure if this is only true for 1024 bit keys or if it'd be also feasible on longer keys) One would probably be able to break a couple of the weak debian keys, but the interesting question would be if this wold lead to more signs of issues similar to the debian bug. -- Hanno Böck mail/jabber: [email protected] GPG: BBB51E42 http://www.hboeck.de/
signature.asc
Description: PGP signature
