Common-factors attack

As explained in Hacking Cryptography

A cryptanalytic attack that factors RSA moduli by finding a prime factor shared by two public keys.

A common-factors attack breaks RSA when two independently generated public moduli reuse a prime. For public keys (n1,e1) and (n2,e2), computing gcd(n1,n2) reveals the shared prime rather than 1. An attacker can then divide each affected modulus to recover its other factor and reconstruct the private key. section 8.4.1

The failure is not RSA arithmetic itself but key generation: poor entropy or a weak random-number generator can cause devices to select the same primes. Public RSA keys are sufficient for detection, so one faulty population can expose multiple private keys and encrypted traffic. section 8.4.1

Shared prime example

n2 = 269 × 839 and n3 = 151 × 269 share 269, so gcd(225691,40619) = 269. That GCD immediately factors both moduli enough to recover their private-key material. section 8.4.1

Figure 8.15 Moduli that share prime factors reveal the shared factor when calculating their GCD.

The figure visualizes why a nontrivial GCD of two RSA moduli exposes their reused prime factor. section 8.4.1

How Hacking Cryptography covers it

How deep it goes

Works through GCD detection, batch processing, factor recovery, and Go private-key reconstruction.

Examples

Demonstrates four toy moduli, a 512-prime pool generating 48 keys, and recovery of 14 private keys.

What it assumes

Assumes RSA public and private key structure while explaining GCD-based shared-factor recovery.

What you can do after

Diagnose/debug weak RSA key generation by batch-testing public moduli and reconstructing affected private keys.

How it connects

Connects RSA, public-key cryptography, greatest common divisor, entropy, random number generation, and TLS.

liveBookmanning.com

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

Related concepts

• greatest common divisoruses · A greatest common divisor is a common divisor maximal under divisibility, conventionally selected as positive for integers or monic for polynomials.
• batch GCD algorithmaddressed by · A technique for efficiently computing the greatest common divisor of each number in a collection with the product of the other numbers.

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.