It's Not My Fault 2 picoCTF 2021 Solution

Description

1. Step 1Understand the RSA-CRT relationship

   Observation

   The server hands over n and e, generated with a CRT private exponent d_p capped at 36 bits. So the attack lives in the algebraic relationship between e, d_p, and the prime p, not in any weakness of n or e themselves.

   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 is roughly 65,536 times more work, which is months of continuous computation.

   The polynomial reformulation (Galbraith, 2012): Pick a random m and split the unknown as d_p = l + L*l'. Then m^(e*d_p) = m^(e*l) * m^(e*L*l'), and Fermat's condition m^(e*d_p) = m mod p rearranges into a match between two precomputable lists: the inner values y_l = m^(e*l) mod n and the outer values z_l' = m * (m^(e*L*l'))^-1 mod n, with y_l = z_l' mod p for the correct pair. (Note that m^(e*x) - m is not itself a polynomial in x, which is why the substitution matters.) So build the single degree-2^18 polynomial F(x) = prod_l (x - y_l), evaluate it at all 2^18 outer points in one subproduct-tree multipoint evaluation, and take a batch GCD with n: F(z_l') is divisible by p exactly for the right l'.

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

2. Step 2Build the subproduct tree in SageMath

   Observation

   A 2^36 bound on d_p rules out the brute-force GCD loop from Part 1. Splitting it meet-in-the-middle into two 2^18 loops, paired with polynomial multipoint evaluation on a subproduct tree, drops the cost to roughly 2^18 polylog operations, which fits the 15-minute 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]
   
   # inner points: y_l = m^(e*l) mod n for l in 0..L-1
   print("Building inner points...")
   inner = []
   mpower = Integer(1)
   for l in range(L):
       inner.append(mpower)
       mpower = (mpower * me) % n
   
   # F(x) = prod_l (x - y_l), degree L, is exactly the root of the tree
   print("Building F(x) = prod (x - y_l)...")
   F = subproduct_tree(inner)[-1][0]
   
   # ---- meet-in-the-middle ----
   # d_p = l + L*l', so m^(e*d_p) = m^(e*l) * m^(e*L*l').
   # The condition m^(e*d_p) = m (mod p) rearranges to
   #   y_l = z_lprime   (mod p),  with z_lprime = m * (m^(e*L*l'))^-1 mod n,
   # so F(z_lprime) = 0 mod p for the correct l'. Evaluate F at every outer
   # point in ONE multipoint evaluation instead of L separate tree walks.
   print("Building outer points...")
   mL = pow(m, e * L, n)
   outer = []
   w = Integer(1)
   for lprime in range(L):
       outer.append(Integer(m) * inverse_mod(w, n) % n)
       w = (w * mL) % n
   
   print("Multipoint evaluation of F at the outer points...")
   evals = multipoint_eval(F, subproduct_tree(outer))
   
   # batch GCD: p divides the product because it divides one evaluation
   prod = Integer(1)
   for v in evals:
       prod = (prod * Integer(v)) % n
   g = gcd(Integer(prod), n)
   if 1 < g < n:
       p = g
       q = n // p
       print("p =", p)
       print("q =", q)
       print("p + q =", p + q)
   else:
       print("no factor found: try a different m")

   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 takes a few minutes. At 2^36 the same code runs about 65,536 times longer, which is months of continuous computation on one machine, against a 15-minute window. The meet-in-the-middle split reduces this to 2^18 polynomial evaluations rather than testing every d_p.

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

   F has degree 2^18, so evaluating it naively costs 2^18 multiplications per point, and doing that for 2^18 outer points puts the total back near 2^36. The subproduct tree amortizes those inner evaluations into O(N log^2 N) polynomial operations by computing every remainder in one top-down pass, and that is what fits the attack inside the 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 candidates are folded into the single polynomial F(x) = prod (x - m^(e*l)), and the outer candidates become the 2^18 points that polynomial is evaluated at, so the entire search is one multipoint evaluation costing 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 exactly one.

3. Step 3Recover the primes and compute p + q

   Observation

   A non-trivial GCD out of the polynomial evaluation gives one prime directly. Since n is p times q, the other follows by integer division, and the server's required p + q is one addition away.

   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, which is 0 when p divides n exactly, not q. What you want is the quotient: integer division, n // p. Submit the remainder, or confuse it with the quotient, and the server rejects the answer.

   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 sometimes returns a composite factor, or an artefact of the polynomial evaluation, rather than a prime. If the product of your two values does not equal n exactly, the recovered factor is invalid and the sum will be wrong. The sanity check catches that and tells the outer loop to move to the next candidate.

   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'.