<- CRYPTO

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 = 0x8415befe8ed2f11bc9980dca665d9f011ca1993cac84cbfa19b5b467ad66719eb5dca91f802d3cedd78395b3f94b7f937af8bd0789601b7b68f62e833d1304f2e49058e024a2fc60611017466dcc07c67121604f04d700a15a2e6d2bd146a433b004905c76e543bf1ad3cc26536592bb27081e77c39728535c8d44294dcf28d2199bc1f96ccebe018d12cc8660804f88555887208d4685465ffaa6433e8c0c6bbed3d8ce3f10e1b15962811246292dd9f52728f94a520449db79c9f1cf056d0600dbeb32f6206f9e80ad76570433f4c58fc46c33aa5f1dd7082fdbd2b92981f290d2fca9c135b2cd3d12e794da78f10f8548df11858e2c79af9218e97f09c1a1  
e = 0x447a951fc908492e818cad6d6f0ab1b0212b57f952575e391bec5ad43
c = 0x23e6597702fba920abcbd5502b4102c0d88c9cac2186231444f4f23bf3e721031bb45cff4fa7dc325c9fc6d7fd51a216afa2161478e8e6610c350c9d5568506c8c94d0385cc77565b402db266e73e301473c0aa5149e920b66e3c81391b488812ef42a451d3003d1ba9d18befbdc38adfb5ca8f67a098ffb86e6aaa1230be7bc54fbade19f2f6d273f62ce07d92aa0356b979f108135c8fb33c77bd6b4eb07cce383f82ae3693feb1ebe3370974db1ae05919661558ce637c922caceb295a5c7717f5fdfd353d6b3b05113194fea4573b7a205ae0c2b034997d1bbbf1eee029499d7116b75413558d09a57b74315b45a9f17b2099dd647da1d63ccb5cb92cb2e
dp = 0xc8c6f6c4408d9d34b18948d976313329f4e09e722df217fe8dbd0684dbe52bccdcf4de9e6697d788601d753221886b1bc689e68e9745d1297a39cdd2de9bdcdf
dq = 0x230ba63327b3480c4cf80369f10af726baacf61e631b07178d5aa62dc4b9017b30bf28c5ada9486817d71f0587dd23eea5162ff60880eb0cf7f866c695e1b369

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:

$$ A := 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 not easy to factor. But notice that we can reduce the previous equation $\mod{e}$:

$$ \begin{align} k_p k_q \cdot n \mod{e} & = \left(-1 + k_p\right) \cdot \left(-1 + k_q\right) \mod{e} \\ k_p k_q \cdot n \mod{e} & = k_p k_q - (k_p + k_q) + 1 \mod{e} \\ k_p + k_q \mod{e} & = k_p k_q (1 - n) + 1 \mod{e} \end{align} $$

And therefore,

$$ S := k_p + k_q = A \cdot (1 - n) + 1 \mod{e} $$

So, we can try to find $k_p$ and $k_q$ by solving the following system of equations:

$$ \begin{cases} k_p \cdot k_q & = A \\ k_p + k_q & = S \end{cases} $$

Actually, the exact value of $S$ is $k_p + k_q$ or $k_p + k_q + e$, because both $k_p$ and $k_q$ have a simlar bit size compared to $e$.

Once we have $k_p$ and $k_q$ we can 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_H = int(f.readline().split(' = ')[1], 16) << 512  
    dq_H = int(f.readline().split(' = ')[1], 16) << 512


A = (e * dp_H - 1) * (e * dq_H - 1) // n + 1
S = (A * (1 - n) + 1) % e

Next, we find $k_p$ and $k_q$ by solving a system of equations, trying with $S$ and $S + e$ if no solution is found:

kp_var, kq_var = var('kp, kq')
assume(kp_var, 'integer')
assume(kq_var, 'integer')

possible_kp_kq = []

while True:
    sols = solve([
        kp_var * kq_var == A,
        kp_var + kq_var == S
    ], kp_var, kq_var, algorithm='sympy')  

    if not sols:
        S += e
        continue

    for sol in sols:
        kp, kq = map(int, sol.values())
        possible_kp_kq.append((kp, kq))

    break

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 = (pow(e, -1, kp) - dp_H) % kp
    P = (e * (dp_H + kp * x + d_kp) - 1 + kp).monic()  
    roots = P.small_roots(beta=0.5)

    if roots and roots[0] != n:
        dp_L = kp * roots[0] + d_kp
        p = int((e * (dp_H + dp_L) - 1 + kp) // kp)
        assert n % p == 0 and 1 < p < n
        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:

$ python3 solve.py
HTB{4ny_l34k4g3_0f_pr1v4t3_1nf0rm4t10n_r3su1ts_1n_br0k3n_crypt0}

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