Lattice Attacks

A surprising fraction of CTF crypto reduces to one sentence: find a short vector, or a close vector, in a lattice you can build from the challenge data. Small RSA roots, biased ECDSA nonces, broken knapsack ciphers, and approximate-GCD problems all collapse onto the same machinery - construct a basis whose short vectors encode the secret, then call LLL.

This page is the toolbox behind RSA Attacks (Coppersmith, Boneh-Durfee) and ECC Attacks (the nonce Hidden Number Problem). If you have never seen a lattice, start at the intuition and work down.

Lattice Intuition

A lattice is a regular grid of points in $\mathbb{R}^n$, but the grid need not be axis-aligned. The same lattice has infinitely many bases: any basis multiplied by an integer matrix of determinant $\pm 1$ (a unimodular matrix) generates the same point set. Some bases are "good" (short, nearly orthogonal vectors); most are "bad" (long, skewed vectors). Almost every lattice attack is the same move:

Two hard problems sit underneath:

• SVP (Shortest Vector Problem): find the shortest non-zero $\mathbf{v} \in \mathcal{L}$.
• CVP (Closest Vector Problem): given a target $\mathbf{t} \notin \mathcal{L}$, find the lattice point nearest to it.

Both are NP-hard in general, but in the low dimensions and with the gap typical of CTFs, LLL solves them in practice.

The length scale to keep in your head is the Gaussian heuristic: a random lattice's shortest vector has norm roughly

If the vector encoding your secret is much shorter than this, it is unusually short and LLL will find it.

LLL Reduction

The Lenstra-Lenstra-Lovász algorithm (1982) runs in polynomial time and returns a basis whose first vector satisfies

The exponential factor is a worst-case bound; on the structured lattices you build in a CTF, LLL routinely returns the shortest vector. That is the whole reason these attacks work.

# SageMath - the one line you will type most often
M = Matrix(ZZ, [
    [b00, b01, b02],
    [b10, b11, b12],
    [b20, b21, b22],
])
reduced = M.LLL()          # rows of `reduced` are a reduced basis
print(reduced[0])          # usually the shortest vector

For tougher instances (higher dimension, smaller gap), use BKZ with a block size, which interpolates between LLL (block size 2) and full enumeration:

reduced = M.BKZ(block_size=20)   # slower, stronger; raise block_size if LLL fails

The Python library fpylll exposes the same engine outside Sage and is what fplll / many PoCs call under the hood.

Coppersmith Small Roots

Coppersmith's method finds small integer roots of a polynomial modulo $N$ (or modulo an unknown divisor of $N$). It is the lattice engine behind the RSA stereotyped-message, partial-key, and Boneh-Durfee attacks.

Univariate: roots mod N

Given a monic $f(x)$ of degree $d$ and a modulus $N$, Coppersmith finds all roots $x_0$ with

The idea: build a lattice of polynomials $x^j N^{i}\, f(x)^{k}$ that all vanish at $x_0$ modulo $N^m$. A short vector in that lattice is a polynomial $g(x)$ with small enough coefficients that $g(x_0) = 0$ holds over the integers, not just mod $N$ - so its integer roots (found with ordinary root-finding) include $x_0$.

# SageMath - built in to PolynomialRing over Zmod(N)
N = ...
P.<x> = PolynomialRing(Zmod(N))
f = x^3 + a2*x^2 + a1*x + a0     # your monic polynomial, root x0 is small
f = f.monic()
roots = f.small_roots(X=2**200, beta=1.0, epsilon=1/20)
print(roots)

The knobs:

• X - an upper bound on $\lvert x_0 \rvert$. Larger X needs a bigger lattice.
• beta - the root is taken mod a divisor $b \mid N$ with $b \ge N^{\beta}$. Use beta=1.0 for roots mod $N$ itself; beta≈0.5 when factoring $N$ given high bits of a prime.
• epsilon - controls lattice size vs. the achievable bound; smaller is stronger but slower.

