THE GARDEN

ROCA Vulnerability (Infineon RSA Key Generation Weakness)

Updated 19 Sep 2026

• •

  What it is

  • •

    ROCA ("Return of Coppersmith's Attack," CVE-2017-15361) is a real-world vulnerability discovered in RSA key generation used by Infineon smart-card/TPM chips: instead of generating primes uniformly at random, the flawed generator constructs each prime as $p = k \cdot M + (e_0^a \bmod M)$ for a fixed "primorial" $M$ (the product of the first several tens of small primes) and small unknown integers $k, a$ — drastically shrinking the effective search space for $p$'s "fingerprint" modulo $M$. This lets an attacker recover $p$ from $N$ alone using a two-stage attack: a discrete-log-style search narrows down candidate values of $a$, and Coppersmith's lattice-based method for finding small roots of a modular polynomial recovers the corresponding $k$, together pinning down $p$ exactly.

• •

  When to apply

  • •

    A challenge's prime-generation routine explicitly builds primes from a large "primorial" product of the first $n$ small primes combined with a modular-exponentiation term — this exact shape (not just "weirdly generated primes" in general) is the signature of ROCA specifically.

• •

  Math

  • •

    Full derivation requires the discrete-log stage over $(\mathbb{Z}/M\mathbb{Z})^\times$ plus a Coppersmith small-roots lattice construction — see the original ROCA paper ("The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli," Nemec et al., 2017) for the rigorous treatment; this is research-level cryptanalysis, not a formula reducible to a few lines.

• •

  Worked example

  • •

    No independent ROCA lattice derivation is claimed here. The practical method fingerprints the restricted prime structure, enumerates the small exponent residue, then uses a Coppersmith/Howgrave-Graham small-root step to recover a factor. Use a maintained reference implementation and verify $pq=N$.

• •

  Python

  • •

    Not practical by hand — the attack genuinely needs the discrete-log search plus lattice reduction machinery.

• •

  SageMath

  • •

    A "you need Sage" case for the same reason as Boneh-Durfee — LLL lattice reduction is core to the attack, and Sage's implementation is the community-standard reference:

  • •

    # using a public ROCA implementation, e.g. github.com/FlorianPicca/ROCA:
    # from sage_functions import *
    # p = roca_factor(N)
    # q = N // p
    ```
    

• •

  Related

  • •

    RSA (Textbook Construction)

• •

  Cards

  • •

    What real-world vulnerability does ROCA refer to, and what hardware did it affect?

    • •

      CVE-2017-15361, affecting RSA key generation in Infineon smart-card/TPM chips.

  • •

    What structural shortcut in prime generation does ROCA exploit?

    • •

      Primes built as p = k·M + (e^a mod M) for a fixed primorial M, drastically shrinking the effective randomness compared to a uniformly random prime.

◌ Explore connections in Graph view