Boneh-Durfee Attack (Lattice Attack on Small RSA Private Exponent)

Updated 19 Sep 2026

• •

  What it is

  • •

    Wiener's attack recovers a small private exponent $d$ up to $d < \frac{1}{3}N^{1/4}$; Boneh and Durfee showed a substantially stronger bound, $d < N^{0.292}$, is achievable using lattice basis reduction (LLL) applied to a bivariate modular polynomial via Coppersmith's method, rather than continued fractions. High-level idea: the RSA key equation $ed \equiv 1 \pmod{\phi(N)}$ can be rewritten as a polynomial in two unknowns (related to $d$ and to $k$, the same integer from Wiener's derivation) with a "small" root exactly when $d$ is small; Coppersmith's technique builds a carefully-chosen lattice of polynomials sharing that root modulo a power of $N$, and LLL-reduces it to find a short lattice vector revealing the actual (non-modular) polynomial the root satisfies — solvable directly from there.

• •

  When to apply

  • •

    A challenge's private exponent $d$ is small enough to be dangerous, but was deliberately chosen just outside Wiener's $N^{1/4}$-ish bound (protecting specifically against Wiener) while still well inside the larger $N^{0.292}$ Boneh-Durfee bound — a common "harder version of the same idea" framing in CTFs, and exactly what's implied by a title/flag explicitly contrasting the two attacks.

• •

  Math

  • •

    The full derivation requires Coppersmith's theorem for finding small roots of modular polynomials via lattice reduction — see Boneh & Durfee's original paper ("Cryptanalysis of RSA with Private Key d Less than N^0.292") for the rigorous construction; this is genuinely research-level machinery, not a formula that reduces to a few lines.

• •

  Worked example

  • •

    For a 2048-bit modulus, $N^{0.292}$ is about $2^{598}$. A 512-bit $d$ can lie above Wiener’s roughly $2^{510}$ cutoff and below the Boneh–Durfee range. The exponent comparison only shows that the instance is in the intended regime; a practical lattice attack still depends on parameters and the usual algebraic-independence step.

• •

  Python

  • •

    Not practical by hand — this needs a real lattice-reduction (LLL) implementation, which Python alone doesn't provide out of the box.

• •

  SageMath

  • •

    This is squarely a "you need Sage" case — Sage has LLL (Matrix.LLL()) built in, the whole engine the attack depends on:

  • •

    # using a standard public boneh_durfee.sage implementation:
    # load("boneh_durfee.sage")
    # d = boneh_durfee_attack(N, e, delta=0.28)  # delta ~ log_N(d), tuned just above Wiener's range
    

• •

  Related

  • •

    Wiener's Attack (Continued Fractions, Small Private Exponent)

  • •

    RSA (Textbook Construction)

• •

  Cards

  • •

    What bound on d does the Boneh-Durfee attack achieve, compared to Wiener's?

    • •

      d < N^0.292, versus Wiener's d < (1/3)N^0.25 — a meaningfully larger range of "small" d values are recoverable.

  • •

    What mathematical machinery does Boneh-Durfee rely on that Wiener's attack doesn't need?

    • •

      Coppersmith's method for finding small roots of modular polynomials via lattice basis reduction (LLL), rather than continued fractions.

◌ Explore connections in Graph view