THE GARDEN

Coppersmith's Method for Stereotyped-Partially-Known Messages

Updated 19 Sep 2026

• •

  What it is

  • •

    If most of an RSA-encrypted message's content is already known or guessable (a fixed prefix/suffix format like crypto{...}, or predictable padding), and only a small unknown portion remains, Coppersmith's theorem guarantees that unknown portion can be recovered efficiently — even from a single ciphertext, with no need for multiple related messages — by finding small roots of a univariate polynomial modulo $N$ via lattice basis reduction (LLL), provided the unknown portion is small enough relative to $N$ and the exponent $e$.

• •

  When to apply

  • •

    The plaintext format is largely predictable (a known flag prefix/suffix with a modest unknown middle section, or a message with mostly-fixed padding bytes), the public exponent $e$ is small (2 or 3 is typical for feasibility), and you have at least one ciphertext.

• •

  Math

  • •

    Write the known structure as $M(X) = (\text{known prefix, shifted}) + X \cdot 2^{\text{shift}} + (\text{known suffix})$ where $X$ represents the unknown portion; then $f(X) = M(X)^e - c \equiv 0 \pmod N$ has the true unknown value as a root, and Coppersmith's small-roots algorithm finds it directly whenever that root is smaller than the method's recoverable bound.

• •

  Worked example

  • •

    For monic $f(X)=M(X)^3-c$ modulo $N$, univariate Coppersmith can recover a sufficiently small integer root $X$, roughly below $N^{1/3-\varepsilon}$ in the full-modulus setting. Encode the exact byte shifts, pass the intended root bound, and verify every returned root by reconstructing and re-encrypting the message. beta has a different meaning when the root is only modulo an unknown divisor.

• •

  Python

  • •

    Not practical by hand — this genuinely needs LLL lattice reduction, which plain Python doesn't provide.

• •

  SageMath

  • •

    P.<X> = Zmod(N)[]
    f = (known_prefix_int + X * 2**(8*padding_len) + known_suffix_int)**e - c_prime
    f = f.monic()
    roots = f.small_roots(X=2**(8*unknown_len), beta=0.4)   # beta controls the size/confidence tradeoff
    

• •

  Related

  • •

    RSA (Textbook Construction)

  • •

    Franklin-Reiter Related Message Attack

• •

  Cards

  • •

    What does Coppersmith's small-roots method need to succeed, beyond the ciphertext itself?

    • •

      Most of the plaintext already known/guessable, with only a small enough unknown portion remaining (roughly smaller than N^(1/e)-ish, tuned by the lattice parameters).

  • •

    Why doesn't this attack need a second, related ciphertext the way Franklin-Reiter does?

    • •

      The "smallness" of the unknown root itself (not a shared relationship between two messages) is what the lattice construction exploits — a single ciphertext with enough known structure is sufficient.

◌ Explore connections in Graph view