Weak RSA key generation: shared primes, ROCA and safe keys

An RSA public key includes a modulus n=pq and an exponent e. The private operation depends on information derived from p and q. In a correctly generated large key, factoring n should be infeasible. If two public moduli share one prime, n₁=pq and n₂=pr, then gcd(n₁,n₂)=p reveals that prime through a cheap public calculation.

Take n₁=11413=101×113 and n₂=12827=101×127. Their greatest common divisor is 101. Division yields the other factors 113 and 127. For the first key, φ(n₁)=100×112=11200. If e=3, the private exponent can be d=7467 because 3×7467=22401=2×11200+1. This is a complete small arithmetic demonstration of why sharing one factor destroys the key.

Real deployments use much larger moduli, but a greatest-common-divisor calculation remains efficient. The 2012 Mining Your Ps and Qs research connected many observed weak network keys to insufficient randomness during generation, especially on devices. A cryptographically strong library cannot create unpredictability from a cloned or badly seeded random source.

Exact duplicates mean two systems use the same modulus, possibly through deliberate sharing or image cloning; gcd(n,n)=n does not by itself factor it. Shared-prime detection finds a different failure. ROCA (/domains/identity-crypto/key-management-pki/roca-infineon-weak-keys/) identified restricted mathematical structure in primes from a particular generator; its detection and factorization approach is not simply a shared-prime search. A clean result from one detector therefore cannot certify all RSA generation.

Key length, randomness, prime selection, implementation, and provenance are separate review dimensions. A 2048-bit key generated by a vulnerable process is not repaired by its size. Conversely, seeing a manufacturer name or an old certificate is not sufficient evidence that a particular public key is vulnerable. Preserve the public key fingerprint and the exact detector result.

Different public exponents do not prevent a shared-prime attack because the gcd uses only the moduli. In the exercise, A and C use e=3 while B uses e=65537, which is coprime to B’s φ(n)=12600. Reusing e=3 for B would not form a valid RSA key because 3 divides 12600.

Fix or replace the generator and ensure the platform has a functioning cryptographic random source before generating replacement keys. Then replace certificates or identity bindings, deploy the new private keys, remove old trust where appropriate, and test consumers. Reissuing a certificate around the same modulus preserves the vulnerable key.

Decide what key compromise would expose. An RSA signing key can enable impersonation or forged signatures; an RSA decryption key may expose data encrypted to it. Historical TLS exposure depends on the negotiated key exchange and retained traffic, not just the certificate’s RSA label. An RSA certificate used to sign an ephemeral ECDHE handshake is different from RSA key transport, which DROWN (/domains/identity-crypto/encryption/drown/) attacked.

Fleet scanning can compare public keys without collecting private keys. Track duplicates separately from shared factors, associate findings with owners, and retain generation provenance. A public detector is useful triage evidence, but repair still requires identifying every service, credential, and backup that depends on the affected key.

Generate new keys on systems with a seeded operating-system random source, never on the first boot of a cloned image or a device without an entropy source. Then check what you already have: this Python module generates a key with sound parameters and compares a fleet’s RSA public keys pairwise for duplicates and shared primes. It was tested with cryptography 50 on Python 3.14 using real 2048-bit keys and a modulus deliberately built from two of their primes. For tens of thousands of keys, use a batch-GCD tool, and run roca-detect from the ROCA researchers on the same keys to catch the structured primes a gcd cannot see.

from itertools import combinations
from math import gcd

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa


def new_rsa_key() -> rsa.RSAPrivateKey:
    # e = 65537 and 3072 bits (128-bit security). Generate on a host whose OS random source is
    # seeded, not on first boot of a cloned image.
    return rsa.generate_private_key(public_exponent=65537, key_size=3072)


def shared_prime_report(public_keys: dict[str, bytes]) -> list[tuple[str, str, str]]:
    """Compare a fleet's RSA public keys (PEM) pairwise. Fine for a few thousand keys;
    use a batch-GCD tool for more."""
    moduli = {name: serialization.load_pem_public_key(pem).public_numbers().n for name, pem in public_keys.items()}
    findings = []
    for (a, n_a), (b, n_b) in combinations(moduli.items(), 2):
        if n_a == n_b:
            findings.append((a, b, "same key: replace both"))
        elif gcd(n_a, n_b) > 1:
            findings.append((a, b, "shared prime: both keys can be factored"))
    return findings

The positive case is a successful operation with the new key and expected identity. The negative case is rejection of the retired credential after the chosen cutoff. The boundary case is a dependent consumer with a cached or pinned old public key: it must receive a controlled trust update rather than an indefinite exception.

Compare public-key fingerprints, not only certificate serial numbers. Run the relevant generation-failure checks on new keys and record their scope. A successful detector result means that its specific fingerprint or shared factor was not found; it is not proof of an unpredictable generator or absence of all cryptographic weaknesses.

Sources & further reading

The standards, specifications and documentation behind the guidance above. Each is the evidence for a claim on this page; consult it for detail beyond the defaults and versions listed here.

1. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. Extended version, Rev. 2 (July 2012).
2. CRoCS: ROCA — Vulnerable RSA Generation. 16 October 2017.
3. RFC 8017: RSA Cryptography Specifications Version 2.2. November 2016.
4. OWASP Cryptographic Storage Cheat Sheet
5. NIST IR 8547 (initial public draft): RSA and elliptic-curve transition dates. November 2024.
6. CRoCS: ROCA detection tool (roca-detect)

Reference information

Tags

Key managementPKI and certificatesHistorical cryptographic attacks

SDLC phase

Maintenance

Role

Developers

ASVS 5.0.0 requirements

v5.0.0-11.6.1 · v5.0.0-11.2.3 · v5.0.0-11.5.1

Download this guide as Markdown

Continue exploring