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 , , 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 easy to factor. Then, we can consider pairs of numbers and and 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_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 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 and :

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 , 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 = 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.