[SSL Observatory] Batch gcd

[Hanno Böck]

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: hanno at hboeck.de
GPG: BBB51E42		http://www.hboeck.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://lists.eff.org/pipermail/observatory/attachments/20121229/2d1ae339/attachment.sig>