Tags: reverse rsa

Rating: 3.3

**_This is an alternative solution to this task_**

## Reversing

We can reverse the binary and find the important steps it does:

1. It asks for a 60-byte prefix, and uses a prime with that prefix to generate a key for RSA (we don't actually need the details in this solution)
2. It gives you an RSA public key and asks the question "What's the sum of {rand()} and {rand()}?" encrypted by that key.
3. If you get the previous question correct, it gives the flag encrypted by the key.

## The Prefix

The program first generates a 512-bit prime number r, then uses r to generate two primes p and q. The public key is given by N=pq and e=65537. Notice that we can decide the first 480 bits of r, and that the lengths of p and q depend on the length of r -- we can actually control the size of N! If we set the prefix to 0 except the last few digits, N will be small and factorizable.

## The Question

The question is trivial because the program uses srand(time(0)) and rand(): we can solve it by executing srand in the same second as the request.

Note that we cannot decrypt the problem if our goal is to get the flag; the time given is not enough. See the next section to see why.

## The Flag

After answering the question, we will get the encrypted flag. However, if N is too small, it simply gives us an empty string, since the length of N should be $\ge$ the flag's length (with padding). Therefore, we should choose a prefix so that N is larger than the message, but also small enough to be factorizable. Choosing 1<<50 as the prefix gives us a valid N such that $\log_2 N \sim 330$. The N then can be factored (rather easily) and we can decrypt the flag: OOO{Be_A_Flexible_Coppersmith}.