Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292

A lattice-based extension of Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions that recovers a small RSA private exponent up to d < N^0.292 (Wiener's proven bound tops out at d < (1/3)N^0.25) by casting the RSA key equation as a bivariate small-root problem and solving it with Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction over a lattice reduced by LLL Reduction — the polynomial-time workhorse behind almost every lattice attack.

The signal that gives it away

- Same surface artifact as Wiener: a public exponent e that is huge — full-size, comparable in bit-length to N, instead of a small e like 3 or 65537 — which is the classic tell that d was chosen small (since e·d ≡ 1 mod φ(n) forces e up if d is down). - **The concrete trigger for reaching for Boneh-Durfee specifically is a negative result, not the size of e alone: you ran Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions's continued-fraction expansion of e/N and none of the convergents pass the consistency check** — no convergent k/d gives an integer φ = (e·d − 1)/k, or the resulting quadratic x² − (N − φ + 1)x + N has no integer roots. That failure is the actual signal, because Wiener is cheap to try first and is proven to succeed only when d < (1/3)N^{1/4} — the 1/3 factor is part of the bound, not a rounding nicety, and Wiener structurally cannot succeed once d exceeds that. - The exploitable window is (1/3)N^{1/4} < d < N^{0.292} — a narrow-looking but real gap where continued fractions provably fail yet the private exponent is still small enough for a lattice attack. If d is smaller than (1/3)N^{1/4}, Wiener alone already gets it and Boneh-Durfee is unnecessary extra machinery; if d is larger than N^{0.292}, neither technique applies and you're looking at Partial Key Exposure — recovering RSA when part of p or d has leaked (if you have leaked bits of p or d) or generic factoring instead.

How it's exploited

Start from e·d ≡ 1 (mod φ(n)), i.e. e·d = 1 + k·φ(n) for some integer k, with φ(n) = n + 1 − (p+q). Substitute A = n+1 and y = −(p+q) (both small relative to k and n respectively — y is bounded by roughly N^{1/2}, k by roughly N^{δ} for your working guess of δ) to get the bivariate modular polynomial

`` f(x, y) = x·(A + y) + 1 ≡ 0 (mod e) ``

whose small root (x0, y0) = (k, −(p+q)) you recover with Coppersmith's lattice method:

1. Confirm you're in the window. Wiener already failed (no consistent convergent) — that's the precondition, not an optional check. 2. Pick a working `δ` such that you're hypothesizing d < N^δ. Don't start at the theoretical ceiling: begin conservative (δ ≈ 0.26 is a reasonable first guess) and step up toward 0.292 only if the lower guess fails to produce a root — an over-optimistic δ with under-sized lattice parameters just fails silently, it doesn't error out helpfully. 3. Build the Boneh-Durfee lattice (x-shifts parameter m, y-shifts parameter t) over f(x,y) mod e^m, or use a packaged small-roots routine built on the same machinery as Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction: ``python # SageMath: bivariate Coppersmith via a Boneh-Durfee lattice P.<x,y> = PolynomialRing(Zmod(e)) A = (n + 1) f = 1 + x*(A + y) # build/reduce lattice (m, t params), LLL, resultant -> (k, s) -> p+q -> factor n ` The field-tested go-to tool for this in a CTF is boneh_durfee.sage from mimoo/RSA-and-LLL-attacks — it takes delta (your d < N^δ guess), m, and t` as the tunable knobs. 4. **Run LLL Reduction — the polynomial-time workhorse behind almost every lattice attack on the assembled lattice (the packaged tool does this internally). Take two independent short output vectors, treat them as polynomials, and compute their resultant to eliminate one variable and solve for `x0` (=`k`) and `y0` (=`−(p+q)`). 5. Recover and verify.** φ(n) = n + 1 + y0; factor n via the usual quadratic z² − (n − φ + 1)z + n = 0 (same final step as Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions). Always check the recovered p, q actually multiply to n before trusting the run — like any LLL-derived candidate, a short vector can be short and still wrong (see LLL Reduction — the polynomial-time workhorse behind almost every lattice attack's general verification warning).

Parameter tuning, field-tested

m and t control lattice size — bigger reaches closer to the 0.292 bound and is more forgiving of a slightly-off δ guess, but cost grows fast, so don't over-provision by default. A workable default relation is t ≈ τ·m with τ ≈ 1 − 2δ, subject to 1 ≤ t ≤ m. If a run errors or comes back empty, increase m (and t accordingly) before assuming the technique doesn't apply. As a last resort, shrink the bound X on x if it was set looser than the actual root size.

Built on Lattice Fundamentals — encoding a bounded unknown as a short vector and Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction. Related: Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Lattice Fundamentals — encoding a bounded unknown as a short vector RSA Fundamentals — the routing hub: which artifact points to which attack Partial Key Exposure — recovering RSA when part of p or d has leaked

What does NOT work

- **Re-running or tweaking Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions once it has already failed. Continued fractions are only guaranteed to work below `(1/3)N^{1/4}` — that's a structural ceiling of the convergent search (the 1/3 factor included), not a tuning problem. A Wiener failure is the signal to switch technique entirely, not to re-check the arithmetic. - Treating Boneh-Durfee as a deterministic, always-succeeds-if-in-range algorithm.** Unlike Wiener's rigorous continued-fraction argument, Boneh-Durfee's 0.292 bound rests on a *heuristic* extension of Coppersmith's method to two variables: it assumes the resultant of the two lattice-derived polynomials doesn't vanish (equivalently, that they're algebraically independent). This is usually true in practice but isn't proven, so occasional non-convergence — especially with d close to the 0.292 edge — is a known failure mode of the method itself, not necessarily a parameter mistake. - Jumping straight to `δ = 0.292` on the first attempt. Higher δ demands larger m/t to actually surface the root; an aggressive guess paired with small lattice parameters just returns nothing, and it's easy to misread that as "d isn't small" when it's really "lattice too small for this δ." Start conservative and step up. - Grinding `m`/`t` upward hoping to push past `d > N^0.292`. That threshold is a genuine wall from the underlying lattice-volume argument, not a soft limit you can out-compute. Beyond it, this technique and Wiener both offer nothing — reach for Partial Key Exposure — recovering RSA when part of p or d has leaked if you have any leaked high/low bits of p or d, or fall back to generic factoring. - Trusting a recovered `(x0, y0)` without re-deriving `φ(n)` and checking it factors `n`. A candidate short vector that "looks right" (plausible bit length, right sign) can still be numerically short but semantically wrong, same general caveat as any LLL Reduction — the polynomial-time workhorse behind almost every lattice attack output — verify before spending more time downstream.