david wong

Hey ! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

How to efficiently compute a batch GCD December 2015

Heard a bit late about the factorable research results and how they used batch gcd to recover a bunch of servers' private keys.

The question one could think of is how to efficiently do a batch gcd on a big set of public keys?

From this utility:

  • Actual pairwise GCD
    This performs n*(n-1)/2 GCD operations on the moduli. This is slow. Don't use this.
  • Accumulating Product
    This iterates over all input moduli, performing a GCD of each one against the product of all previous. Once it finds a candidate, it scans all previous moduli to find out which ones it shared a factor with (either GCD or division, depending on whether one or both were found). The main scan cannot be done in parallel, and even though it seems like this is O(n), the increasing size of the accumulated product results it lots of long multiplication and long divison so it's still painfully slow for large numbers of moduli.

Looks like the most efficient ways come from Dan Bernstein (again!), in a 7 pages paper

Well done! You've reached the end of my post. Now you can leave me a comment :)