Personalized

3 minutes to read

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

#!/usr/bin/env python3

from Crypto.Util.number import *
from random import seed, getrandbits

m = bytes_to_long(open('flag.txt', 'rb').read())
print("What's your name?\n>>> ", end='')
name = open(0, 'rb').readline().strip()
seed(bytes_to_long(name))
e = 2*getrandbits(32)+1
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, e, n)
print(f"Here's your flag, {''.join(chr(i) for i in name)}!")
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')

It uses a RSA implementation where we can provide a name that will be used as the seed for a Pseudo-Random Number Generator (PRNG). And then the public exponent is computed as 2 * getrandbits(32) + 1.

Each time we connect to the server, the public modulus will be different, but as long as we use the same name, the exponent will be the same. Hence, we will get this system of congruences:

According to the Chinese Remainder Theorem (CRT), this system of congruences will have a unique solution modulo as long as all are coprime with each other (which is satisfied). With enough equations, we will have that , and the solution of the CRT will be precisely .

Then, the next step will be to do the -th root and get .

To make this strategy work, we need to find an exponent that is short enough, so that we don’t need to get so many messages.

One approach is to use brute force. We will find out that using 8115501 ("{\xd5-" as bytes) as a seed will result in , which is short enough.

For the CRT, I requested 1000 pairs of ciphertext and modulus. Maybe it is a lot, but it will make sure that the CRT works (imported from SageMath into Python).

This is the final Python script:

#!/usr/bin/env python3

from gmpy2 import iroot
from pwn import context, log, remote, sys
from random import getrandbits, seed
from sage.all import CRT


def main():
    if len(sys.argv) != 3:
        log.warning(f'Usage: python3 {sys.argv[0]} <host> <port>')
        exit(1)

    host, port = sys.argv[1], sys.argv[2]

    seeds = log.progress('Seed')

    for i in range(10000000):
        seeds.status(str(i))
        seed(i)

        if getrandbits(32) < 50:
            nice_seed = i
            break

    if nice_seed is None:
        log.warning('Could not find nice seed')
        exit(1)

    seeds.success(str(nice_seed))

    name = bytes.fromhex(hex(nice_seed)[2:])
    seed(nice_seed)
    e = 2 * getrandbits(32) + 1

    log.info(f'{e = }')

    ns, cs = [], []

    connections = log.progress('Connections')

    for i in range(1000):
        connections.status(str(i + 1))

        with context.local(log_level='CRITICAL'):
            r = remote(host, int(port))
            r.sendlineafter(b'>>> ', name)

            r.recvuntil(b'n = ')
            ns.append(int(r.recvline().strip().decode()))
            r.recvuntil(b'c = ')
            cs.append(int(r.recvline().strip().decode()))
            r.close()

    connections.success(str(i))

    m_e = CRT(cs, ns)
    m = iroot(m_e, e)

    log.success(f'Flag: {bytes.fromhex(hex(m[0])[2:]).decode()}')


if __name__ == '__main__':
    main()

And we obtain the flag:

$ python3 solve.py puzzler7.imaginaryctf.org 4002
[+] Seed: 8115501
[*] e = 73
[+] Connections: 1000
[+] Flag: ictf{just_f0r_y0uuuuuuuu}

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