NSA Backdoor picoCTF 2022 Solution

Description

1. Step 1

   Recognize the smooth-prime discrete log setup

   Observation

   I noticed the generator script encodes the flag as c = 3^flag mod n rather than flag^e mod n, which suggested the problem is a discrete logarithm rather than RSA inversion, and the deliberately smooth primes hinted that Pohlig-Hellman would be the intended solver.

   Read the generator. It produces primes whose order is smooth (p-1 and q-1 are products of small factors), exactly like the "very-smooth" challenge. Crucially the flag is encoded as c = 3^flag mod n, so recovering the flag means solving a discrete logarithm to base 3 modulo n, not decrypting RSA. The David Wong paper referenced by the challenge describes using Pohlig-Hellman as a shortcut on a composite modulus with smooth order, then reassembling with CRT.

   Learn more

   The challenge name and prompt nod to Dual_EC_DRBG, but the actual mechanism is the construction from David Wong's How to Backdoor Diffie-Hellman paper: choose a composite modulus whose group order is smooth (only small prime factors), which makes the discrete logarithm easy to solve via Pohlig-Hellman.

   The smoothness has two consequences. First, n factors instantly with Pollard's p-1 because each prime p has a smooth p-1 (this is the same weakness as the "very-smooth" challenge). Second, once you know each prime factor, the discrete log modulo that prime is cheap because the multiplicative group has small-factor order.

   This is not RSA. There is no private exponent d to recover and no pow(c, d, n) decryption. The plaintext is the exponent: c = 3^flag mod n, so you must take a logarithm, not invert an exponentiation.

2. Step 2

   Factor n with Pollard's p-1

   Observation

   I noticed the prime generation script mirrors the 'very-smooth' challenge by constructing primes whose p-1 values have only small factors, which is precisely the condition Pollard's p-1 exploits to factor the modulus in seconds.

   Because each prime was generated so that p-1 is smooth, Pollard's p-1 recovers a factor immediately. SageMath has this built in, or use the standalone primefac package (pip3 install primefac) which the challenge author used, calling its Pollard p-1 routine on n to get p and q.

   python

   # Option A: pip package the author used
   pip3 install primefac
   python3 -c "
   import primefac
   n = <N_FROM_OUTPUT>
   p = primefac.pollard_pm1(n)   # smooth p-1 makes this instant
   q = n // p
   print('p =', p)
   print('q =', q)
   "

   Copied!

   bash

   # Option B: SageMath
   sage -c "n = <N_FROM_OUTPUT>; print(factor(n))"

   Copied!

   What didn't work first

   Tried: Trying to factor n with yafu or msieve (general-purpose sieve methods) instead of Pollard's p-1.

   General sieves (GNFS, MPQS) target arbitrary hard semiprimes and will stall for hours on a 1024-bit n. The weakness here is not size but smoothness of p-1; Pollard's p-1 exploits exactly that structure and finishes in seconds. Switching to a sieve ignores the backdoor and turns an easy problem hard.

   Tried: Calling primefac.factorint(n) expecting it to automatically pick the best method.

   primefac.factorint tries several methods in sequence and may fall back to trial division or Lenstra ECM before reaching Pollard p-1; on a large n this can time out or return a partial factorization. Calling pollard_pm1 directly targets the known weakness. If factorint stalls, switch to the explicit Pollard p-1 call or use SageMath's factor() which also applies p-1 early.

   Learn more

   Pollard's p-1 factoring works when a prime factor p of n has the property that p - 1 is B-smooth (all its prime factors are below some bound B). It computes a^(k!) - 1 mod n for increasing k; once k! is a multiple of the order of a modulo p, gcd(a^(k!) - 1, n) reveals p. The challenge deliberately constructs such primes, so this terminates almost immediately.

   See the sibling challenge very-smooth for the same prime-generation weakness, where it is used to break RSA directly. Here the same factoring step is just the first half of the attack.

3. Step 3

   Solve the discrete log mod p and mod q, then CRT

   Observation

   I noticed that with p and q known, the multiplicative groups mod p and mod q each have smooth order, which meant SageMath's discrete_log (using Pohlig-Hellman) could solve log base 3 of c cheaply in each group and CRT would reconstruct the full flag integer.

   Set up the integers mod p and mod q in SageMath, reduce c into each, and call discrete_log(c mod p, Mod(3, p)) and discrete_log(c mod q, Mod(3, q)). Sage uses Pohlig-Hellman automatically when the order is smooth. You then have flag mod (order_p) and flag mod (order_q); combine the residues with the Chinese Remainder Theorem to get the integer flag, then convert it from a big integer to bytes.

   python

   # Run in SageMath (or sagemath.org if local install is painful)
   sage <<'EOF'
   n = <N_FROM_OUTPUT>
   c = <C_FROM_OUTPUT>
   p = <P_FROM_POLLARD>
   q = <Q_FROM_POLLARD>
   
   # Discrete log of c to base 3, modulo each prime.
   # Sage applies Pohlig-Hellman because the group order is smooth.
   xp = discrete_log(Mod(c, p), Mod(3, p))
   xq = discrete_log(Mod(c, q), Mod(3, q))
   
   # Recombine with CRT over the respective subgroup orders.
   flag_int = crt([Integer(xp), Integer(xq)],
                  [Mod(3, p).multiplicative_order(),
                   Mod(3, q).multiplicative_order()])
   print(flag_int)
   
   from Crypto.Util.number import long_to_bytes
   print(long_to_bytes(int(flag_int)))
   EOF

   Copied!

   What didn't work first

   Tried: Treating it as RSA and computing pow(c, d, n) with d = modular_inverse(3, phi(n)) to 'decrypt' c.

   RSA decryption inverts c = m^e mod n to recover m. Here the encoding is the reverse: c = 3^flag mod n, so the flag is the exponent, not the base. Computing pow(c, d, n) with any d produces a meaningless large integer, not the flag. The correct operation is a discrete logarithm - asking 'to what power must 3 be raised to produce c mod p?'.

   Tried: Calling discrete_log(Mod(c, n), Mod(3, n)) directly on the composite modulus n instead of factoring first.

   SageMath's discrete_log over Z/nZ with composite n does not automatically apply Pohlig-Hellman; it either errors or attempts Baby-Step Giant-Step over the full group, which is computationally infeasible for a 1024-bit modulus. The attack requires factoring n into p and q, solving the discrete log modulo each prime separately (where the smooth order makes Pohlig-Hellman cheap), and then recombining the two residues with CRT.

   Learn more

   The Pohlig-Hellman algorithm reduces a discrete log in a group of smooth order to a set of discrete logs in small prime-order subgroups (each solved by Baby-Step Giant-Step), then stitches them together with CRT. SageMath's discrete_log picks this path automatically once the order factors into small primes, which is exactly the case the challenge engineers.

   Solving modulo each prime separately and recombining with the Chinese Remainder Theorem is the standard trick for discrete logs over a composite modulus: the multiplicative group mod n splits as the product of the groups mod p and mod q. Convert the recovered integer to bytes (hex to ASCII) to read the flag.

   The takeaway mirrors the real Dual_EC_DRBG story: cryptographic constants and parameters must be nothing-up-my-sleeve. Here the "backdoor" is simply choosing smooth primes, which silently makes both factoring and discrete log tractable for anyone who knows to look.

Flag

Unsolved during the competition. This is a discrete log challenge (c = 3^flag mod n), not RSA. Factor n with Pollard's p-1 (smooth primes), solve discrete_log base 3 of c modulo p and modulo q with SageMath (Pohlig-Hellman), CRT the residues, then convert the integer to bytes.