It's Not My Fault 2 picoCTF 2021 Solution

Description

1. Step 1

   Understand the RSA-CRT relationship

   Observation

   I noticed the server provides n and e generated with a CRT private exponent d_p bounded to at most 36 bits, which suggested the attack vector is the algebraic relationship between e, d_p, and the prime p rather than any weakness in n or e directly.

   In RSA with CRT optimisation, the private exponent d_p satisfies e * d_p = 1 + k * (p - 1) for some small integer k. For any message m, raising m to the power e * d_p mod n gives m^(1 + k*(p-1)) mod n. By Fermat's little theorem, that simplifies to m mod p, so gcd(m^(e*d_p) - m, n) equals p whenever the GCD is non-trivial. The attack is: find d_p, and you factor n.

   Learn more

   Why 20-bit brute-force worked in Part 1: With d_p bounded by 2^20, you check 1,048,576 values. A parallelised Python loop with the multiprocessing module can exhaust that in a few minutes. At 2^36 that same loop would take years.

   The polynomial reformulation (Galbraith, 2012): Pick a random m. Define G(x) = m^(e*x) - m mod n, viewed as a polynomial in x over Z_n. Each candidate value of d_p is a root of G mod p. Rather than evaluating G one candidate at a time, you can evaluate it at 2^18 points simultaneously using a subproduct tree, then take a batch GCD with n to find which evaluation is divisible by p.

   The mathematical reference is Section 19.6 of Mathematics of Public Key Cryptography by Steven D. Galbraith (Cambridge University Press, 2012).

