Rating:
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!
