Leaking for Answers

We need to solve some RSA from given numbers.

First question: given \(n\) and \(p-q\), solve \(p\) and \(q\).

Since \(n = pq\), so \(n=p(p-(p-q))\), \(p^2-(p-q)p-n=0\), solve the quadratic equation to find \(p\).

Second equation: given \(n\), \(e\), \(\phi^{-1}d \bmod n\).

Since \(ed = 1 \bmod \phi\), so there is a \(k\) where \(ed = \phi k+1\), so \(\phi^{-1}de = k + \phi^{-1} \pmod n\).

The \(k\) is small, because \(e\) is not large. So we can enumerate \(k\) until we find \(\phi\). Given \(\phi\), we know that \(\phi = pq - p - q + 1\) and \(n = pq\), so \(p + q = n + 1 - \phi\), \(p (p + q - p) = n\), \(-p^2 + (p + 1) * p - n = 0\), solve the quadratic equation to find \(p\).

Third equation, given \(n\), \(e\) and \(d\), use existing code to solve.

Fourth question, given \(n\), pow(p, -q, q) and pow(q, -p, p). By Fermat's little theorm, pow(p, -q, q) equals to inverse of \(p\) modulo \(q\). Let A=pow(p, -q, q), B=pow(q, -p, p), so \(Ap = 1 \pmod q\) and \(Bq = 1 \pmod p\), then \(Ap+Bq = 1 \pmod p\) and \(Ap+Bq = 1 \pmod q\), \(Ap+Bq = 1 \pmod n\), since \(A<q\) and \(B<q\), so \(Ap+Bq=n+1\) is the only solution. Then, we can solve \(p\) from the quadratic equation \(A p^2 - (n+1)p + Bn = 0\).

Attack script:

from pwn import *
import math
import tqdm

context(log_level="debug")

r = remote("46.101.163.234", 32080)

# first question: known n and p-q
r.recvuntil(b"n = ")
n = int(r.recvline().decode().strip())
print("n", n)
r.recvuntil(b"p-q = ")
diff = int(r.recvline().decode().strip())
print("p-q", diff)

# n = p * (p - diff)
# p ** 2 - diff * p - n = 0
# p = (diff + sqrt(diff ** 2 + 4 * n)) / 2
p = (diff + math.isqrt(diff**2 + 4 * n)) // 2
q = n // p
assert n == p * q
r.sendline(f"{p},{q}".encode())

# second question: known n, e, pow(phi, -1, n) * d % n
# e*d = 1 mod phi
# e*d = phi*k+1
# pow(phi, -1, n) * d * e = k + pow(phi, -1, n)
r.recvuntil(b"n = ")
n = int(r.recvline().decode().strip())
print("n", n)

r.recvuntil(b"e = ")
e = int(r.recvline().decode().strip())
print("e", e)

r.recvuntil(b"pow(phi, -1, n) * d % n = ")
result = int(r.recvline().decode().strip())
print("pow(phi, -1, n) * d % n", result)

# find k
for k in tqdm.trange(100000):
    phi_inv = result * e % n - k
    phi = pow(phi_inv, -1, n)
    # good phi?
    # phi = p * q - p - q + 1
    # n = p * q
    # p + q = n + 1 - phi
    p_plus_q = n + 1 - phi
    # p * (p_plus_q - p) = n
    # - p ** 2 + p_plus_q * p - n = 0
    p = (-p_plus_q - math.isqrt(p_plus_q**2 - 4 * n)) // -2
    q = n // p
    if p * q == n and (p - 1) * (q - 1) == phi:
        # found
        r.sendline(f"{p},{q}".encode())
        break

# third question: known n, e, d
r.recvuntil(b"n = ")
n = int(r.recvline().decode().strip())
print("n", n)

r.recvuntil(b"e = ")
e = int(r.recvline().decode().strip())
print("e", e)

r.recvuntil(b"d = ")
d = int(r.recvline().decode().strip())
print("d", d)

# https://gist.github.com/ddddavidee/b34c2b67757a54ce75cb
from math import gcd  # for gcd function (or easily implementable to avoid import)
import random  # for random elements drawing in RecoverPrimeFactors


def failFunction():
    print("Prime factors not found")


def outputPrimes(a, n):
    p = gcd(a, n)
    q = int(n // p)
    if p > q:
        p, q = q, p
    print("Found factors p and q")
    print("p = {0}".format(str(p)))
    print("q = {0}".format(str(q)))
    return p, q


def RecoverPrimeFactors(n, e, d):
    """The following algorithm recovers the prime factor
    s of a modulus, given the public and private
    exponents.
    Function call: RecoverPrimeFactors(n, e, d)
    Input:  n: modulus
                    e: public exponent
                    d: private exponent
    Output: (p, q): prime factors of modulus"""

    k = d * e - 1
    if k % 2 == 1:
        failFunction()
        return 0, 0
    else:
        t = 0
        r = k
        while r % 2 == 0:
            r = int(r // 2)
            t += 1
        for i in range(1, 101):
            g = random.randint(0, n)  # random g in [0, n-1]
            y = pow(g, r, n)
            if y == 1 or y == n - 1:
                continue
            else:
                for j in range(1, t):  # j \in [1, t-1]
                    x = pow(y, 2, n)
                    if x == 1:
                        p, q = outputPrimes(y - 1, n)
                        return p, q
                    elif x == n - 1:
                        continue
                    y = x
                    x = pow(y, 2, n)
                    if x == 1:
                        p, q = outputPrimes(y - 1, n)
                        return p, q


p, q = RecoverPrimeFactors(n, e, d)
r.sendline(f"{p},{q}".encode())

# fourth question: known n, pow(p, -q, q), pow(q, -p, p)
# pow(p, q, q) = p, pow1 * p = k * q + 1
# pow(q, p, p) = q, pow2 * q = l * p + 1
# (pow1 * p + pow2 * q) mod p = 1
# (pow1 * p + pow2 * q) mod q = 1
# therefore:
# (pow1 * p + pow2 * q) mod n = 1
# pow1 < q, pow2 < p, so
# pow1 * p + pow2 * q = n + 1
# pow1 * p ** 2 + pow2 * n = (n + 1) * p
# pow1 * p ** 2 - (n + 1) * p + pow2 * n = 0
# p = ((n + 1) + sqrt((n + 1) ** 2 - 4 * pow1 * pow2 * n)) / 2 / pow1
r.recvuntil(b"n = ")
n = int(r.recvline().decode().strip())
print("n", n)

r.recvuntil(b"pow(p, -q, q) = ")
pow1 = int(r.recvline().decode().strip())
print("pow(p, -q, q)", pow1)

r.recvuntil(b"pow(q, -p, p) = ")
pow2 = int(r.recvline().decode().strip())
print("pow(q, -p, p)", pow2)
p = ((n + 1) + math.isqrt((n + 1) ** 2 - 4 * pow1 * pow2 * n)) // (2 * pow1)
q = n // p
assert n == p * q
r.sendline(f"{p},{q}".encode())

r.recvall()

Flag: HTB{t0_l34k___0r_n0t___t0_l34k_f0r_4nsw3rs_758dd2da6409e36a5ec63cc933a8bf1f}.