Small Trouble picoCTF 2026 Solution

Description

1. Step 1Identify the small-private-exponent (Wiener) condition

   Observation

   In message.txt, e is nearly as large as n, which is the classic sign that d was chosen small. That points at a small-private-exponent attack rather than factoring.

   Title hint: 'small' is d. encryption.py builds N from two 1048-bit primes (2096 bits total) and then sets d = getPrime(256) and e = inverse(d, phi), which is the wrong way round and leaves e almost as large as N. Wiener's attack requires d < N^(1/4)/3; for this 2096-bit N that ceiling is about 522 bits (N^(1/4) is 524 bits), so a 256-bit d sits comfortably inside the bound and continued fractions recover d directly. (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 this 2096-bit N, N^(1/4) is 524 bits, so the ceiling is about 522 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 612 bits for this 2096-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 2Recover d with Wiener's continued-fraction attack

   Observation

   d is 256 bits against a 2096-bit modulus, comfortably inside Wiener's bound of about 522. The continued-fraction convergents of e over N expose the ratio that yields 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{sm4ll_d_...}'

   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 needs. Wiener's bound here is about 522 bits and d is 256, so continued fractions recover it directly in a second of pure Python. Boneh-Durfee would also work, since its bound subsumes Wiener's, but setting up Sage and a lattice script buys nothing.

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

   N is the product of two strong 1048-bit primes, so factoring is out of reach. The weakness is not in N at all but in the deliberately small private exponent. An e nearly as large as N is that fingerprint, and Wiener's attack derives d from the continued fractions of their ratio without factoring anything.

   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, about 522 bits for this 2096-bit N), so the continued-fraction attack recovers d from the public key: d = 68887774502271338957062311167447501492711325582360363047266665739903259761543. The flag is shown abbreviated on this page; work the steps above to recover the full value.