RRSSAA

2 minutes to read

My primes are prefectly random. I wonder if you can find them.
Challenge contributed by CryptoHack
Challenge files:
output.txt
RRSSAA.py

Source code analysis

We are given the following Python script that uses RSA to encrypt the flag:

flag = open("flag.txt", "rb").read().strip()
assert len(flag) == 128
N = prod(get_prime(i) for i in range(2, len(flag)))
print(hex(N), hex(pow(bytes_to_long(flag), 0x10001, N)))

The RSA setup is not the usual one. This time, we have a multi-prime RSA setup, where each prime factor of the modulus is computed with get_prime:

def get_prime(n):
    p = 1
    r = random.Random()
    r.seed(randbelow(2**n))
    while not isPrime(p):
        p = r._randbelow(2**256) | 1
    return p

The modulus has a total of 256-bit prime factors, so it is not easy to factor.

Solution

Notice that is computed as N = prod(get_prime(i) for i in range(2, len(flag))), so the first prime factors are easy to obtain by brute force, because we can brute force the seed for random.seed and compute p = r._randbelow(2**256) | 1 until we have a prime number.

In a bit of time, we can get around 16 prime factors of , which is what we need to find the flag.

Since multi-prime RSA is used, we can decrypt the flag using RSA-CRT. This is just finding , then computing and finally use the CRT to recover .

This works because is huge, so having a bunch of factors is enough to decrypt the message. Actually, the output of the CRT is for some . We are not able to factor in its factors, but is nice since the CRT modulus is bigger than the message as an integer ( flag bits and CRT modulus bits).

Flag

We can write down the above procedure in a Python script and find the flag:

$ python3 solve.py
ECSC{brute_it_like_bruce_49a22a7465edcdeab5b01ffcd325110382c6f93f4d1d898be0569e5f97efe557574b28c83b6209a509dbfea1c45f06c5518928}

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