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.


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:
            number //= 2
    while currentFactor <= limit:
        if number % currentFactor == 0 and isPrime(currentFactor):
            number //= currentFactor
            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}