Small Trouble picoCTF 2026 Solution

Description

1. Step 1

   Identify the small-private-exponent (Wiener) condition

   Observation

   I noticed that e is nearly the same size as n in the message.txt parameters, which is a classic indicator that d was chosen to be small and suggested a small-private-exponent attack rather than attempting to factor n directly.

   Title hint: 'small' is d. Here d is a 256-bit prime while N is ~2000 bits. Wiener's attack requires d < N^(1/4)/3; for a 2000-bit N that ceiling is roughly 498 bits (N^(1/4) is 500 bits), so a 256-bit d sits comfortably inside the bound and continued fractions recover d directly. The flag itself confirms the intended technique: picoCTF{w13n3r_4tt4ck_...}. (Boneh-Durfee, a stronger lattice attack reaching d < N^0.292, would also work since it subsumes Wiener's range, but it is not needed here.)

   Learn more

   Why Wiener works here. Wiener's 1990 attack requires d < N^(1/4)/3. For a 2000-bit N, N^(1/4) is about 500 bits, so the ceiling is roughly 498 bits. The challenge's d is a 256-bit prime, well under that bound, so the continued-fraction convergents of e/N land on k/d and recover d directly.

   How it works. From e*d - k*phi(N) = 1 and phi(N) ≈ N, the fraction e/N is a very close approximation to k/d. The theory of continued fractions guarantees that k/d appears among the convergents of e/N when d is small enough, so you enumerate the convergents and test each candidate denominator as d.

   If d were larger. Past Wiener's ~N^(1/4) ceiling, the Boneh-Durfee (1999) lattice attack extends recovery to d < N^0.292 (about 584 bits for a 2000-bit N) using Coppersmith/LLL basis reduction. It is the right tool only when d is too big for Wiener; this challenge does not need it.

   The right way to make RSA fast is the Chinese Remainder Theorem (CRT) optimization: keep d normal-sized, store d_p = d mod (p-1) and d_q = d mod (q-1), decrypt mod p and mod q separately, recombine. Roughly 4x faster than computing m = c^d mod n directly, and no small-d exposure. See RSA attacks for CTF for the full attack catalogue.

2. Step 2

   Recover d with Wiener's continued-fraction attack

   Observation

   I noticed that d is a 256-bit prime and N is approximately 2000 bits, placing d well within Wiener's bound (~498 bits), which indicated that the continued-fraction convergents of e/N would expose k/d and recover d from the public key alone.

   Wiener's attack is pure Python: expand e/N as a continued fraction, walk its convergents, and for each convergent k/d check whether the implied phi(N) yields an integer factorization of N. The owiener library (pip install owiener) does exactly this. Once d is recovered, decrypt with m = pow(c, d, n), convert the decimal m to hex (Python's hex(m)), then decode the hex bytes to read the flag.

   bash

   pip3 install owiener

   Copied!

   python

   python3 -c "
   import owiener
   n = YOUR_N
   e = YOUR_E
   c = YOUR_C
   d = owiener.attack(e, n)
   print('recovered d =', d)
   m = pow(c, d, n)
   print(bytes.fromhex(hex(m)[2:]))
   "

   Copied!

   Expected output

   b'picoCTF{w13n3r_4tt4ck_...}'

   What didn't work first

   Tried: Reach straight for the Boneh-Durfee lattice attack (SageMath + LLL) assuming Wiener's bound is too tight.

   Boneh-Durfee is heavier machinery than this challenge needs. Wiener's bound for a 2000-bit N is roughly N^(1/4)/3 ~ 498 bits, and d here is only 256 bits, so the simple continued-fraction attack recovers d directly. The flag (picoCTF{w13n3r_4tt4ck_...}) confirms Wiener is the intended path. Boneh-Durfee would also succeed (its N^0.292 bound subsumes Wiener's), but setting up SageMath and a lattice script is wasted effort here.

   Tried: Try to factor N directly with a tool like factordb or msieve before checking the exponent size.

   N is a product of two strong ~1000-bit primes, so direct factorization is infeasible. The vulnerability is not in N at all; it is the deliberately small private exponent d. Spotting that e is nearly as large as N (a small-d fingerprint) points you to Wiener's attack, which never factors N - it derives d from the continued-fraction structure of e/N.

   Learn more

   Why continued fractions? When d is small, the fraction e/N is an extremely close rational approximation to k/d, where k comes from e*d - k*phi(N) = 1. A theorem of continued fractions guarantees that any sufficiently good rational approximation appears among the convergents, so k/d is one of the convergents of e/N. Enumerate them and you find d.

   Verifying a candidate. For each convergent k/d, compute phi = (e*d - 1)/k and check it is an integer; then solve the quadratic x^2 - (N - phi + 1)x + N = 0 for the roots p and q. If they multiply back to N, d is correct. This is exactly what owiener.attack(e, n) automates.

   Decryption after recovery. Once d is recovered, compute m = pow(c, d, n) in Python. The result is a large decimal integer. Convert it to hex with hex(m) (drop the leading 0x), then decode the hex bytes to ASCII using CyberChef's "From Hex" recipe or bytes.fromhex(...) in Python.

Flag

The RSA private exponent d is a 256-bit prime, well inside Wiener's bound (d < N^(1/4)/3, roughly 498 bits for a 2000-bit N), so the continued-fraction attack recovers d from the public key. The flag itself names the technique.