Batch GCD ssh key challenge

Here is a little challenge I have had some fun with recently.

The Greatest Common Divisor (GCD) method can quickly find any common denominator between two numbers. This even works on very large numbers such as those used by RSA. If you want to try it you can write a method in a few lines of code to find the factors between these two 1024 bit numbers :

154562462709421668048811029574429176339967582770033927576824633187099552180626760770554766161885657196312518658221149688394800043151559510354818420232102676069730902564150494088745313126769777823443395885737730234868902723737890922926976276986298764777507242621301740051336797119228435868695641797422930394301

141870892963640483906191484688359999906901497888195706215571887802641521733841862353130672719272343785182876822221422152533930744933871548118719685110452659915157122801280912706475082870290416497225380769325061108597080567715885948417156740160002970573069043853048947718197839111694567700297700024292552486341

If you can find a common factor you can of course find the other factors of each number by simple division.

There is such a thing as the batch GCD algorithm http://facthacks.cr.yp.to/batchgcd.html. This was used in 2012 to test millions of deployed RSA keys. That obviously took some time and computing hardware. You should be able to run this challenge in a few minutes on a laptop.

This file https://s3-eu-west-1.amazonaws.com/batchgcd/10000_ssh_pub_keys.gz has a list of 10^4 ssh public keys of various lengths. Hidden amongst them are two which share a common factor. Your task is find them with the batch GCD algorithm. You can either implement your own batchGCD from the algorithm as described in the article or there are a few implementations out there. Once you have identified the two public keys and their prime factors you have all the information you need to reconstruct the ssh private keys.

With one of the private keys sign the unzipped file. This is not something you normally do with a ssh key but is possible with.

openssl dgst -sha256 -hex -sign reconstructed-private-key 10000_ssh_pub_keys

If you want you can email the output to: batchGCD at fishtrap dot co dot uk for a final check that you have constructed the keys correctly.