Coppersmith's Attack: When Knowing a Little Is Enough to Break RSA

The Problem

RSA relies on a simple asymmetry: multiplying two large primes is easy, but factoring their product is hard.

Given

$$N = pq$$

recovering secret primes $p$ and $q$ from public modulus $N$ should be computationally infeasible when RSA is implemented correctly.

But what if we already know part of a secret?

Suppose we know most significant bits of $p$, or the beginning of an encrypted message. We don't know the complete value, but we know enough to constrain it.

Can we recover the missing pieces without brute-forcing every possibility?

This is where Coppersmith's method comes in.

Turning Secrets into Equations

The key idea is to express the unknown information as a variable in a polynomial.

Suppose an RSA message has a known prefix and an unknown suffix. We can represent it as

$$m = A + x$$

where $A$ represents the known part and $x$ is the unknown.

RSA encryption gives us

$$c \equiv m^e \pmod N$$

Substituting our representation,

$$(A+x)^e \equiv c \pmod N$$

Rearranging gives a polynomial:

$$f(x) = (A+x)^e-c$$

Our problem is now finding a small integer $x$ satisfying

$$f(x)\equiv0\pmod N$$

Instead of searching for the entire message, we only need to recover its unknown portion.

But how do we solve this equation efficiently?

The Trick: Small Roots and Lattices

A polynomial congruence can have multiple solutions modulo $N$. Coppersmith's insight was that small roots are easier to recover than arbitrary roots.

For a monic polynomial of degree $d$, the classical univariate method can find sufficiently small roots, with a root-size bound on the order of

$$|x| < N^{1/d}$$

The smaller the unknown, relative to the modulus, the more useful this result becomes.

The technique relies on lattice reduction.

Here's the intuition:

1. Start with the polynomial equation that the unknown satisfies.
2. Construct additional polynomials that preserve its modular relationship.
3. Represent their coefficients as vectors forming a lattice.
4. Apply the LLL algorithm to find useful combinations with small coefficients.
5. Use these combinations to construct an ordinary polynomial equation whose roots include the unknown.

Why?

Suppose we construct a polynomial $g(x)$ such that

$$g(x_0)\equiv0\pmod {N^t}$$

for our unknown root \(x_0\).

If we can also establish

$$|g(x_0)|<N^t$$

then \(g(x_0)\) must equal zero over the integers.

We've turned a modular equation into an ordinary polynomial equation, which we can solve using standard root-finding techniques.

Where Does This Break RSA?

Coppersmith's method is a framework, not one specific attack. Different RSA weaknesses provide different polynomial equations. Like:

1. Partial prime-factor recovery

Suppose we know the most significant bits of prime $p$. We can write

$$p=P+x$$

where $P$ represents the known bits and $x$ represents the missing portion.

Since $p$ divides $N$, the unknown satisfies

$$P+x\equiv0\pmod p$$

Under suitable conditions, small-root techniques can recover the missing bits and reveal the factor.

2. Stereotyped messages

Suppose an encrypted message contains a known prefix or suffix. Representing the unknown portion as a small variable gives us a polynomial derived from

$$c\equiv m^e\pmod N$$

If the unknown portion is sufficiently small, Coppersmith's method can recover it.

3. Short padding

Padding is supposed to prevent RSA messages from having predictable mathematical relationships. When padding is insufficient, related messages can produce polynomial equations that expose the underlying plaintext.

These attacks have different assumptions and mathematical constructions, but they share a common strategy: exploit known structure to reduce a large secret to a small unknown.

The Why now?

I was working on Coppersmith-based attacks for RsaCtfTool :)

In the next post, we'll look at the concrete attacks built on this idea and derive the equations that make each one work.