<- HTB UNICTF

Mayday Mayday

5 minutes to read

We are given the Python source code to encrypt the flag:

from Crypto.Util.number import getPrime, GCD, bytes_to_long
from secret import FLAG
from random import randint

class Crypto:
    def __init__(self, bits):
        self.bits = bits
        self.alpha = 1/9
        self.delta = 1/4
        self.known = int(self.bits*self.delta)
    
    def keygen(self):
        while True:
            p, q = [getPrime(self.bits//2) for _ in '__']
            self.e = getPrime(int(self.bits*self.alpha))
            φ = (p-1)*(q-1)
            try:
                dp = pow(self.e, -1, p-1)
                dq = pow(self.e, -1, q-1)
                self.n = p*q
                break
            except:
                pass

        return (self.n, self.e), (dp, dq)

    def encrypt(self, m):
        return pow(m, self.e, self.n)

rsa = Crypto(2048)
_, (dp, dq) = rsa.keygen()

m = bytes_to_long(FLAG)
c = rsa.encrypt(m)

with open('output.txt', 'w') as f:
    f.write(f'N = 0x{rsa.n:x}\n')
    f.write(f'e = 0x{rsa.e:x}\n')
    f.write(f'c = 0x{c:x}\n')
    f.write(f'dp = 0x{(dp >> (rsa.bits//2 - rsa.known)):x}\n')  
    f.write(f'dq = 0x{(dq >> (rsa.bits//2 - rsa.known)):x}\n')

And we have the result in output.txt:

N = 0x78fb80151a498704541b888b9ca21b9f159a45069b99b04befcb0e0403178dc243a66492771f057b28262332caecc673a2c68fd63e7c850dc534a74c705f865841c0b5af1e0791b8b5cc55ad3b04e25f20dedc15c36db46c328a61f3a10872d47d9426584f410fde4c8c2ebfaccc8d6a6bd1c067e5e8d8f107b56bf86ac06cd8a20661af832019de6e00ae6be24a946fe229476541b04b9a808375739681efd1888e44d41196e396af66f91f992383955f5faef0fc1fc7b5175135ab3ed62867a84843c49bdf83d0497b255e35432b332705cd09f01670815ce167aa35f7a454f8b26b6d6fd9a0006194ad2f8f33160c13c08c81fe8f74e13e84e9cdf6566d2f  
e = 0x4b3393c9fe2e50e0c76920e1f34e0c86417f9a9ef8b5a3fa41b381355
c = 0x17f2b5a46e4122ff819807a9d92b6225c483cf93c9804381098ecd6b81f4670e94d8930001b760f1d26bc7aa7dda48c9e12809d20b33fdb4c4dd9190b105b7dab42e932b99aaff54023873381e7387f1b2b18b355d4476b664d44c40413d82a10635fe6e7322543943aed2dcfbe49764b8da70edeb88d6f63ee47f025be5f2f38319611ab74cd5db6f90f60870ecbb57a884f821d873db06aadf0e61ff74cc7d4c8fc1e527dba9b205220c6707f750822c675c530f8ad6956e41ab80911da49c3d6a7d27e93c44ba5968f2f47a9c5a2694c9d6da245ceffe9cab66b6043774f446b1b08ee4739d3cc716b87c8225a84d3c4ea2fdf68143d09f062c880a870554
dp = 0x59a2219560ee56e7c35f310a4d101061aa61e0ae4eae7605eb63784209ad488b4ed161e780811edd61bf593e2d385beccfd255b459382d8a9029943781b540e7
dq = 0x39719131fbfd8afbc972ca005a430d080775bf1a5b3e8b789aba5c5110a31bd155ff13fba1019bb6cb7db887685e34ca7966a891bfad029b55b92c11201559e5

Source code analysis

The server uses RSA to encrypt the flag. We are given $n$, $e$, $c$ such that

$$ c = m^e \mod{n} $$

where $m$ is the flag. Curiously, $e$ is a 227-bit prime number ($1024 / 9$).

The server also computes the private exponents for RSA-CRT decryption:

$$ d_p = e^{-1} \mod{p - 1} \qquad d_q = e^{-1} \mod{q - 1} $$

Those are 1024-bit numbers, but we are only given the upper 512 bits, let’s say $d_p^H$ and $d_q^H$.

The above $d_p$ and $d_q$ can be used to decrypt the flag using the Chinese Remainder Theorem (CRT):

$$ m_p = c^{d_p} \mod{p} \qquad m_q = c^{d_q} \mod{q} $$

Coppersmith method

When the challenge removes some bits, probably the solution is related to Coppersmith method, trying to recover small roots of a polynomial modulo a composite number.

Doing the math

We know that

$$ \begin{align*} d_p = e^{-1} \mod{p - 1} & \iff e \cdot d_p = k_p (p - 1) + 1 \\ & \iff p = \frac{e \cdot d_p - 1}{k_p} + 1 \end{align*} $$

So, we have:

$$ p = \frac{e \cdot (d_p^H + d_p^L) - 1}{k_p} + 1 \qquad q = \frac{e \cdot (d_q^H + d_q^L) - 1}{k_q} + 1 $$

And so

$$ k_p k_q \cdot n = \left(e \cdot (d_p^H + d_p^L) - 1 + k_p\right) \cdot \left(e \cdot (d_q^H + d_q^L) - 1 + k_q\right) $$

We can obtain a nice approximation of $k_p k_q$ like:

$$ k_p k_q = \left\lceil\frac{\left(e \cdot d_p^H - 1\right) \cdot \left(e \cdot d_q^H - 1\right)}{n}\right\rceil $$

This number $k_p k_q$ is easy to factor. Then, we can consider pairs of numbers $k_p$ and $k_q$ and try to solve for small roots of

$$ P(x) = e \cdot (d_p^H + x) - 1 + k_p \pmod{n} $$

We have $P(d_p^L) = p$, which is what we need, but this is hard to solve since $d_p^L$ is still pretty large compared to $n$.

Tweaking the polynomial

We can narrow the search space with this condition:

$$ \begin{align*} k_p \cdot p = e \cdot (d_p^H + d_p^L) - 1 + k_p & \iff e \cdot (d_p^H + d_p^L) - 1 \mod{k_p} = 0 \\ & \iff d_p^L = e^{-1} - d_p^H \mod{k_p} \\ & \iff d_{k_p} := e^{-1} - d_p^H \mod{k_p} \end{align*} $$

So, we can redefine the polynomial as

$$ P(x) = e \cdot (d_p^H + k_p \cdot x + d_{k_p}) - 1 + k_p \pmod{n} $$

And now $x$ is much smaller, so we are more likely to solve for small roots.

SageMath implementation

First of all, we compute $k_p k_q$ and compute its divisors:

with open('output.txt') as f:
    n = int(f.readline().split(' = ')[1], 16)
    e = int(f.readline().split(' = ')[1], 16)
    c = int(f.readline().split(' = ')[1], 16)
    dp_hint = int(f.readline().split(' = ')[1], 16) << 512  
    dq_hint = int(f.readline().split(' = ')[1], 16) << 512

kp_kq = (e * dp_hint - 1) * (e * dq_hint - 1) // n + 1

divs = divisors(kp_kq)

Since $k_p k_q$ has a lot of divisors, we can consider only the ones that are more likely to produce a 1024-bit number within the size of $d_p^L$ and $d_q^L$:

possible_kp_kq = set()

for div in divs:
    kp, kq = div, kp_kq // div
    pH = (e * (dp_hint + 2 ** 512) - 1 + kp) // kp
    pL = (e * (dp_hint + 0) - 1 + kp) // kp
    qH = (e * (dq_hint + 2 ** 512) - 1 + kq) // kq
    qL = (e * (dq_hint + 0) - 1 + kq) // kq

    if all(int(x).bit_length() == 1024 for x in [pH, pL, qH, qL]):  
        possible_kp_kq.add((kp, kq))

Now, we find the extra value $d_{k_p}$, define the polynomial and attempt to find a small root. If it exists and is not $n$, then we have the expected result and we can compute $p$. Then it is trivial to decrypt the flag with RSA:

x = PolynomialRing(Zmod(n), 'x').gens()[0]

for kp, kq in possible_kp_kq:
    d_kp = int((pow(e, -1, kp) - dp_hint) % kp)
    P = (e * (dp_hint + kp * x + d_kp) - 1 + kp).monic()
    roots = P.small_roots(beta=0.5)

    if roots and roots[0] != n:
        p = int((e * (dp_hint + kp * roots[0] + d_kp) - 1 + kp) // kp)  
        assert n % p == 0
        q = n // p
        d = pow(e, -1, (p - 1) * (q - 1))
        m = pow(c, d, n)
        print(bytes.fromhex(hex(m)[2:]).decode())
        break

Flag

And this is the flag. It references a paper to perform the intended attack, which is based on Coppersmith method too:

$ python3 solve.py
HTB{f4ct0r1ng_w1th_just_4_f3w_b1ts_0f_th3_CRT_3xp0n3nts!https://eprint.iacr.org/2022/271.pdf}

The full script can be found in here: solve.py.