20.1.1. The story🔗

A courier sends the same templated message every day: a fixed body with one short field that changes, say a two-digit code. An eavesdropper knows the template and knows the day's ciphertext, and wants the code.

The message is RSA-encrypted with public exponent e = 3. That small exponent, with no random padding, is the weakness. Write the plaintext as m = a + x₀, where a is the known template (as an integer) and x₀ is the unknown code, with 0 ≤ x₀ < X for a small bound X. The ciphertext is c = m³ mod N. Everything except x₀ is public: the modulus N, the exponent 3, the ciphertext c, the template a, and the bound X.

Knowing that m³ genuinely wraps around the modulus (m³ > N, so c is not just the integer cube of m) rules out the trivial cube-root attack. The unknown x₀ is a small root of a polynomial modulo N: f(x) = (a + x)³ − c, and f(x₀) ≡ 0 (mod N). Coppersmith's method finds small modular roots by lattice reduction, and that is what this page does with the project's LLL layer. See the HexLLL chapter for the reducer itself.

20.1.2. From a modular root to a lattice🔗

Expanding, f(x) = x³ + 3a·x² + 3a²·x + (a³ − c), a monic cubic whose coefficients we reduce modulo N to small representatives. The idea due to Howgrave-Graham turns "small root mod N" into "root over the integers". If we can find another polynomial g that also has x₀ as a root modulo N, but whose coefficients are small enough that g(x₀), evaluated at the small integer x₀, is smaller in absolute value than N, then g(x₀) ≡ 0 (mod N) forces g(x₀) = 0 over the integers. An integer root of a known polynomial is then read off by a search.

Such small-coefficient combinations are exactly the short vectors of a lattice. Encode a polynomial by its coefficient vector, scaling the degree-j coefficient by Xʲ so that "coefficients small after substituting x = X·y" becomes "vector short". The lattice is spanned by four rows, each a polynomial vanishing at x₀ modulo N: the three multiples N, N·x, N·x², and f itself.

row N       : [ N,     0,      0,       0   ]
row N·x     : [ 0,     N·X,    0,       0   ]
row N·x²    : [ 0,     0,      N·X²,    0   ]
row f       : [ a₀,    a₁·X,   a₂·X²,   X³  ]

Reducing this basis with LLL produces a short vector whose polynomial g is a small-coefficient integer combination of the four rows. The short-vector guarantee is the Lean-proved Hex.short_vector_bound_of_size_bound. The Howgrave-Graham bound that turns "short enough" into "root over the integers" is classical number theory, asserted here in prose rather than formalized; this page demonstrates the computational step, it does not prove the Coppersmith theorem.

20.1.3. The attack, end to end🔗

The instance below uses two nine-digit primes, a known template a = 55_555_500, and a two-digit code x₀ = 42, hidden inside c = m³ mod N. The attacker uses only the public data N, a, c, and X = 100 to rebuild the lattice, reduce it with the exact integer reducer Hex.lllNative, and recover the code.

Every basis row has its degree-j column divisible by Xʲ, so every lattice vector does too; de-scaling a reduced row back to integer coefficients therefore always succeeds. The recovery scans all reduced rows, de-scales each to a candidate polynomial g, searches 0 ≤ x < X for an integer root, and accepts the first x that also reproduces the ciphertext. The verification is that the recovered code is 42.

20.1.4. Scaling up: a real modulus and a factored root🔗

The toy scanned a two-digit code. A real secret is far too large to scan for, so the recovery has to change in two places. This page runs the same attack against a genuine 2048-bit RSA modulus, with an unknown field of about 400 bits, and makes both changes.

First, the lattice grows. In place of the four-row single-shift basis we take the nine polynomials N^(2-j)·xⁱ·f(x)ʲ for i, j ∈ {0, 1, 2}: the multiples of N², of N·f, and of f², each shifted by 1, x, and x². These extra shift polynomials push the recoverable bound up from about N^(1/6) toward N^(1/3), comfortably covering the 400-bit secret.

Second, the root search changes. The reduced short vector is again a polynomial g with x₀ as an integer root, but x₀ is now a 120-digit number and g has degree eight; no bounded scan can find the root. Instead we factor g over the integers with Hex.ZPoly.factorize (via the .factors accessor), the project's Berlekamp-Zassenhaus factorizer, and read the secret straight off the linear factor x - x₀. Factoring a degree-eight integer polynomial, even with its very large coefficients, is instant; the lattice reduction is the only real cost.

20.1.5. Toy versus real🔗

This tutorial is deliberately staged. The first instance is a minimal single-shift lattice with a tiny modulus and a bounded root scan; it recovers roots only up to about N^(1/6). The second keeps the same skeleton but uses a real 2048-bit modulus, a nine-row lattice that reaches about N^(1/4), and Berlekamp-Zassenhaus factorization in place of the scan. Both still assume the attacker knows a bound X on the secret and work with a single polynomial in one unknown.

A production attack pushes the same idea further. It adds still more shift polynomials xⁱ·f(x)ʲ to drive the recoverable bound the rest of the way to N^(1/3), and moves to multivariate lattices for settings such as stereotyped-message recovery, partial key exposure, and the Boneh-Durfee attack on small RSA private exponents. The computational heart, encode the constraint as a lattice and reduce it, then read the root off the result, is exactly what ran above.