The general bound for roots modulo a divisor $b \ge N^{\beta}$ is

which is exactly the "you need about half the bits of $p$" rule for factoring: with $d=1$ and $\beta=0.5$ you can fill in $x_0$ up to $N^{1/4}$.

Bivariate and beyond

small_roots is univariate-only. For two variables (Boneh-Durfee, short-pad, "two leaks"), use the well-known community helper defund/coppersmith, which builds the multivariate lattice and reduces it for you:

# SageMath - defund/coppersmith style multivariate small_roots
load("coppersmith.sage")

P.<x, y> = PolynomialRing(Zmod(N))
f = x*(N + 1 + y) + 1             # e.g. the Boneh-Durfee relation mod e
roots = small_roots(f, bounds=(X, Y), m=4, d=4)
print(roots)

Hidden Number Problem (Biased ECDSA Nonces)

The Hidden Number Problem (HNP) is the single most lucrative lattice attack in CTF crypto, because it breaks ECDSA (and DSA) whenever the per-signature nonces are short or biased. It cross-links directly with ECC Attacks.

Recall the ECDSA signing relation, with secret key $d$, nonce $k$, hash $h$:

Write $t_i = s_i^{-1} r_i \bmod n$ and $u_i = s_i^{-1} h_i \bmod n$, so $k_i \equiv u_i + t_i\, d \pmod n$. If every nonce is small (say only the low $\ell$ bits are nonzero, $k_i < 2^{\ell}$), then $d$ is the hidden number and each signature is an approximate equation $u_i + t_i d \approx 0 \pmod n$ with a small residue $k_i$.

Stack these into a lattice. With $m$ signatures, build the basis

where $K \approx 2^{\ell}$ scales the nonce coordinates. The lattice contains the vector $(k_1, \dots, k_m, \cdot, \cdot)$, which is short precisely because every $k_i$ is small - so LLL surfaces it, and the last meaningful coordinate hands you $d$.

# SageMath - HNP for short ECDSA nonces (top bits of k are zero)
# sigs: list of (h, r, s); n: group order; KB: bound on the nonce (e.g. 2^ell)
def recover_d(sigs, n, KB):
    m = len(sigs)
    t = [(Integer(s).inverse_mod(n) * r) % n for (h, r, s) in sigs]
    u = [(Integer(s).inverse_mod(n) * h) % n for (h, r, s) in sigs]

    B = Matrix(QQ, m + 2, m + 2)
    for i in range(m):
        B[i, i] = n
    for i in range(m):
        B[m, i] = t[i]
        B[m + 1, i] = u[i]
    B[m, m] = QQ(KB) / n
    B[m + 1, m + 1] = KB

    for row in B.LLL():
        # look for the row whose last entry is +/- KB: it encodes -d
        if abs(row[-1]) == KB:
            d = (-row[-2] * n / KB) % n if False else None
        # robust path: try every short row as a candidate for d directly
    # In practice: read d from the vector, then verify Q == d*G.
    return B.LLL()

# A clean, ready-made implementation lives in the lbumns / "lattice-based-cryptanalysis"
# and Cryptohack toolkits; the construction above is the standard EHNP/HNP form.

For the related case where the nonces themselves are partly known (leaked top bits rather than zero), the same lattice works with $u_i$ shifted by the known part; this is the Extended HNP (EHNP). The dedicated lattice-based-cryptanalysis repo packages both.

Knapsack / Subset-Sum

A subset-sum (knapsack) cipher hides a message bit-vector $\mathbf{e} \in \{0,1\}^n$ in a public weight set $a_1, \dots, a_n$ via $S = \sum_i e_i a_i$. Recovering $\mathbf{e}$ from $S$ is the subset-sum problem. When the density $\rho = n / \log_2(\max a_i)$ is low ($\rho < 0.94$, the Lagarias-Odlyzko / Coster-et-al bound), LLL solves it almost always.

