Breaking RSA with Weak Keys: Shared Primes and Pollard's p-1

Breaking RSA with Weak Keys: Shared Primes and Pollard’s p-1

Introduction

RSA rests on one hard problem: factoring a large number N that is the product of two secret primes. For properly generated keys that problem is hopeless, and RSA is safe. But the security lives entirely in how those primes are chosen, and when the key generation goes wrong, factoring N can become trivial.

This guide shows two ways it goes wrong, both of which have broken real keys in the wild. First, when two different keys accidentally share a prime, a single greatest common divisor factors both in an instant. Second, when a prime p is chosen so that p - 1 has only small factors, Pollard’s p - 1 method factors N with no search at all. Neither attack touches the strength of RSA itself. They punish weak randomness and careless prime selection.

Table of Contents

• RSA in One Paragraph
• Shared Primes: One GCD Breaks Two Keys
• Why Shared Primes Happen
• Pollard’s p-1 Method
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

RSA in One Paragraph

An RSA key is built from two secret primes, p and q. Their product N = p * q is public, along with a public exponent e, usually 65537. The private exponent d is the inverse of e modulo (p - 1)(q - 1). Anyone who learns p and q can compute d and read every message. So factoring N is the whole game, and both attacks here are just two ways to factor N when the primes were chosen badly.

Shared Primes: One GCD Breaks Two Keys

Suppose two people generate RSA keys independently, and by accident both use the same prime p. The first modulus is N1 = p * q1, the second is N2 = p * q2, with different second primes. Both moduli are public. The greatest common divisor of two numbers is the largest factor they share, so:

gcd(N1, N2) = p

That single computation, which takes microseconds even on 1024-bit numbers, hands over the shared prime. Dividing each modulus by p gives the other prime, and from the two factors each private key follows at once. Scanning a large collection of public keys for any pair that shares a factor is called a batch GCD, and it has recovered tens of thousands of real keys from the internet.

Why Shared Primes Happen

Two keys sharing a prime sounds impossibly unlikely, and for good randomness it is. The trouble is bad randomness. Devices that generate keys at first boot, before they have gathered any entropy, can seed their prime generators from nearly identical states. Different devices then draw primes from a small, overlapping pool, and collisions become common.

This is not hypothetical. In 2012 two research teams scanned millions of public keys from the internet and found that a few in every thousand shared a prime with another key, letting the researchers factor both. Headless routers and embedded devices were the worst offenders. The RSA math was flawless; the entropy at boot time was not.

Pollard’s p-1 Method

The second attack needs only one key, but a special one. Pollard’s method factors N quickly when one prime p has the property that p - 1 is smooth, meaning all of its prime factors are small. It works through a corner of number theory called Fermat’s little theorem, which says a^(p-1) is congruent to 1 modulo p for any a not divisible by p.

The method computes a = 2^(M) modulo N, where M is the product of every integer up to some bound B. If p - 1 divides M, which happens exactly when p - 1 is B-smooth, then a is congruent to 1 modulo p, so p divides a - 1. Taking gcd(a - 1, N) then reveals p. The attacker never knows p in advance; it falls out of the GCD. The defense is simple: choose primes so that p - 1 and q - 1 each have at least one large factor, which is called using strong primes.

Interactive Visualizer

The visualizer above runs the shared-prime attack on real 1024-bit RSA keys. Four people generate keys independently, but a weak random number generator makes two of them reuse a prime. The visualizer computes the GCD of every pair of moduli, finds the one pair whose GCD is greater than one, and uses that shared prime to factor both moduli and recover both private keys, verifying each with a real encryption round-trip. Every number is a genuine 1024-bit RSA modulus, with nothing faked.

Watch how a value that would take longer than the age of the universe to factor directly falls apart the instant it shares a prime with a neighbor. The attacker never factors anything the hard way. One careless collision does all the work.

A Worked Example

Four people, Alice, Bob, Carol and Dave, generate 1024-bit RSA keys. A weak RNG makes Dave draw the same first prime that Alice used. The attacker, who has only the public moduli, compares every pair:

Alice N = 0x7c3523b20ef5...141c01   (1023 bits)
Bob   N = 0x8bb8731aec7a...d12e07   (1024 bits)
Carol N = 0x653161490705...2dc6e5   (1023 bits)
Dave  N = 0x9da718b888a5...e7f3db   (1024 bits)

gcd(Alice, Dave) = 0xb5d47aecfb56...ae7185   <- a shared secret prime
recovered Alice's private key d = 0x3ee330e59089...caefa1
recovered Dave's private key  d = 0x2c8a8d3d75bd...99b761

