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 , , such that

where is the flag. Curiously, is a 227-bit prime number ().

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

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

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

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

So, we have:

And so

We can obtain a nice approximation of like:

This number is not easy to factor. But notice that we can reduce the previous equation :

And therefore,

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

Actually, the exact value of is or , because both and have a simlar bit size compared to .

Once we have and we can try to solve for small roots of

We have , which is what we need, but this is hard to solve since is still pretty large compared to .

Tweaking the polynomial

We can narrow the search space with this condition:

So, we can redefine the polynomial as

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

SageMath implementation

First of all, we compute 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 and by solving a system of equations, trying with and 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 , define the polynomial and attempt to find a small root. If it exists and is not , then we have the expected result and we can compute . 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.