THE GARDEN

Batch GCD Attack (Shared RSA Prime Across Keys)

Updated 13 Sep 2026

• •

  What it is

  • •

    A real-world attack (formalized in the 2012 "Mining Your Ps and Qs" paper) against poorly-seeded RSA key generators: if two different, independently-generated RSA keys happen to share one of their two prime factors — a real, observed failure mode when a device's random number generator has too little entropy at boot time — then simply computing $\gcd(N_1, N_2)$ across the two public moduli instantly reveals that shared prime, factoring both keys at once, with no private information and no advanced mathematics needed: just Euclid's algorithm, one pairwise GCD at a time.

• •

  When to apply

  • •

    You're given a large batch of independently-collected RSA public keys (not just one) — the tell isn't in any single key's math, it's in having many keys to check pairwise against each other.

• •

  Math

  • •

    If $N_1 = p \cdot q_1$ and $N_2 = p \cdot q_2$ for a shared prime $p$, then $\gcd(N_1, N_2) = p$ directly.

• •

  Worked example

  • •

    10 toy 256-bit moduli generated independently, except two of them (indices 3 and 7) deliberately sharing one prime factor: looping gcd() over every pair found exactly that pair and recovered the shared factor exactly.

• •

  Python

  • •

    from math import gcd
    from itertools import combinations
    for (i, n1), (j, n2) in combinations(enumerate(moduli), 2):
            g = gcd(n1, n2)
            if g != 1:
                print(f"keys {i} and {j} share factor {g}")
    

• •

  SageMath

  • •

    Not particularly relevant — plain gcd over a nested loop, equally simple in either language. (At true internet scale — millions of keys — a real batch-GCD algorithm computing all pairwise GCDs in O(n log n) rather than O(n²) matters a lot; for a CTF-sized set of tens of keys, the naive nested loop is entirely sufficient.)

• •

  Related

  • •

    RSA (Textbook Construction)

• •

  Cards

  • •

    What real-world failure mode does the batch-GCD attack exploit?

    • •

      Independently-generated RSA keys accidentally sharing one prime factor, typically from insufficient entropy in the random number generator used at key-generation time.

  • •

    Why does gcd(N1, N2) instantly reveal the shared factor, with no advanced math needed?

    • •

      If N1 and N2 share exactly one prime factor p, then p is by definition their greatest common divisor — Euclid's algorithm finds it directly.

◌ Explore connections in Graph view