Both private keys fall out, confirmed by a signing round-trip. The Pollard attack is just as sharp against its special key:

N = SMOOTH_P * Q_ORD   (537 bits)
found factor at j=179: p = 0x212336632509...923601
recovered private key d = 0xeed71b4de969...0c2401

The prime came out at step 179, because the largest prime factor of p - 1 is 179. No searching, no luck, just arithmetic that a well-chosen prime would have made impossible.

Python Implementation

The code is self-contained and runnable, using fixed primes so the worked example repeats exactly. It builds the shared-prime scenario and runs the batch GCD, then factors a key with a smooth p - 1 using Pollard’s method. Each recovered key is checked with a real RSA round-trip.

# rsa_weak_keys.py
#
# Two ways RSA keys break when the primes are chosen badly. (1) Shared primes: if two moduli share a
# prime, gcd(N1, N2) returns it instantly, factoring both; scanning many keys this way is a "batch GCD",
# which recovered tens of thousands of real internet keys in 2012. (2) Pollard's p-1: if p-1 is smooth
# (all prime factors small), then 2^(B!) - 1 is divisible by p, so gcd(2^(B!)-1, N) reveals p. Neither
# attack weakens RSA itself; both punish weak randomness and non-strong primes. Keys here are real 1024-bit.
from math import gcd

E = 65537

P = [  # fixed 512-bit primes
    0xb5d47aecfb569d026ac91ee62847bd65d6523ee4555d93e191df1557986a8a97ae764a4af65577d86d8b3787b15e7890cd6836252a1246d53ee73fd2b5ae7185,
    0xaedf76573db272b82959e816d50565b2344563fcde120b1e828f9cd145bae73c4e62c615122e00203ae5e583b162967505d5e00a7978783eef741393e9124b4d,
    0xdb38a450059a15d2097efec3435da1995916e31fed010da07d19da2529efd4d119ec8215c8391667c32509620f1996e5910a5157e69c08e521bae820256adaa9,
    0xa3295239d206855eebdd0043d38ff0820bfe32e9d99794df8f387d11754981e472dfbc15a63d06d297658ab5d2694c5f6e29fe027b57fb9d44da0dfbe331612f,
    0x8d61e700f4ce47f203d5008de068328eeba9be97ee351a4bc81c8a1f47cf7e99e7e785760230d7d7377d514dbbd65e9d5e0d3928504bb097cafe62e253d8202f,
    0xb73aa858496f543d377c918c6dd5ba03c14598de724886e8ef1aaca4113e1056a961f295f764fc13e3ce588c965e5fe2d578b0ce4cfe9a1e348cd819ea86d12b,
    0xddf5ea1104c908813c0a61be2326344b9a1f4d3546b785c544d74e7f5ff3d91c0f599a8a3e0807b7ac44dcdb8bed06c3e12d15c815367e935c020e2ea4eb1ddf,
]
SMOOTH_P = 0x21233663250911eb5e079c35a03a7a1969e02e4b6a50298dd5d3929752e11f680923601  # p-1 is 180-smooth
Q_ORD = 0x9a17a8390450c5b085a1d5f571d81e3eaa47a749713845f9366fe5413e3c129b


def private_key(p, q):
    n = p * q
    return n, pow(E, -1, (p - 1) * (q - 1))


def rsa_roundtrip(n, d, msg=0x1234567890ABCDEF):
    return pow(pow(msg, E, n), d, n) == msg      # encrypt then decrypt


# ---- attack 1: shared primes via batch GCD ----
def shared_prime_attack(moduli):
    names = list(moduli)
    for i in range(len(names)):
        for j in range(i + 1, len(names)):
            g = gcd(moduli[names[i]], moduli[names[j]])
            if g != 1:
                return names[i], names[j], g
    return None


# ---- attack 2: Pollard's p-1 ----
def pollard_p_minus_1(n, bound=200):
    a = 2
    for j in range(2, bound + 1):
        a = pow(a, j, n)                         # builds a = 2^(j!) mod n
        g = gcd(a - 1, n)
        if 1 < g < n:
            return g, j
    return None, None


