Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n

When textbook RSA uses a tiny public exponent e (3, 5, 17...) and the plaintext m is small enough that m^e < n, the modular reduction in c = m^e mod n never actually triggers — c *is* m^e as an ordinary integer — so m is recovered by taking the exact integer e-th root of c, no factoring and no private key needed.

The signal that gives it away

- `e` is small — 3, 5, 17 are the classic values seen in CTF setups (real-world RSA moved to 65537 specifically to make this and related attacks harder). Any challenge that hands you a conspicuously small e alongside n and c is worth checking first for this. - The plaintext is short relative to `n` — a flag, a short key, a small number — so that raising it to the e-th power plausibly stays under the modulus. A 2048-bit n with e=3 and a plaintext under roughly 2048/3 ≈ 683 bits is exactly the shape that qualifies. - `c` "looks too small" relative to n (far fewer digits than you'd expect from a uniformly random residue) — that asymmetry is the empirical tell that no wraparound happened, or only a small one did. - Single recipient, one `(n, e, c)` triple. This is what distinguishes it operationally from Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring: that attack needs e (or more) different moduli encrypting the *same* message to *different* recipients; this one needs only one ciphertext. If you're handed a list of (n_i, c_i) pairs sharing one exponent, you're looking at Hastad, not this. - No OAEP / no randomized padding — the challenge does raw pow(m, e, n) or equivalent. Any real padding scheme randomizes m up to the size of n, which kills the "m is small" premise outright.

How it's exploited

1. Take the integer `e`-th root of `c` directly. No modular exponentiation of a guess, no factoring — just an exact-root check.

```python from gmpy2 import iroot

m, exact = iroot(c, e) if exact: # m is the plaintext integer directly ... ```

2. If it's not exact, don't give up — brute-force the wraparound count. In practice m^e often *slightly* overshoots n (the plaintext is close to, not comfortably under, the n^(1/e) bound), so the true relation is m^e = c + k*n for some small positive integer k (the true m^e "wrapped" k times around the modulus before reduction). Search k upward from 1:

``python for k in range(1, 1 << 20): m, exact = iroot(c + k * n, e) if exact: break ``

1 << 20 (roughly a million) is a field-tested ceiling: it costs a few seconds and comfortably covers the case where the plaintext overshoots the "safe" bound by a small margin. This is the operational core of the technique — treating "no exact root at k=0" as "attack fails" is the single most common way to walk away from an actually-solvable challenge. 3. Convert the recovered integer to bytes (long_to_bytes(m) in pycryptodome, or m.to_bytes(...) in stdlib) and check it decodes to something readable. 4. Always verify: pow(m, e, n) == c. It's free and it immediately catches an accidental false-exact root from iroot on the wrong k.

Related

Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction RSA Fundamentals — the routing hub: which artifact points to which attack

What does NOT work

- Brute-forcing `k` indefinitely. The search is only cheap because k is small *by construction* — the plaintext was close to, not far past, the bound where wraparound starts. If nothing turns up in the first ~10^6–10^7 iterations, the plaintext isn't merely "a bit too big": it's genuinely on the order of n itself, and this technique's premise (an un-reduced m^e) is false. Growing the search range further almost never pays off — the cost is linear in k while the odds of hitting the exact root stay flat, so this is the point to stop and re-diagnose rather than let the loop run overnight. - Applying it to a single ciphertext when `m` is actually the full size of `n`. That's not a small-exponent weakness at all — the exponentiation genuinely wrapped many times and no small-k search will recover it. Look instead for a different signal (factoring weakness, oracle, leaked bits) rather than forcing this attack past its regime. - Confusing "small `e`" with "attack always applies." A small e alone is necessary but not sufficient — plenty of CTF RSA setups use e=3 or e=17 *with* properly randomized/padded plaintexts specifically so this attack fails; the actual gate is whether m^e (or m^e + k*n for small k) fits under an integer root, not the size of e by itself. - Trying this with only one ciphertext when the plaintext is provably too large for any small `k`. If the challenge's real setup is the *same* message broadcast under the *same* small e to several different moduli, don't keep hammering a single-ciphertext root search — that's the CRT-combination regime of Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring, which is a different reconstruction (combine first, then root), not a bigger brute force on this one. - Skipping the `pow(m, e, n) == c` sanity check. iroot-style functions can occasionally report an "exact" root that isn't the real plaintext once you're brute-forcing across many k values (numerical/library edge cases at scale) — the verification step is cheap and catches this before you waste time on a garbage decode. - Reaching for this when only part of the plaintext is known or fixed (e.g. a known prefix/suffix, or the flag is embedded in a longer padded structure). That's a different, harder regime — Coppersmith's Method — recovering a small unknown from a modular polynomial via lattice reduction (small modular roots of a polynomial with one small unknown) is the right tool once "the whole plaintext is small" stops being true but "part of it is small/known" still is.