Partial Key Exposure — recovering RSA when part of p or d has leaked

Some bits of an RSA prime factor p (or of the private exponent d) are known — usually from a corrupted key file, a truncated leak, or a side-channel dump — and Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction recovers the rest without brute force.

The signal that gives it away

- The challenge hands you something besides the usual (n, e, c): a partial prime like p >> k or p & mask, or a private exponent with a chunk zeroed/redacted (d's top half given, bottom half ?, or vice versa). Framing is often "corrupted backup", "truncated memory dump", "leaked side-channel trace", "partially redacted PEM". - e is a normal, full-size exponent (not tiny) — that alone rules out Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n and Hastad as the first move, and points you at the bit-leak instead. - Some non-trivial fraction of the unknown value's bits is known — but the exact threshold for a guaranteed Coppersmith root is not a fixed "half". It varies a lot by configuration (standard vs. CRT vs. multi-prime RSA, size of e); published bounds range from roughly a third to over 80% of the unknown bit-length depending on setup. The signal that matters is that the challenge hands you *enough* known bits to be solvable exactly — not so few it's a coin flip, not so many it's trivial substitution. - Two structurally different leaks look similar but are NOT the same attack: bits of a factor (p or q) vs. bits of the private exponent (d). Read carefully which one the challenge actually gives you before picking a construction — they use different polynomials.

How to exploit

Route by what actually leaked.

A) Known high or low bits of a prime factor. Write p = p_known + x0 (high bits known, low part x0 unknown and small) or the mirror case for low bits known. Build f(x) = p_known + x over Zmod(N) and hunt a small root — since the root only needs to hold modulo the unknown factor p ~ sqrt(N), not modulo the full N, set beta = 0.5 (this is the detail that trips people up, see below):

``python # SageMath P.<x> = PolynomialRing(Zmod(N)) f = x + p_known # p = p_known + x0, x0 small and unknown f = f.monic() beta = 0.5 epsilon = beta/7 X = 2^bits_unknown # bound on the unknown chunk roots = f.small_roots(X=X, beta=beta, epsilon=epsilon) ` Once x0 pops out, p = p_known + x0, then q = N // p and you're done — no discrete-log-scale factoring needed. There is no single threshold to keep in your head here: the fraction of p's bits you need known for a guaranteed root depends on the RSA configuration, not just on beta = 0.5. For standard, balanced RSA with a normal-size e, roughly half of p's own bit-length known is a reasonable starting estimate (about a quarter of n's bit-length) — but that number moves substantially in other setups: CRT-RSA and multi-prime constructions have been shown to work with as little as ~1/3 of the bits known (2022 results), while some public-exponent-dependent variants need considerably more — published bounds report a known fraction of 0.71 sufficient for e = N^0.55 but 0.81 required for e = N^0.6. Treat "about half" as a rule of thumb to try first, not a hard cutoff; if small_roots comes back empty near that estimate, check whether your actual configuration (CRT, multi-prime, unusual e`) shifts the real bound before concluding there's no shortcut.

B) Known high or low bits of the private exponent `d`. This is the Boneh–Durfee–Frankel construction, distinct from plain Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 (which needs d to be small with *no* bits revealed). Here d can be full-size; what you have is literal bits of it. From ed - 1 = k*phi(n), the known chunk of d plus the known e constrains k to a small search space; for each candidate k build a Coppersmith polynomial for the unknown chunk of d (or of phi(n)) and run small_roots. Once the unknown part resolves, reconstruct full d, then recover phi(n) and factor n via the standard p, q from phi(n) roots of x^2 - (n - phi(n) + 1)x + n. Keep the two constructions mentally separate: if the challenge gives you a *small* d with no bits revealed, go to Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions or Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 first (cheaper, no bit-leak machinery needed); reach for the Boneh–Durfee–Frankel partial-exposure construction only when bits are literally handed to you.

Tuning that matters in practice

- beta encodes what modulus the root is guaranteed against: beta = 1.0 for a root mod the full N (message/stereotyped-message cases), beta = 0.5 for a root mod an unknown factor p ~ sqrt(N) (the factor-leak case above). Using the wrong beta doesn't crash — it just makes small_roots silently return no root even though a real solution exists, because the lattice bound estimate is wrong. This is the single most common self-inflicted dead end here. - Larger lattice parameters (m, t in the shifted-polynomial construction) push the bound closer to the theoretical limit at rapidly rising cost. For CTF-sized RSA (1024–2048 bit), modest m in the 3–6 range is usually enough before runtimes become punishing; only crank it up if you're deliberately close to the threshold. - Always verify a recovered candidate root with a direct gcd(candidate - guess, N) or by checking p * q == N before trusting it — an over-optimistic bound estimate can hand back a root of the *polynomial* that isn't a real factor.

What does NOT work

- Brute-forcing the missing bits directly. The unknown chunk is exponential in its own bit-length; if it were small enough to brute force you wouldn't need Coppersmith. Once too many bits are missing relative to whatever bound your specific configuration requires (see the threshold discussion above — it moves with standard/CRT/multi-prime RSA and with e's size, it isn't a fixed "half"), brute force is hopeless *and* Coppersmith has no guaranteed small root either — there just isn't enough information yet. Go look for more leaked bits before spending compute. - **Treating it as Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n or Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions. Those exploit a small `e` or a small, bit-clean `d` respectively. Partial-bit exposure of an otherwise full-size key is a different information source entirely; forcing it through the wrong attack wastes the one piece of leverage the challenge actually gave you. - Reusing beta = 1.0 (the message-root default) for a factor-recovery polynomial. As above: this is the most common way to get "no roots found" on a case that is genuinely solvable — the fix is almost always the `beta` value, not the bound `X` or `epsilon`. - Assuming symmetry between p and q. If the leak is specifically about `p`, the polynomial has to be built around `p`; there is no shortcut that lets you reuse the same known bits against `q` unless the challenge separately tells you they're related. - Skipping the sanity check on the recovered root.** Especially near the threshold, small_roots can return a spurious algebraic root that isn't an actual factor of N; always confirm with gcd/division before declaring victory.

Related

Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction — the lattice tool everything here is built on. Boneh-Durfee Attack — the lattice extension of Wiener that reaches d < N^0.292 — sibling attack for a small *unrevealed* d; use partial-key-exposure instead when bits are directly given, regardless of how small d actually is. Wiener Attack — recovering RSA's private exponent when d is small, via continued fractions — rule this out first if d merely looks small but no bits are actually handed to you. LLL Reduction — the polynomial-time workhorse behind almost every lattice attack — the reduction step underneath the lattice construction. RSA Fundamentals — the routing hub: which artifact points to which attack — triage hub for routing RSA artifacts to the right sub-attack.