THE GARDEN

Partial-Match RSA Verification Exploit (Suffix Forgery via Small Modulus)

Updated 19 Sep 2026

• •

  What it is

  • •

    If a verifier only checks a small portion of a decrypted/verified value — e.g. splitting on a delimiter and checking only the last few bytes match a target string — an attacker can forge a value satisfying just that portion using arithmetic modulo a small power of 2 (or another small modulus matching the checked portion's byte-length), entirely decoupled from the real, large RSA modulus $N$. If the forged value raised to the public exponent stays smaller than $N$ (no modular wraparound occurs), then $x^e \bmod N = x^e$ exactly as an integer — so controlling $x$'s value modulo a small $2^k$ directly controls the low $k$ bits of $x^e$, which is exactly the portion the verifier inspects; the untouched high-order bits simply don't matter to a check that only looks at the tail.

• •

  When to apply

  • •

    Verification logic extracts and checks only a substring/suffix/prefix of the full decoded value (e.g. .split(delimiter)[-1] == target) rather than requiring the entire decoded value to match exactly — and the checked portion is small enough, in bytes, that raising a same-sized candidate to the public exponent still stays well below the real modulus.

• •

  Math

  • •

    For a $k$-bit odd target $m$ and odd $e$, exponentiation by $e$ is a permutation of the odd residues modulo $2^k$ when $\gcd(e,2^{k-2})=1$. Compute $d\equiv e^{-1}\pmod{2^{k-2}}$, set $x\equiv m^d\pmod{2^k}$, and verify $x^e\equiv m\pmod{2^k}$. The shortcut does not apply unchanged to an even target. Also require $x^e<N$ if the verifier reduces modulo $N$ before checking the suffix.

• •

  Worked example

  • •

    Target suffix \x00VOTE FOR PEDRO (15 bytes, 120 bits), $e=3$: computing $d \equiv 3^{-1} \pmod{2^{119}}$ and $x \equiv m^d \pmod{2^{120}}$ gave a candidate whose cube ($x^3$, only 359 bits) was far smaller than a real 1024+ bit $N$ — confirming no wraparound — and $x^3 \bmod N$'s raw bytes ended in exactly the target suffix.

• •

  Python

  • •

    k_bits = len(target_suffix) * 8
    mod = 1 << k_bits
    phi = 1 << (k_bits - 1)
    d = pow(e, -1, phi)
    x = pow(bytes_to_long(target_suffix), d, mod)
    # x**e < N (verify this bound explicitly), so pow(x, e, N) ends in target_suffix
    

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Low-Exponent Cube-Root Attack (Unpadded RSA)

• •

  Cards

  • •

    Why can the real RSA modulus N be ignored entirely in this attack?

    • •

      As long as the forged value raised to e stays smaller than N, no modular reduction happens, so the result equals the small-modulus computation exactly — N never comes into play.

  • •

    What makes φ(2^k) easy to compute and invert e against?

    • •

      φ(2^k) = 2^(k-1) always, and any odd e is automatically coprime to a power of 2, guaranteeing an inverse exists.

◌ Explore connections in Graph view