TLDR (Full writeup @ [https://www.nullhardware.com/reference/hacking-101/picoctf-2022-greatest-hits/nsa-backdoor/](https://www.nullhardware.com/reference/hacking-101/picoctf-2022-greatest-hits/nsa-backdoor/))
We need to solve $3^m = c \text{ mod n}$ for `m` given `c` & `n` (discrete logarithm).
1. Factor `n` into `p` and `q` using Pollard's p-1 algorithm (`primefac.pollard_pm1`)2. Solve for c `mod p` and `mod q` - We will solve the discrete log over `p` and `q` and use CRT to find the answer `mod n`	```python	cp = c % p	cq = c % q	```3. Define a simple algorithm to bruteforce a discrete logarithm (for simple problems):	```python	def dlog_brute(g, h, p, pi):			'''solves g^x = h (mod p) for some x, where x only takes values in the range [0, pi)'''			l=[]			c_power = 1			for xi in range(pi): # HERES THE BRUTE!					if c_power == h:							l.append(xi)					c_power = c_power*mpz(g) % p # next power of g, just pow(g,xi,p)			assert len(l) > 0, f"WARNING prime {p}, g={g}, h={h} has NO solutions! Error!"			assert len(l) < 2, f"WARNING prime {p}, g={g}, h={h} has multiple solutions: {l}. Error!"			return l[0]	```4. Define a naive form of [Pohlig-Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm) - this version need not handle repeated prime factors	```python	def naive_pohlig_hellman(h, p, p_factors):		'''solve g^x === h mod p, when p-1 has prime factors p_factors, assumed multipliticy is 1 (ie: no repeated prime factors).		Naive implementation of Pohlig-Hellman_algorithm.		'''		assert len(p_factors) == len(set(p_factors)), "Repeated prime factor found. The naive form of this algorithm will not work"		x=[]		for pi in p_factors:				gi = pow(g, (p-1)//pi, p)				hi = pow(h, (p-1)//pi, p)				x.append(dlog_brute(gi,hi,p,pi))
		X=chinese_remainder(p_factors,x)		return X	```5. The CRT implementation is as follows:	```python	import math	def chinese_remainder(n, x):			s = 0			p = math.prod(n)			for ni, xi in zip(n, x):					pi = p // ni					s += xi * pow(pi, -1, ni) * pi			return s % p	```6. Factor `p-1` and `q-1` into their prime factorizations:	```python	pm1_factors = list(primefac.primefac(p-1))	pm1_factors.sort()	qm1_factors = list(primefac.primefac(q-1))	qm1_factors.sort()	```7. Observe that the prime-factor of 2 causes problems for these numbers. Both values (`0` and `1`) are equally valid solutions. We will remove the prime-factor of 2 and use the CRT manually with each of those values to generate two unique solutions `mod p` (and another two `mod q`).	```python	xp = naive_pohlig_hellman(g, cp, p, pm1_factors[1:])	XP0 = chinese_remainder([(p-1)//2, 2], [xp, 0])	XP1 = chinese_remainder([(p-1)//2, 2], [xp, 1])	assert pow(g,XP0,p) == cp, "XP0 is not solution mod p!"	assert pow(g,XP1,p) == cp, "XP1 is not solution mod p!"
	xq = naive_pohlig_hellman(g, cq, q, qm1_factors[1:])	XQ0 = chinese_remainder([(q-1)//2, 2], [xq, 0])	XQ1 = chinese_remainder([(q-1)//2, 2], [xq, 1])	assert pow(g,XQ0,q) == cq, "XQ0 is not solution mod q!"	assert pow(g,XQ1,q) == cq, "XQ1 is not solution mod q!"	```8. Try all pairs, use the CRT, and see if any result in a valid solution `mod n` (the real solution will also have valid solutions `mod p` and `mod q`):	```python	import itertools	from binascii import unhexlify	for a,b in itertools.product([XP0,XP1],[XQ0,XQ1]):			s=chinese_remainder([p,q],[a,b])			if pow(g,s,n) == c:					assert pow(g,s,p) == cp and pow(g,s,q) == cq, "Solution did not satisfy mod p and mod q"					print(f"Found Message:\nm='{unhexlify(s.digits(16)).decode()}'")	``` 	Please note that there are 2 solutions `mod p` and 2 solutions `mod q`. If your discrete logarithm routine only gave you one of them, you may have just gotten lucky!