# CTF-writeups

Some CTF writeups

Project maintained by Qyn-CTF

## First looks

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.

## Solving

### Recovering $$dp, dq$$

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

### Recovering a factor of $$\varphi(N)$$

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)$$.

### Recovering $$\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}

Home