Notes on lattice reduction and small roots

This is a seed post, written to exercise math rendering. Delete it once you have something real to publish.

The setup

A lattice $\mathcal{L}$ generated by linearly independent basis vectors $b_1, \dots, b_n \in \mathbb{R}^m$ is the set of integer combinations

\mathcal{L} = \left\{ \sum_{i=1}^{n} z_i b_i \;\middle|\; z_i \in \mathbb{Z} \right\}.

The same lattice has infinitely many bases. Some are nearly orthogonal with short vectors; most are long and skewed. Reduction is the business of moving from the second kind to the first.

What LLL guarantees

LLL runs in polynomial time and returns a basis whose first vector satisfies

\|b_1\| \le 2^{(n-1)/4} \cdot (\det \mathcal{L})^{1/n}.

That exponential factor looks fatal, but two things rescue it in practice: the dimensions in CTF challenges are small, and LLL’s real-world output is far better than its worst-case bound. Treat the inequality as a guarantee, not a prediction.

Coppersmith’s method

Given a monic polynomial $f$ of degree $d$ over $\mathbb{Z}/N\mathbb{Z}$ , Coppersmith finds all roots $x_0$ with

|x_0| \le N^{1/d}

in polynomial time. The trick is to build a lattice from shifts and powers of $f$ , reduce it, and read off a polynomial that holds over the integers rather than just mod $N$ — at which point ordinary root-finding applies.

The usual appearance is stereotyped RSA: a message with known structure and a small unknown, encrypted under $e = 3$ .

from sage.all import *

N = 0xc2f1... # modulus
e = 3
c = 0x8a3d... # ciphertext

P.<x> = PolynomialRing(Zmod(N))
# known prefix, 40 unknown low bits
f = (prefix * 2**40 + x)**e - c
f = f.monic()

roots = f.small_roots(X=2**40, beta=1.0)
print(roots)

small_roots is Coppersmith with the lattice construction handled for you. The parameter that matters is X, the bound on the root — set it too tight and you miss the answer, too loose and the lattice grows until reduction stops terminating in reasonable time.

Where it breaks

The bound $|x_0| \le N^{1/d}$ is hard. For $e = 3$ and a 1024-bit modulus that is roughly 341 bits of unknown, which sounds generous until the challenge hands you 400. The usual fixes:

Find more known structure to shrink the unknown.
Use several related messages and switch to a multivariate variant.
Check whether the intended bug is elsewhere entirely — a shared prime, a repeated nonce, a broken PRNG.

Most challenges labelled “Coppersmith” turn out to be the third case.