Writeup · 31 Nights of Root

Fianchetto

cryptomediumsolvedFlag: r00t{REDACTED}

Overview

An RSA keypair “deliberately built with an unusually small private exponent for efficiency.” We are given the public modulus N, the public exponent e, and the ciphertext c containing the flag. The hint points straight at a small d, which is the textbook setup for Wiener’s attack.

Recon

Inspecting the parameters:

import json
d = json.load(open("fianchetto_challenge.json"))
N, e, c = d["N"], d["e"], d["c"]
print(N.bit_length(), e.bit_length(), c.bit_length())
N: ~2048 bits
e: ~2048 bits   <-- as large as N
c: ~2048 bits

Exploitation

The key relation is e*d = 1 + k*phi(N), so e/N ≈ k/d. For each convergent k/d of e/N:

  1. Check (e*d - 1) % k == 0, then compute the candidate phi = (e*d - 1) // k.
  2. Use p + q = N - phi + 1 to form x^2 - (p+q)x + N.
  3. If the discriminant is a perfect square and the roots multiply to N, the candidate is correct.
  4. Decrypt with m = pow(c, d, N).
import json
from math import isqrt

data = json.load(open("fianchetto_challenge.json"))
N, e, c = data["N"], data["e"], data["c"]

def cf(n, d):
    while d:
        q = n // d
        yield q
        n, d = d, n - q * d

def convergents(a):
    h0, h1, k0, k1 = 0, 1, 1, 0
    for q in a:
        h0, h1 = h1, q * h1 + h0
        k0, k1 = k1, q * k1 + k0
        yield h1, k1

for k, d in convergents(cf(e, N)):
    if k == 0 or (e * d - 1) % k:
        continue
    phi = (e * d - 1) // k
    s = N - phi + 1
    disc = s * s - 4 * N
    if disc < 0:
        continue
    r = isqrt(disc)
    if r * r == disc and (s + r) % 2 == 0:
        p, q = (s + r) // 2, (s - r) // 2
        if p * q == N:
            m = pow(c, d, N)
            print("d bits:", d.bit_length())
            print(m.to_bytes((m.bit_length() + 7) // 8, "big"))
            break
d bits: 160
b'r00t{REDACTED}'

The recovered d is only 160 bits against a 2048-bit modulus, far under the Wiener bound.

Vulnerability Analysis

Mitigations

  • Never choose a small private exponent d for performance; keep d full-size and use CRT-based decryption (dp, dq, qinv) for speed instead.
  • Use key sizes of at least 2048 bits with properly generated primes.
  • Monitor for small d during key generation and reject keys where d < N^(1/4) / 3.

Flag

r00t{REDACTED}

Lessons / Takeaways

Techniques

  • Wiener’s Attack
  • RSA Small Private Exponent
  • Continued Fractions