We’re given \(dp \times dq\) and \(dp + dq\) where \(dq = d \bmod (q-1)\) and \(dp = d \bmod (p-1)\), we’re also given \(e = 65537\), and the ciphertext. Our goal is to recover the modulus \(N = p \times q\) to finally decrypt the ciphertext.

We can combine \(dp \equiv d \bmod (p-1)\) and \(dq \equiv d \bmod (q-1)\) to the following: \((dp-d) \times (dq-d) \equiv 0 \bmod \varphi(N)\) where \(\varphi(N) = (p-1)\times(q-1)\). This is essentially a quadratic equation: \(d^2 + dpq - d \times (dp + dq - d) \equiv 0 \bmod \varphi(N)\). We can then use the *simplified* quadratic formula to solve this: \(dp,dq = \dfrac{dp + dq}{2} \pm \sqrt{(\dfrac{dp + dq}{2})^2 - dp \times dq}\) since \((\dfrac{dp + dq}{2})^2 - dp \times dq\) is a perfect square. Now we know \(dp, dq\).

In the previous section, we combined two equations to get this: \(d^2 + dpq - d \times (dp + dq - d) \equiv 0 \bmod \varphi(N)\), however, \(d = \dfrac{\varphi(N) + 1}{e}\). So \((\dfrac{\varphi(N) + 1}{e}))^2 + dpq - (\dfrac{\varphi(N) + 1}{e}) \times (dp + dq - d) \equiv 0 \bmod \varphi(N)\), so by multiplying with \(e\), we can simplify, because of the \(\bmod \varphi(N)\) we get: \(e \times (dpq \times e - (dp + dq)) + 1 \equiv 0 \bmod \varphi(N)\).

So \(e \times (dpq \times e - (dp + dq)) + 1\) is a factor of \(\varphi(N)\).

We can now recover the original \(\varphi(N)\), since \(e \times (dpq \times e - (dp + dq)) + 1\) is build up from a lot of smaller prime factors:

```
def factor(n, limit):
number = n
factors = []
currentFactor = 3
while True:
if number % 2 == 0:
factors.append(2)
number //= 2
else:
break
while currentFactor <= limit:
if number % currentFactor == 0 and isPrime(currentFactor):
factors.append(currentFactor)
number //= currentFactor
else:
currentFactor += 2
return factors
nPhiN = e * (dpq * e -dp_q) + 1
factors = factor(nPhiN, 100000)
```

Alternatively, use `factordb`

.

We can now enumerate through all the factors in such a way that the order doesn’t matter and that we don’t check the same factor multiple times, even though it occurs in `factors`

multiple times. For simplicity, I just used `itertools.combinations`

(Which will be a bit less efficient, since it doesn’t satisfy the last rule, but it works):

```
for i in range(1, len(factors)):
perms = combinations(factors, i)
for combs in perms:
num = 1
for comb in combs:
num *= comb
phiN = nPhiN // num
#...
print(f"Finished perm: {i}")
```

From here we can get a value for \(d = e^{-1} \bmod \varphi(N)\) and at that point we can run the solution script from `RSAga 1`

since we recovered \(dp, dq\) in the first step and modifying it a bit.

*Note, there are many ways to solve this from this point*

Which finally gives us the flag:
`HackTM{36f1a66ce55057caeebfa274c1d0abc67e3fd95c83ec0252812b38dfd2a1fd60d6172d793c3124acd02b5504cb7ce19c87896b5ac24bb324528f4b934f0232a3}`