01 / PREDICTION
Conservative sufficient bound
Waiting for public challengeAn exact finite bound for the chosen lattice, not a cutoff for possible recovery.
CRYPTANALYSIS / ADVANCED
RSA Small Roots
Coppersmith · Howgrave-Graham · Exact LLL
Recover an unknown RSA message suffix or a prime from known high bits, and inspect every step from the lattice to the verified answer.
LOCAL COMPUTATIONReal arithmetic · Fresh probable-prime keys · Teaching demo, not production crypto
SET UP THE EXPERIMENT
One small unknown.
You know the prefix. A fresh suffix is encrypted with textbook RSA. Can public information recover the missing bits?
8 bits200 bits
THE ATTACKER’S VIEW
Preparing keyKNOWN PREFIX
crypto-lab://known-prefix/Public informationUNKNOWN SUFFIX64 hidden bits
TURN THE MISSING PART INTO AN EQUATION
f(x) = (A + x)³ − c ≡ 0 mod N
The full message is large. Only x, the unknown suffix, needs to be small.
- 1Public challenge
- 2Integer lattice
- 3Exact LLL
- 4Integer roots
- 5Public check
Generating a fresh 512-bit demonstration key…
PUBLIC EXPONENTe = 3
UNKNOWN RANGE0 ≤ x < 2⁶⁴
LATTICE DIMENSION8 × 8
The worker receives N, e, ciphertext, prefix, and suffix width. It receives no private key or secret suffix.
02 / CERTIFICATE
Computed vector
Run the attack to computeA short enough vector proves the modular root is also an integer root.
03 / RECOVERY
Exact public verification
No result yetEvery candidate must pass the original RSA equation or the hinted-factor check.
ALARM / CONFIDENTIALITY LOST
Suffix recovered without the private key.
RECOVERED SUFFIX · FIXED-WIDTH HEX
A correct encryption/decryption round trip does not establish confidentiality.
This attack knows the prefix and recovers the missing suffix. It does not recover an arbitrary message from its ciphertext.
FOLLOW THE EVIDENCE
Open the computation.
01 Public challenge & bound The complete attacker inputs
Preparing a public challenge.
02 Inspect lattice Original basis, reduced basis, transformation
Run the attack to inspect the integer lattice.
03 Inspect reduction Actual LLL operations, step by step
Run the attack to inspect its reduction trace.
04 Polynomial, certificate & roots Select any reduced row
Run the attack to inspect root isolation and exact candidate checks.
THE IDEA BEHIND THE ATTACK
Too large for a cube root. Small enough for a lattice.
Try the shortcut
If the entire message is so small that cubing never wraps around the modulus, an integer cube root recovers it.
Preparing exact cube-root checks.
This is the integer cube-root attack. Håstad’s broadcast attack instead combines ciphertexts by CRT and compares with the product of the recipients’ moduli. Explore RSA Forge.
Keep just the unknown small
The prefix shifts a small suffix into a much larger message. Polynomial shifts encode the modular equation in an integer lattice.
Known prefix + small x
↓ scaled polynomial coefficients ↓
Integer lattice
↓ scaled polynomial coefficients ↓
Integer lattice
The factor-hint scenario uses the same idea, but the equation vanishes modulo an unknown divisor. It needs leaked high bits and does not rely on a small public exponent.
Make modular become integer
LLL finds short combinations. When an integer is divisible by a large modulus and smaller in magnitude than that modulus, it must be zero.
bᵐ divides h(x₀)
|h(x₀)| < bᵐ
⇒ h(x₀) = 0 over the integers
|h(x₀)| < bᵐ
⇒ h(x₀) = 0 over the integers
Exact Sturm sequences isolate roots without scanning every suffix. Re-encryption or candidate divisibility supplies the final public check.
The mathematics, assumptions & sources
The basis and its bound
For degree r, multiplicity m, and t extra shifts, n = rm + t. Rows are N^(m−i) x^j f^i for 0 ≤ i < m, 0 ≤ j < r, followed by x^j f^m for 0 ≤ j < t. Column ℓ is scaled by X^ℓ. Completed rows are never reduced modulo N.
D = N^[rm(m+1)/2] X^[n(n−1)/2]. With δ = 3/4, the finite sufficient inequality is C X^Q < N^E, where Q = n(n−1), C = n^n 2^[n(n−1)/2], and E = 2βmn − rm(m+1). β = 1 for messages and 1/2 for the promised larger prime.
The sufficient bound is a guarantee for this construction, not a boundary beyond which recovery is impossible. Asymptotic scales N^(1/3) and N^(1/4) require suitable growing lattice parameters; they are not the finite guarantees for every browser preset.
The certificate
For the selected original vector v, S = Σvℓ². Require nS < N^(2m) for the message, or nS < N^m for the larger-prime hint. Cauchy–Schwarz then gives |h(x₀)| < b^m. Integer row operations preserve divisibility by b^m, so h(x₀) = 0. The factor certificate is conditional on the declared larger-prime promise until a factor is found.
What this teaches about RSA
Increasing e is not a general repair for textbook RSA’s lack of a secure encryption encoding. This known-prefix/small-suffix equation does not directly describe correctly implemented RSA-OAEP. Read PKCS #1, §7.1 for the actual OAEP construction.
Out of scope: Håstad implementation, Wiener, Boneh–Durfee, Blömer–May, arbitrary exponents or multivariate polynomials, known-LSB hints, ROCA, BKZ, and an OAEP attack.
Primary references
- Lenstra, Lenstra & Lovász (1982): the LLL algorithm.
- Coppersmith (1997): small roots and RSA vulnerabilities.
- Howgrave-Graham (1997): the modular-to-integer step.
- May (2009): the univariate construction and divisor model.
- SageMath small_roots reference: the published root-4 control.
IN YOUR BROWSER
Keys and secrets stay in session memory. No server solver, telemetry, or secret persistence. Probable primes use a small-prime sieve and 64 independently sampled Miller–Rabin rounds. Demonstration keys are unsuitable for deployment.