Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction

Coppersmith's method finds the small integer root of a polynomial that is only known to hold *modulo* N (or modulo an unknown factor of N), by turning the modular equation into a lattice problem that LLL Reduction — the polynomial-time workhorse behind almost every lattice attack can solve — it is the general tool underneath most "part of the secret is known, recover the rest" RSA attacks.

The signal that gives it away

- The problem can be phrased as "I know a polynomial f(x) such that f(x0) ≡ 0 (mod N) for some small x0, and I don't know x0." Small here is quantitative, not vague: for a degree-d polynomial, Coppersmith's theorem guarantees recovery whenever |x0| < N^{1/d} (verified against Wikipedia's statement of the bound). If the unknown is bigger than that, this technique alone will not reach it — you need a different bound (e.g. Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 pushes further by reformulating the problem, not by beating this bound directly). - Concretely, the tell is one of: most of a message is known and only a short unknown chunk (a random pad, a counter, a suffix) is missing — a *stereotyped message*; most of a prime factor `p` is known (high bits or low bits leaked, e.g. from a side channel or a truncated printout) and only a short chunk of p is missing — *partial key exposure*, see Partial Key Exposure — recovering RSA when part of p or d has leaked; or two ciphertexts of related messages where the relation has an unknown small offset — this is the Coppersmith "short-pad" variant, distinct from Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD where the relation is fully known and a plain polynomial GCD suffices without any lattice work. - Small e (textbook e=3 or e=5) makes the polynomial low-degree, which pushes the recoverable-root bound N^{1/d} up and makes the attack cheap; the technique still works for larger e but the lattice gets bigger and slower to reduce. - Bivariate/modular variants of the exact same idea power Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 (small private exponent d reformulated as a two-variable small-root problem) — recognizing "this is secretly a Coppersmith small-roots problem in disguise" is itself a transferable skill once you've done it once.

How it's exploited

1. Write the relation as `f(x) ≡ 0 (mod N)` (or mod the unknown factor `p`) with the small unknown isolated as x. Getting this polynomial right is most of the work — the lattice machinery afterward is close to mechanical. 2. Bound the unknown. You need a concrete numeric bound X with |x0| < X (e.g. "the missing chunk is at most 64 bits," from the challenge's own padding scheme or leak size). The tighter this bound, the smaller and faster the lattice. 3. Hand it to a packaged small-roots routine rather than hand-rolling the lattice. In practice this is SageMath's small_roots, which builds the shift-polynomial lattice and runs LLL internally: ``python # SageMath P.<x> = PolynomialRing(Zmod(N)) f = x^e - c # textbook, or a stereotyped polynomial with a known constant part f = f.monic() roots = f.small_roots(X=2^bits_unknown, beta=1.0, epsilon=1/30) ` 4. **For roots modulo an unknown *factor* p of N** (the partial-key-exposure case) rather than modulo the full N, set beta below 1.0 — beta=0.5 is the standard choice when the modulus you're really working against is p ≈ sqrt(N) rather than N itself. This is the parameter that most often trips people up: leaving beta=1.0 on a factor-of-N problem silently returns nothing, because the bound the routine is optimizing for no longer matches the problem. 5. **Tune beta and epsilon (and, for hand-built lattices, the shift-polynomial degree/multiplicity parameters m, t) to trade lattice size for reach.** Larger lattices (bigger m) get you closer to the theoretical bound N^{1/d} at higher LLL cost; smaller epsilon` tightens the bound estimate but also raises cost. If the default call returns no roots, this — not "the technique doesn't apply" — is usually the first thing to adjust. 6. This is the general engine behind three named attacks in this wiki: Partial Key Exposure — recovering RSA when part of p or d has leaked (known high/low bits of p or d), the Coppersmith short-pad case that generalizes Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD to an *unknown* small offset between two related messages, and the bivariate lattice inside Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292. Recognize which shape you're in before reaching for the tool — it changes the polynomial and the beta you need, not the underlying machinery, which is always LLL Reduction — the polynomial-time workhorse behind almost every lattice attack on a lattice built per Lattice Fundamentals — encoding a bounded unknown as a short vector. Cleanup of a returned candidate root against the original equation sometimes uses Polynomial GCD — the Euclidean algorithm on polynomials, and the trick that recovers a shared root when multiple roots come back and need disambiguating.

What does NOT work

- Reaching for this when the unknown is not actually small relative to `N^{1/d}`. The bound is not a soft guideline — it is the theorem. If your unknown is, say, half the bit-length of p for a degree-1 polynomial, no amount of lattice tuning saves you; you are past the provable region and need a fundamentally different approach (or the challenge intends a different technique). - Treating `beta=1.0` as a safe default when the modulus is really an unknown factor `p`, not `N`. This is the single most common "it just returns an empty list" failure. If you're solving "known high bits of p," you are implicitly working mod p, and p is only about sqrt(N) — leave beta at 1.0 and the routine's internal bound math assumes a modulus the size of N, which is wrong by a large margin. - Skipping the packaged `small_roots` and hand-rolling the lattice from scratch as a first move. The construction (shift polynomials, picking m/t, balancing lattice rows) has enough subtlety that reinventing it under time pressure burns the hours the tool exists to save; hand-roll only once the packaged version's assumptions genuinely don't fit the problem shape. - Using this when the relation between two ciphertexts is fully known (not just "there exists some small unknown offset"). If the relation is a specific, known linear function m2 = a·m1 + b, that's plain Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD — a polynomial GCD, no lattice, no small-root bound to worry about. Reaching for Coppersmith here is solving an easier problem the hard way. - Assuming a larger `e` makes the technique fail outright. It doesn't fail, it degrades: the polynomial degree d grows with e, which shrinks the provable bound N^{1/d} and grows the lattice dimension needed to reach it. What actually fails is running the naive small X guess against a large-e polynomial without re-deriving the bound — check the arithmetic on N^{1/d} against your assumed unknown size before concluding the attack doesn't apply.

Related

LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Lattice Fundamentals — encoding a bounded unknown as a short vector Partial Key Exposure — recovering RSA when part of p or d has leaked Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 Polynomial GCD — the Euclidean algorithm on polynomials, and the trick that recovers a shared root