if __name__ == "__main__":
    # A weak RNG makes Dave reuse Alice's first prime P[0].
    moduli = {
        "Alice": P[0] * P[1],
        "Bob":   P[2] * P[3],
        "Carol": P[4] * P[5],
        "Dave":  P[0] * P[6],
    }
    print("=== Shared-prime attack (batch GCD) ===")
    a, b, p = shared_prime_attack(moduli)
    print(f"shared prime from {a} and {b}: {hex(p)[:16]}...")
    for name in (a, b):
        n = moduli[name]
        q = n // p
        assert p * q == n
        n2, d = private_key(p, q)
        print(f"  {name}: private key recovered, RSA round-trip = {rsa_roundtrip(n, d)}")

    print("\n=== Pollard's p-1 attack ===")
    n = SMOOTH_P * Q_ORD
    factor, j = pollard_p_minus_1(n, bound=200)
    assert factor == SMOOTH_P
    _, d = private_key(factor, n // factor)
    print(f"  factor found at step j={j} (p-1 is {j}-smooth)")
    print(f"  private key recovered, RSA round-trip = {rsa_roundtrip(n, d, 0xCAFEBABE)}")

Running it prints the worked example:

=== Shared-prime attack (batch GCD) ===
shared prime from Alice and Dave: 0xb5d47aecfb56...
  Alice: private key recovered, RSA round-trip = True
  Dave: private key recovered, RSA round-trip = True

=== Pollard's p-1 attack ===
  factor found at step j=179 (p-1 is 179-smooth)
  private key recovered, RSA round-trip = True

Limitations

Both attacks are devastating, but each needs its specific weakness to be present:

• Shared primes need a repeated prime. The GCD only helps when two keys actually share a factor. Against a single key, or a set of keys all made with good randomness, every pairwise GCD is 1 and the attack finds nothing.
• Batch GCD needs many keys. The power of the attack comes from scanning a huge collection and testing all pairs efficiently with a product tree. A handful of keys rarely collides; the 2012 breaks worked because they had millions.
• Pollard’s p-1 needs a smooth p-1. It only factors N when some prime has a smooth p - 1. Modern libraries avoid this by using strong primes or primes large enough that smoothness is astronomically unlikely, so the method almost never applies to real keys today.
• Neither attack factors a well-made key. Against properly generated RSA with good entropy and strong primes, both methods fail completely. They exploit mistakes in key generation, not any weakness in RSA.

Security Status

• RSA is secure only with correct key generation. The algorithm is sound, but it hands all of its security to the quality of its primes. Weak entropy or poor prime selection turns an unbreakable key into an open book, as both of these attacks show.
• Good randomness is non-negotiable. The shared-prime disaster was entirely an entropy failure, devices making keys before they had any randomness to work with. Seeding the random number generator properly, and never generating long-term keys at first boot, prevents it.
• Use library defaults. Modern crypto libraries generate primes correctly, with enough size and the right structure, and check for obvious weaknesses. The practical lesson is to use a well-tested library and a strong entropy source, and never to roll your own prime generation.

FAQ

How can a GCD break 1024-bit RSA so fast?

The GCD algorithm is extremely efficient, running in time proportional to the number of digits, not the size of the numbers. Factoring a 1024-bit number directly is infeasible, but computing the GCD of two of them takes microseconds. The attack works only because the two keys share a factor, which the GCD extracts directly.

Is sharing a prime really plausible?

With good randomness, no. With bad randomness it is common. Devices that generate keys before gathering entropy draw primes from a tiny effective pool, so different devices collide. Internet-wide scans in 2012 factored tens of thousands of real keys this way.

What makes a prime vulnerable to Pollard’s p-1?

A prime p is vulnerable when p - 1 factors entirely into small primes, called being smooth. Then the product of small numbers up to a modest bound is a multiple of p - 1, which is exactly what the method exploits. Strong primes, where p - 1 has a large factor, are immune.

Do these attacks affect modern RSA keys?

Rarely, because modern libraries generate primes properly. Shared primes can still appear in cheap embedded devices with weak entropy, and Pollard’s p-1 is a standard check that good key generators already defend against. Against a correctly made key, both attacks do nothing.

How do I protect my own keys?

Use a reputable crypto library, ensure a strong source of entropy before generating keys, and never generate long-term keys at device first boot. The library handles prime size and strength; your job is to give it good randomness and not to reinvent prime generation yourself.

References

1. Lenstra, Arjen, et al. “Ron was wrong, Whit is right,” 2012 (the shared-prime scan of public RSA keys).

2. Heninger, Nadia, et al. “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices,” USENIX Security 2012.

3. Pollard, John M. “Theorems on factorization and primality testing,” 1974 (the p-1 method).

4. The RSA guide on this site, whose key generation these attacks exploit: /blog/rsa_guide/