Similiar to the setup of RSA is easy #1 and RSA is easy #2.
This time, encryption is done on the plaintext as a whole and not for every byte separately,

In addition we get the public key, the encrypted flag and remote access to a key-generation server. The key-generation server is starting from a specific snapshot every time you connect to it.
Furthermore, the challenge description states that no more than 10k messages have been sent between the flag encryption and the time of the snapshot.
All of these, in addition to the name of the challenge, suggests that the goal is to somehow break the key-generation algorithm and obtain the key for the flag.

Accessing the key-generation server, we can generate new public/private RSA key pairs.
In RSA terminology, we get: ((e, n), (d, n)) where (e, n) is the public key (e is always 65537), and (d, n) is the private key.
After generating a few key pairs, we can’t notice any visible connection that can help us guess older keys.
However, we know that RSA starts by picking two large prime numbers p, q and maybe the process of picking p and q is predictable. As it turns out, given the public and private RSA keys, one can deduce p and q. Ways to do this can be found easily online.

Looking at p and q of different generated keys, we quickly notice that either p or q is monotonically increasing. That is, starting from some q_0, the next q, namely q_1, will be the next prime after q_0.
In order to find the (p,q) that were used to encrypt the flag, we can start from the q extracted from the RSA key returned from the server and guess our way down to the prime number q* that suffices:

n % q* == 0

Where n is taken from the provided public key for the flag.

Once we find q*, we find p* by calculating n/q* and decryption of the flag easily follows.