b00tl3gRSA3 picoCTF 2019 Solution

Description

1. Step 1Understand Wiener's attack
   Get n and e from the challenge file. Wiener's attack exploits RSA keys where the private exponent d is small relative to n. It uses the continued fraction expansion of e/n to recover d efficiently.
   bash

   cat pk

   Copied!
   Learn more

   Wiener's theorem (1990). If d < n^(1/4) / 3, then d can be recovered from the public key (n, e) alone in polynomial time. The trick is that the secret k/d appears as a convergent of the continued fraction expansion of e/n.

   The derivation. By definition e*d ≡ 1 (mod φ(n)), so for some integer k:

   e*d - k*φ(n) = 1
   =>  e*d - k*n + k*(n - φ(n)) = 1
   =>  e/n - k/d = (1 - k*(n - φ(n))) / (d*n)
   
   For an RSA modulus, n - φ(n) = p + q - 1 < 3*sqrt(n).
   So |e/n - k/d| < 1/(2*d^2)  whenever d < n^(1/4)/3.
   
   Theorem (continued fractions): any fraction k/d satisfying
      |x - k/d| < 1/(2*d^2)
   is one of the convergents of the continued fraction of x.

   Mini worked example. Take p = 17, q = 23, n = 391, φ(n) = 352, choose tiny d = 5. Then e ≡ d^(-1) ≡ 141 (mod 352), so e = 141. Continued fraction of 141/391:

   141/391 = [0; 2, 1, 3, 5, 1, 1, 2]
   Convergents h_i / k_i:
     0/1, 1/2, 1/3, 4/11, 21/58, 25/69, 46/127, 117/322
   
   Test each convergent (h, k) as candidate (k_guess, d_guess):
     d=2: ed - 1 = 281, /k = 281/1 -> not (p-1)(q-1) of valid (p,q)
     d=3: ed - 1 = 422, /k = 422/1 -> 422 = (p-1)(q-1) ?
          solve x^2 - (n - φ + 1)x + n = 0 -> not integer roots
     d=5: ed - 1 = 704, k from 4/11 -> 704/4 = 176 ?
     ...
     d=5, k=2 (from 2/5 ?? actually):  ed = 705, k*φ = 704
          φ = 704/2 = 352  ✓
          p+q = n - φ + 1 = 40
          solve x^2 - 40x + 391 = 0  ->  x = 17, 23  ✓
          Recovered (p, q, d) = (17, 23, 5)

   That convergent test - "is (e*d - 1)/k a valid φ(n) that factors n via the quadratic x^2 - (n - φ + 1)x + n = 0?" - is exactly the verification step inside owiener.attack. It walks the convergents of e/n in order and stops at the first one that produces real integer primes.

2. Step 2Apply Wiener's attack with owiener
   Use the owiener Python library (or implement the continued fraction attack manually). It takes n and e and returns d if the attack succeeds.
   bash

   pip3 install owiener

   Copied!

   python

   python3 << 'EOF'
   import owiener
   
   n = <PASTE_N>
   e = <PASTE_E>
   
   d = owiener.attack(e, n)
   if d is None:
       print("Wiener's attack failed - d may not be small enough")
   else:
       print(f"d = {d}")
   EOF

   Copied!
   Learn more

   What owiener does internally. The library iterates the convergents of e/n using the Euclidean algorithm:

   def convergents(num, den):
       h_prev, h = 1, 0
       k_prev, k = 0, 1
       while den:
           a, num, den = num // den, den, num % den
           h_prev, h = h, a*h + h_prev
           k_prev, k = k, a*k + k_prev
           yield h, k       # h/k is a convergent of (num/den)

   For each (k_guess, d_guess) = (h, k) convergent it tests: (1) (e*d - 1) % k == 0 so a candidate φ = (e*d - 1)/k is integer, (2) the quadratic x^2 - (n - φ + 1)x + n = 0 has integer roots (discriminant is a perfect square). The first convergent that passes both gives the real d. Total time: O(log n) iterations - microseconds even for 2048-bit moduli.

   Beyond Wiener. Boneh-Durfee (1999) extended the bound to d < n^0.292 using lattice (LLL) techniques, and the conjectured bound is d < n^0.5. In CTFs, if owiener fails but d is still small, try boneh_durfee implementations (sage, defund/cryptools).

3. Step 3Decrypt the ciphertext
   With d recovered, decrypt the ciphertext c using pow(c, d, n). Convert the integer result to bytes to read the flag.
   python

   python3 -c "
   c = <C>
   n = <N>
   d = <RECOVERED_D>
   m = pow(c, d, n)
   print(bytes.fromhex(hex(m)[2:]).decode())
   "

   Copied!
   Learn more

   Wiener's attack was the first practical attack showing that RSA key generation choices directly affect security. It led to the recommendation that d should be at least n^0.5 in length. Modern RSA key generation always ensures d is large (close to the size of n).

Alternate Solution

Flag

Use Wiener's continued fraction attack (owiener library) on the small-d RSA key to recover d and decrypt the ciphertext.