THE GARDEN

Complex Multiplication (CM) Prime Factorization Backdoor

Updated 19 Sep 2026

• •

  What it is

  • •

    An extremely advanced structural weakness where one RSA prime is generated with a specific algebraic form, $p = (D s^2 + 1)/4$ for a fixed small negative "discriminant" $D$ and random $s$ — the same form that shows up in complex-multiplication (CM) theory for elliptic curves with a specific, unusually small class number. This isn't a coincidence: it lets an attacker construct an elliptic curve not over the usual integers-mod-$N$, but over a specialized quotient ring built from $N$ and the Hilbert class polynomial $H_D$ associated with that discriminant — an "anomalous" curve whose order is exactly $p$ when reduced modulo $p$. Running a Montgomery-ladder scalar multiplication $[N]P$ on that curve and mapping the resulting denominator back down to $\mathbb{Z}/N\mathbb{Z}$ produces a value that's frequently a nontrivial multiple of $p$ — so $\gcd(\text{that value}, N)$ splits off the factor, a variant of the elliptic curve factorization method (ECM) specialized for this exact prime structure.

• •

  When to apply

  • •

    One RSA prime is generated as $p = (D s^2+1)/4$ for an explicit small discriminant $D$ (here $D=-427$) — an extremely specific, research-paper-level red flag rather than something to stumble on by pattern-matching alone.

• •

  Math

  • •

    The full construction (building the class group $\mathbb{Z}/N\mathbb{Z}[j]/(H_D(j))$, defining the curve parameters $A,B$ over it, running the Montgomery ladder in that ring, and mapping the projective $Z$-coordinate of the result back to a multiple of $p$) is genuinely graduate-level algebraic number theory and elliptic curve theory — see the discussion of complex-multiplication discriminants for elliptic-curve-based factorization methods for the rigorous background this challenge draws on. This is about as advanced as CTF cryptography gets; treat the referenced write-up/paper as the authoritative source rather than expecting a short self-contained derivation here.

• •

  Worked example

  • •

    This page records the challenge’s intended complex-multiplication backdoor and the historical solve route. The attack was not independently re-derived in these notes. Keep the supplied reference implementation or paper beside the challenge inputs, and accept a factor only after $1<p<N$ and $p\mid N$.

• •

  Practical alternative

  • •

    Check FactorDB (Pragmatic Factorization Lookup) first: for a modulus this specifically and publicly structured, it's entirely reasonable (and was how this challenge was actually solved) to check whether the number has already been factored and published, rather than reimplementing a research paper's algorithm from scratch under time pressure.

• •

  Python / SageMath

  • •

    See the full reference implementation linked from the challenge write-up; it is long enough (custom modular inverse in the quotient ring, Montgomery dbl/add formulas, the ladder itself, and the final denominator-to-factor mapping) that reproducing it here wouldn't add clarity over reading the original.

  • •

    https://github.com/crocs-muni/cm_factorization

  • •

    https://www.cryptohack.org/challenges/rsa_backdoor/solutions/

• •

  Related

  • •

    RSA (Textbook Construction)

• •

  Cards

  • •

    What algebraic form makes a prime vulnerable to this specific attack?

    • •

      p = (D·s² + 1)/4 for a small, fixed discriminant D — the same shape as complex-multiplication discriminants for elliptic curves with small class number.

  • •

    What's a legitimate, pragmatic alternative to reimplementing the full attack under time pressure?

    • •

      Checking whether the specific modulus has already been factored and published on a service like FactorDB.

◌ Explore connections in Graph view