Batch GCD algorithm

As explained in Hacking Cryptography

A technique for efficiently computing the greatest common divisor of each number in a collection with the product of the other numbers.

A batch GCD algorithm finds shared factors across many RSA moduli without computing every pairwise GCD. Let N be the product of all moduli. For each modulus n, compute gcd(n, N/n): a nontrivial result reveals a prime factor shared with another public key. section 8.4.1

A direct batch procedure is:

• Multiply every public modulus into one product. section 8.4.1
• For each modulus, derive the product of all other moduli and take its GCD with that modulus. section 8.4.1
• Ignore GCD results of 1 or the modulus itself; otherwise treat the result as p, derive q = n/p, then reconstruct the RSA private exponent. section 8.4.1

Shared-prime moduli

For 225691 = 269 × 839 and 40619 = 151 × 269, each modulus has GCD 269 with the product of the other moduli. That factor permits recovery of the corresponding private keys. section 8.4.1

Figure 8.17 Using a remainder tree to efficiently calculate batch GCD

A remainder tree illustrates the more efficient batch-GCD approach for large collections. section 8.4.1

How Hacking Cryptography covers it

How deep it goes

Works through total-product GCDs and private-key reconstruction, then points to product and remainder trees for greater efficiency.

Examples

Uses four concrete RSA moduli, including two sharing 269, plus a Go test recovering private keys from generated public keys.

What it assumes

Assumes familiarity with RSA moduli, prime factors, and GCD while demonstrating the batch calculation directly.

What you can do after

Build it from scratch to identify shared RSA factors and reconstruct affected private keys.

How it connects

Connects RSA, public keys, private exponents, greatest common divisors, prime factors, random number generation, and product trees.

liveBookmanning.com

Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

• algorithmkind of · An algorithm is a finite, precisely specified procedure for performing a computation, transforming inputs into outputs, or solving a problem.
• common-factors attackaddresses · A cryptanalytic attack that factors RSA moduli by finding a prime factor shared by two public keys.

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.