Build the lattice

with a large multiplier $N$. The short vector $(e_1 - \tfrac12, \dots, e_n - \tfrac12, 0)$ has tiny last coordinate (the subset-sum constraint is satisfied) and $\pm\tfrac12$ entries, so it is unusually short.

# SageMath - Coster-LaMacchia-Odlyzko-Schnorr-Stern low-density subset-sum
def solve_knapsack(a, S):
    n = len(a)
    N = ceil(sqrt(n)) + 1                  # any sufficiently large weight works
    B = Matrix(QQ, n + 1, n + 1)
    for i in range(n):
        B[i, i] = 1
        B[i, n] = N * a[i]
    for j in range(n):
        B[n, j] = QQ(1) / 2
    B[n, n] = N * S

    for row in B.LLL():
        bits = row[:n]
        if all(x in (QQ(-1)/2, QQ(1)/2) for x in bits):
            e = [0 if x == QQ(1)/2 else 1 for x in bits]
            if sum(ei * ai for ei, ai in zip(e, a)) == S:
                return e
            # also try the complemented vector
            e = [1 - b for b in e]
            if sum(ei * ai for ei, ai in zip(e, a)) == S:
                return e
    return None

The classic Merkle-Hellman cryptosystem builds a superincreasing private knapsack and disguises it with modular multiplication; the Shamir attack (and the low-density LLL attack above) break it.

Approximate GCD

The Approximate-GCD problem underlies some homomorphic-encryption toy schemes and shows up directly in CTFs: you are given several near-multiples $x_i = q_i p + r_i$ of a hidden $p$, with small noise $r_i$, and must recover $p$. With exact multiples ($r_i = 0$) it is just $\gcd$; with noise, build a lattice.

For two samples $x_0, x_1$ with $\lvert r_i \rvert < 2^{\rho}$, the lattice

has a short vector $(q_0\, 2^{\rho+1},\; q_0 r_1 - q_1 r_0)$; reducing it reveals $q_0$, and then $p \approx x_0 / q_0$ rounded. With more samples, extend to an $(m+1)$-dimensional "orthogonal lattice" version for robustness.

# SageMath - approximate GCD from many noisy multiples x_i = q_i*p + r_i
def approximate_gcd(xs, rho):
    m = len(xs)
    B = Matrix(ZZ, m, m)
    B[0, 0] = 2**(rho + 1)
    for i in range(1, m):
        B[0, i] = xs[i]
        B[i, i] = -xs[0]
    short = B.LLL()[0]
    q0 = short[0] // 2**(rho + 1)
    p = round(xs[0] / q0)
    return p

Picking the Right Lattice

When in doubt: write the unknowns as a vector, find an integer relation they satisfy, scale the coordinates so the secret vector is short, and LLL.

Checklist

• Can the secret be written as a short vector of an integer relation? Then it is a lattice problem.
• Small root of a polynomial mod $N$? Coppersmith small_roots (set X, beta, epsilon).
• Factoring with ~half the bits of $p$? Coppersmith with beta≈0.5.
• Two or more small unknowns? defund/coppersmith multivariate.
• Short or biased ECDSA/DSA nonces across many signatures? HNP lattice, then verify $Q = dG$.
• Subset-sum with density $< 0.94$? CLOS low-density knapsack lattice.
• Noisy near-multiples of a hidden modulus? approximate-GCD lattice.
• LLL returns nothing useful? scale columns harder, tighten bounds, collect more samples, or switch to BKZ.

See Also

• RSA Attacks - Coppersmith, Boneh-Durfee, partial-key exposure built on these lattices.
• ECC Attacks - the biased-nonce HNP attack in its native ECDSA setting.
• ECC Basics - ECDSA signing relation used by the HNP construction.
• RSA Basics - the modular arithmetic underpinning Coppersmith.

Last updated on Jun 15, 2026