Reproducing RSA GCD attack (common factor) - real world certificates

Question

I'd like to reproduce common factor attack on rsa. And wondering how to get as many as possible (milions?) real world rsa certificates. Any ideas?

Answer 1

There are multiple steps you'll need to reproduce the attack done by different teams in 2012:

1. Firstly, you effectively need to grab the data you'll need consecutively. You might take the X.509 certs proposed by third parties, such as scans.io or the SSL Observatory; or grab it yourself directly as explained by Pedro (although I guess it might be easier to use specialized fingerprinting tools to pull them quickly instead of a script relying on OpenSSL).
2. Secondly, you need to extract the interesting data out of the certificate, this shouldn't be too hard, just make sure you can link the data back to where it came from. What you need to find is just the modulus used in each certificate and collect those in a big database.
3. Finally you need to perform batch GCD on the huge list of modulus you've extracted from those certs... That is probably the hardest part, I don't know if there exists distributed algorithms to perform it easily without having tons of RAM under the hand...

Now since you seem especially interested by how you could perform 1., you might also want to pull out all of the SSH keys you can find on the web, since most of them will also be RSA keys, as well as PGP keys (which was also done in one of the papers).
I've also once read a blog about doing this on Github's user SSH keys as well, but this would take months to perform, since Github has strict rules regarding its API and requests' rate.

Finally another team has built a key analyzer using the same methods to test your key against millions of other keys (and allowing them to build a bigger database at the same time, obviously): https://keytester.cryptosense.com/

Answer 2

You can download the ssl certificates from the most visited websites. See https://serverfault.com/questions/139728/how-to-download-the-ssl-certificate-from-a-website#192731

You can grab the list from Alexa, GTmetrix.com, Moz or Similarweb.

See http://www.alexa.com/topsites or https://en.wikipedia.org/wiki/List_of_most_popular_websites

You can use an API like https://www.programmableweb.com/api/alexa-top-sites to extract the website list. Or you can use the DNS information to have the list.