kavklaw@llm $ cat writeup.md
RSA Partial-P Recovery via Coppersmith's Theorem
You've infiltrated Gringotts Bank using the cloak of invisibility. The vault passphrase is RSA-encrypted, and the bank will give you:
(n, e)p with the bottom 256 bits zeroed outYour goal: factor n, recover the private key, decrypt the passphrase, and unlock vault_68 to retrieve the flag.
If you're new to cryptography, don't worry — we'll build up from the basics. This challenge uses some beautiful mathematics, and I'll walk you through every step.
Before diving into the attack, let's understand what we're attacking. RSA key generation works like this:
p and q. In this challenge, each is 1024 bits (~308 digits).n = p × q. This is public. The number n is 2048 bits.φ(n) = (p-1)(q-1). This must stay secret.e = 65537 (standard choice).d = e-1 mod φ(n). This is the secret decryption key.The public key is (n, e). The private key is d. The security assumption is that factoring n into p and q is computationally infeasible. If you can factor n, you can compute φ(n), then d, and decrypt everything. That's exactly what we're going to do.
The challenge provides a Python server. Let's break down the critical parts:
class RSA():
def __init__(self, key_length):
self.e = 0x10001 # 65537
phi = 0
prime_length = key_length // 2 # 1024-bit primes for 2048-bit n
while GCD(self.e, phi) != 1:
self.p, self.q = getPrime(prime_length), getPrime(prime_length)
phi = (self.p - 1) * (self.q - 1)
self.n = self.p * self.q
self.d = inverse(self.e, phi)Standard 2048-bit RSA. Two 1024-bit primes, e = 65537. The GCD check ensures e and φ(n) are coprime (share no common factors), which is required for the inverse to exist. Nothing unusual here — this is textbook RSA.
class Bank:
def __init__(self, rsa):
self.shift = 256 # ← This is the key number
def calculateHint(self):
return (self.rsa.p >> self.shift) << self.shiftThis is where the magic happens. Let's understand this line by line:
self.rsa.p >> 256 — Shift p right by 256 bits. This throws away the bottom 256 bits (like dividing by 2256 and rounding down).... << 256 — Shift the result back left by 256 bits. This fills the bottom 256 positions with zeros.The net effect: the "hint" is p with the bottom 256 bits replaced by zeros. We get the top 768 bits of a 1024-bit prime. That's 75% of the prime leaked!
Think of it like being shown a phone number with the last 3 digits hidden: 555-0123-???. You still know most of the number. The question is: can 75% of a prime be enough to recover the rest? Spoiler: absolutely yes.
Key insight: If we knowp_high(the hint), thenp = p_high + xwherex < 2256. We need to find this smallx. And Coppersmith's theorem gives us a beautiful, efficient way to do exactly that.
This is a textbook application of Coppersmith's method for finding small roots modulo an unknown factor. Let's build up the intuition step by step.
We know:
n = p × q (given to us, 2048 bits)p (that's the hint)p = hint + x, where x is an unknown number less than 2256We also know that p divides n (by definition, since n = p × q). So:
hint + x ≡ 0 (mod p)
In other words, the polynomial f(x) = x + hint has a root modulo p — and this root is "small" (only 256 bits, compared to p's 1024 bits). Coppersmith's theorem tells us we can find this root efficiently.
The unknown x is 256 bits. That means there are 2256 possibilities — approximately 1077. For reference, the estimated number of atoms in the observable universe is about 1080. Brute force is utterly impossible.
Coppersmith's method finds x in seconds. How? Through the magic of lattices and the LLL algorithm.
Here's the core idea, stripped of jargon:
f(x) = x + hint that has a small root x₀ modulo p (an unknown factor of n).p directly because we don't know p!n (which we DO know).x₀ modulo p, then use lattice reduction to combine them into a polynomial that vanishes at x₀ over the integers (not just modulo something).x₀ over the real numbers, we can find x₀ using standard root-finding techniques.The formal statement: for a polynomial f(x) of degree d, with an unknown factor p ≥ Nβ of N, we can find all roots |x₀| < Nβ²/d in polynomial time.
For our case:
d = 1 (degree of f(x) = x + hint)β = 0.5 (since p ≈ √n — both primes are about half the bit-length of n)x₀ < N0.25 ≈ 2512 (for a 2048-bit n)x < 2256To understand Coppersmith's method, you need a basic feel for lattices. Here's the simplest possible explanation:
Imagine a sheet of graph paper. The grid lines create intersection points at regular intervals. Those points form a 2D lattice. The lattice is defined by its basis vectors — the arrows that tell you how to get from one point to the next:
Simple 2D lattice (basis: right→ and up↑):
• • • • •
• • • • •
• • • • •
• • • • •
Every point = a×(right) + b×(up) for some integers a, bBut a lattice can have a different basis that generates the same points — some bases use short, perpendicular vectors (nice!) while others use long, tilted vectors (awkward). The LLL algorithm takes any basis and finds a "nicer" one with shorter, more orthogonal vectors.
In Coppersmith's method, we construct a lattice where each point represents a polynomial. The "short" vectors (found by LLL) correspond to polynomials with small coefficients — and these small-coefficient polynomials are exactly what we need to find our root over the integers.
We build the lattice from two families of polynomials, all of which vanish at x₀ modulo pm (a power of the unknown prime):
# Shift polynomials: g_i(x) = N^(m-i) · f(x)^i for i = 0..m
# Extra polynomials: h_j(x) = f(x)^m · x^j for j = 1..t
# Each polynomial is evaluated at x·X (where X = 2^256, our bound)
# and its coefficients form a row of the lattice matrix.
# After LLL reduction, the short vectors correspond to
# polynomials with small coefficients that still vanish
# at x₀ modulo p^m.
# By Howgrave-Graham's lemma, if the coefficients are
# small enough, the polynomial also vanishes over ℤ —
# meaning we can find x₀ using standard root-finding.Why does multiplying by powers of N help? Because N = p × q, so Nk is divisible by pk. This means N(m-i)} × f(x)i is divisible by pm at x = x₀. All our polynomials agree: they all vanish at x₀ modulo pm.
For this challenge, parameters m = 7, t = 3 (giving a lattice of dimension 11) work well. The LLL algorithm reduces this 11×11 lattice in about 2 seconds.
Once we recover x₀, the rest is straightforward RSA:
p = hint + x₀ — we now know the full primeq = n / p — simple division gives us the other primeφ(n) = (p-1)(q-1) — compute the totientd = e-1 mod φ(n) — compute the private keypassphrase = encryptedd mod n — decrypt!Let's turn this math into working code. The implementation uses fpylll for lattice reduction:
#!/usr/bin/env python3
"""Gringotts Bank Solver — Coppersmith partial-p attack"""
import socket
from Crypto.Util.number import long_to_bytes, inverse
from fpylll import IntegerMatrix, LLL
def connect(host, port):
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.settimeout(15)
sock.connect((host, port))
# ... parse encrypted passphrase, n, e, hint from server
return sock, n, e, hint, encrypted
def coppersmith_factor(n, hint, shift=256):
X = 1 << shift
m, t = 7, 3
dim = m + t + 1 # = 11
def f_power_coeffs(i):
"""Binomial expansion of (x + hint)^i"""
coeffs = [0] * (i + 1)
binom = 1
for k in range(i + 1):
if k > 0:
binom = binom * (i - k + 1) // k
coeffs[k] = binom * pow(hint, i - k)
return coeffs
# Build lattice: shift polynomials + extra polynomials
rows = []
for i in range(m + 1):
fi = f_power_coeffs(i)
Npow = pow(n, m - i)
row = [0] * dim
for j in range(len(fi)):
if j < dim:
row[j] = Npow * fi[j] * pow(X, j)
rows.append(row)
fm = f_power_coeffs(m)
for j_extra in range(1, t + 1):
row = [0] * dim
for k in range(len(fm)):
idx = k + j_extra
if idx < dim:
row[idx] = fm[k] * pow(X, idx)
rows.append(row)
# LLL reduction
M = IntegerMatrix(dim, dim)
for i in range(dim):
for j in range(dim):
M[i, j] = rows[i][j]
LLL.reduction(M)
# Extract root via Newton's method on reduced polynomials
for row_idx in range(dim):
coeffs = [int(M[row_idx, j]) // pow(X, j) for j in range(dim)]
if coeffs[1] != 0:
x_est = -coeffs[0] // coeffs[1]
# Newton refinement + neighborhood scan
for delta in range(-50, 51):
x_test = x_est + delta
if 0 < x_test < X:
p_cand = hint + x_test
if n % p_cand == 0:
return p_cand, n // p_cand
return None, None
# Connect, get values, factor, decrypt
sock, n, e, hint, encrypted = connect("target", 32025)
p, q = coppersmith_factor(n, hint)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
passphrase = long_to_bytes(pow(encrypted, d, n))
# Send passphrase to vault_68 → get flag!Let's walk through the key parts of this code:
f_power_coeffs(i) — This computes the coefficients of (x + hint)i using the binomial theorem. For example, (x + hint)² = x² + 2·hint·x + hint², so the coefficients are [hint², 2·hint, 1].
Building the lattice — We create shift polynomials g_i(x) = N(m-i) · f(x)i and extra polynomials h_j(x) = f(x)m · xj. Each polynomial's coefficients (scaled by powers of the bound X) become a row in our lattice matrix. The result is an 11×11 matrix with entries that can be thousands of bits long.
LLL reduction — The fpylll library handles the heavy lifting. LLL transforms our "bad" basis (with huge, nearly parallel vectors) into a "good" basis (with short, nearly orthogonal vectors). This is where the magic happens.
Root extraction — From the reduced lattice, the first few rows correspond to polynomials with very small coefficients. For a degree-1 reduced polynomial c₀ + c₁·x, the root is simply x = -c₀/c₁. We scan a small neighborhood around this estimate to handle rounding, and check if hint + x divides n.
Connect to the service. The encrypted passphrase is displayed on connection. Then request the public key (option 1) and the hint (option 2).
With m=7, t=3, we build an 11×11 integer matrix. The entries are enormous (up to ~8000 bits), but fpylll handles this natively with arbitrary-precision arithmetic. Building the matrix takes milliseconds.
LLL runs in about 2 seconds on this lattice. The reduced basis vectors have much smaller coefficients — small enough for Howgrave-Graham's bound to guarantee that the roots we find modulo pm are also roots over the integers.
From the reduced lattice, we extract polynomial coefficients and find the integer root. The root x₀ gives us the missing 256 bits of p. We verify by checking that n % (hint + x₀) == 0.
With p and q known, standard RSA decryption recovers the passphrase:
Passphrase: horcrux_horcrux_Helga_Hufflepuff's_cup(A Harry Potter reference — fitting for a Gringotts challenge! 🧙)
Send the passphrase to vault_68:
"Coppersmith is still magic!" — Indeed. 🪄
n. The Coppersmith bound for degree-1 polynomials allows recovering up to N0.25 unknown bits — that's 512 bits for a 2048-bit modulus. Our 256-bit unknown is well within that range.p, bits of d, or even bits of the plaintext — is likely exploitable. The theorem converts "partial information" into "complete break."Nβ²/d is remarkably generous. For balanced RSA primes (β = 0.5) and a degree-1 polynomial, you can recover up to 512 unknown bits from a 2048-bit modulus. Increasing the polynomial degree reduces the bound, but even degree-2 allows 256 unknown bits.pycryptodome — RSA primitives, number theory utilitiesfpylll — LLL lattice reductionsmall_roots() method on polynomial rings over Z/nZ that implements Coppersmith automatically; fewer lines of code but requires a SageMath installation