THE GARDEN

Low-Exponent Cube-Root Attack (Unpadded RSA)

Updated 19 Sep 2026

• •

  What it is

  • •

    When RSA uses a small public exponent (classically $e=3$) with no padding scheme, $c \equiv m^e \pmod N$ might not "wrap around" the modulus much (or at all) if $m^e$ isn't dramatically larger than $N$. In the simplest case, $m^e < N$ outright, so $c = m^e$ exactly over the integers and $m = \sqrt[e]{c}$​ needs no modular reduction at all. More generally, even when $m^e$ does exceed $N$, it typically only wraps a handful of times for realistic message sizes — so trying $m^e = c + kN$ for small integer $k = 0, 1, 2, \dots$ and testing each for an exact integer $e$-th root finds the true message quickly once $k$ matches how many times it actually wrapped.

• •

  When to apply

  • •

    e is small (3, 5, ...) and the encryption function applies no padding (OAEP, PKCS#1, etc.) before exponentiating a message that isn't astronomically larger than $N^{1/e}$.

• •

  Math

  • •

    $m^e \equiv c \pmod N \Rightarrow m^e = c+kN$ for some non-negative integer $k$; the correct $k$ is found by testing each candidate for an exact integer $e$-th root.

• •

  Worked example

  • •

    Let $N=55$, $e=3$, and $m=7$. Then $m^3=343$, so $c=343\bmod55=13$ and the correct lift is $c+6N=343=7^3$. Searching $k=0,1,\ldots$ finds $k=6$ here. The required range is instance-dependent; small $e$ alone does not guarantee a tiny $k$.

• •

  Python

  • •

    def exact_nth_root(x, n):
        # use gmpy2.iroot(x, n) in practice -- exact and fast for big integers;
        # DO NOT use x ** (1/n): floating point loses all precision at RSA sizes
        from gmpy2 import iroot
        r, exact = iroot(x, n)
        return int(r) if exact else None
    
    for k in range(0, 10**8):
        m = exact_nth_root(c + k * N, e)
        if m is not None:
            break
    

• •

  SageMath

  • •

    Not particularly relevant — Sage's integer nth_root(x, e, truncate_mode=True) is a fine alternative to gmpy2.iroot, but neither language makes the underlying search meaningfully simpler than the other.

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Hastad's Broadcast Attack

• •

  Cards

  • •

    Why does a small unpadded exponent risk exposing the plaintext directly?

    • •

      If m^e doesn't exceed N by much, c = m^e wraps the modulus only a few times (or not at all), so a small search over k in c + kN quickly finds an exact e-th root — the true message.

  • •

    What's the critical implementation mistake this attack exploits?

    • •

      Encrypting with a small public exponent (e.g. e=3) without any padding scheme to inflate/randomize the message beforehand.

◌ Explore connections in Graph view