Private Keys

Reading the source file we understand that the private_key and the public_key are one of the prime numbers generated by valid_primes_sieve(). They are also greater than (d+1)*max_input = 11 * 255.

We can compute the list of all the valid private keys.
Because private_key and public_key are different, we only need to try 29.

For python source code and detailed explaination see the original writeup https://theromanxpl0it.github.io/ctf_codefest17/russia/

Original writeup (https://theromanxpl0it.github.io/ctf_codefest17/russia/).