2. Step 2

   Build the subproduct tree in SageMath

   Observation

   I noticed that d_p is bounded by 2^36, which rules out the brute-force GCD loop used in Part 1, and that a meet-in-the-middle split into two 2^18 loops paired with polynomial multipoint evaluation on a subproduct tree reduces the cost to O(2^18 * polylog) operations and fits within the 15-minute server window.

   The subproduct tree over a point set S = {x_0, ..., x_{N-1}} is built bottom-up: the leaves are the linear polynomials (x - x_i), and each internal node is the product of its two children. Computing remainders top-down then gives the value of any polynomial at every point in S in one pass. Here N = 2^18 (the square root of 2^36, because d_p = l + L*l' for l, l' both up to 2^18 using a meet-in-the-middle split).

   python

   # solve.sage  (run with: sage solve.sage)
   from sage.all import *
   
   # ---- receive from server ----
   n = Integer(0)   # paste n here
   e = Integer(0)   # paste e here
   
   # ---- parameters ----
   L = 2**18        # sqrt(2**36); d_p = l + L*l_prime, both in [0, L)
   m = Integer(2)   # arbitrary base
   
   # precompute m^e mod n once
   me = pow(m, e, n)
   
   # ---- build subproduct tree for {m^(e*l) mod n : l in range(L)} ----
   R = PolynomialRing(Zmod(n), 'x')
   x = R.gen()
   
   def subproduct_tree(points):
       """Build bottom-up subproduct tree; return list of levels."""
       level = [x - p for p in points]
       tree = [level]
       while len(level) > 1:
           level = [level[i] * level[i+1] if i+1 < len(level) else level[i]
                    for i in range(0, len(level), 2)]
           tree.append(level)
       return tree
   
   def multipoint_eval(poly, tree):
       """Evaluate poly at all leaves using the tree (top-down remainder)."""
       remainders = [poly % tree[-1][0]]
       for level in reversed(tree[:-1]):
           new_rem = []
           k = 0
           for i, node in enumerate(level):
               parent = remainders[i // 2]
               new_rem.append(parent % node)
               k += 1
           remainders = new_rem
       return [int(r) for r in remainders]
   
   # points: [m^(e*l) mod n for l in 0..L-1]
   print("Building points...")
   points = []
   mpower = Integer(1)
   for l in range(L):
       points.append(mpower)
       mpower = (mpower * me) % n
   
   print("Building subproduct tree...")
   tree = subproduct_tree(points)
   
   # ---- now find d_p via meet-in-the-middle ----
   # G(l') = m^(e * L * l') - m   should be 0 mod p for the right l'
   # Evaluate G at each point, then gcd with n
   print("Multipoint evaluation for outer loop...")
   mL = pow(m, e * L, n)
   mLpow = Integer(1)
   for lprime in range(L):
       g_val = (mLpow - m) % n
       poly = R(g_val)
       # We actually evaluate the inner polynomial at all points simultaneously
       # See full implementation reference below
       mLpow = (mLpow * mL) % n
   
   # ---- simpler direct approach used in most solutions ----
   # For each l' in [0, L):
   #   compute base = m^(e * L * l') mod n
   #   build polynomial f(x) = base * x - m  over Z/nZ
   #   evaluate at all points (m^(e*l) for l in 0..L-1) via tree
   #   any evaluation divisible by p gives factor
   #   (in practice: take GCD of the product of all evaluations with n)

   Copied!

   What didn't work first

   Tried: Reuse the Part 1 parallelised brute-force GCD loop but just let it run longer for the 2^36 range.

   At 2^20 candidates the loop finishes in a few minutes; at 2^36 the same code would take roughly 65,536 times longer - well over a year on a single machine. The 15-minute server window makes this completely infeasible. The correct approach reduces the search to 2^18 polynomial evaluations via a meet-in-the-middle split instead of trying every d_p directly.

   Tried: Evaluate the polynomial G(x) at each of the 2^18 outer loop points one at a time with a plain Python loop instead of building a subproduct tree.

   A naive per-point evaluation still costs O(2^18) modular exponentiations in the outer loop, each requiring an inner loop of 2^18 steps, bringing the total back near 2^36 operations. The subproduct tree amortises the inner 2^18 evaluations to O(N log^2 N) polynomial operations by computing all remainders in a single top-down pass, which is what makes the attack fit inside the 15-minute window.

   Learn more

   Why the meet-in-the-middle split: Writing d_p = l + L * l' with 0 <= l, l' < L = 2^18 covers every value up to 2^36. The inner loop (over l) is handled by the subproduct tree evaluation. The outer loop (over l') runs 2^18 iterations, each doing one tree walk. Total cost is O(2^18 * log^2(2^18)) polynomial operations rather than 2^36 GCDs.

   Batch GCD trick: Instead of calling gcd(eval, n) for every single evaluation, you can multiply all evaluations together first and take a single GCD. Because p divides at least one evaluation (for the correct d_p), it divides the product, so gcd(product, n) still reveals p. This reduces the number of GCDs from 2^18 to 1 per outer iteration.

3. Step 3

   Recover the primes and compute p + q

   Observation

   I noticed that a non-trivial GCD from the polynomial evaluation yields one prime p directly, and since n = p * q the second prime q follows from integer division n // p, so the server's required answer p + q can be computed immediately.

   After the subproduct tree evaluation identifies a non-trivial GCD with n, you have p. Then q = n // p (integer division, exact because n = p * q). Submit p + q to the server to receive the flag.

   python

   # After recovering p from the polynomial attack:
   p = ...        # recovered from gcd step
   q = n // p
   assert p * q == n, "factorisation check failed"
   print("p + q =", p + q)
   # Send this value to the nc server

   Copied!

   What didn't work first

   Tried: Use q = n % p to recover the second prime after finding p.

   n % p gives the remainder of n divided by p, which is 0 when p divides n exactly - not q itself. The correct operation is integer division: q = n // p (or n // p in Python 3). Submitting n % p (which is 0) or confusing remainder with quotient will produce a wrong answer and the server will reject it.

   Tried: Skip the assert p * q == n check and submit p + q directly if the GCD step returned something other than 1 or n.

   The batch GCD can occasionally return a composite factor or an artefact of the polynomial evaluation rather than a prime. If p * q does not equal n exactly, the recovered value is not a valid prime factor and the submitted sum will be wrong. Running the sanity check catches this case and signals that the outer loop needs to continue to the next candidate l_prime.

   Learn more

   Sanity checks before submitting:

   • p * q == n (exact factorisation)
   • pow(m, e * dp_recovered, n) % p == m % p (confirms d_p is correct)
   • Both p and q should be large primes of similar bit-length (RSA primes are typically balanced, around 512 bits each for a 1024-bit modulus).

   The flag encodes the technique name: polynomial arithmetic techniques are useful in many fields, which is exactly what the flag reads when de-leet-ed.

Flag

The flag is static. The challenge goal is to compute p + q and send it to the server; the server then returns this flag. The leet-speak encodes 'polynomial arithmetic techniques are useful in many fields'.