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 $n$ 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 $n$ has a total of $128$ 256-bit prime factors, so it is not easy to factor.

Solution

Notice that $n$ 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 $n$, 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 $d_i = e^{-1} \mod{p_i - 1}$, then computing $m_i = c^{d_i} \mod{p_i}$ and finally use the CRT to recover $m$.

This works because $n$ is huge, so having a bunch of factors is enough to decrypt the message. Actually, the output of the CRT is $m \mod{p_1 \cdot p_2 \cdots p_k}$ for some $k$. We are not able to factor $n$ in its $128$ factors, but $k = 5$ is nice since the CRT modulus is bigger than the message $m$ as an integer ($128 * 8 = 1024$ flag bits and $256 * 5 = 1280$ 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.