This challenge was solved by and the write up was written by one of my teammates, NGG.

If we submitted x such that 0<x<p then the server replied with x^flag % p.

So if we could compute discrete logarithms over GF_p, then we would have been done.

However the best algorithms to compute discrete logarithm in a group requires more than O(sqrt(q)) time where q is the largest prime factor of the order of the base number, which would be too slow if we used a primitive root modulo p, because

2 is a primitive root modulo p, so x = 2^q has order 2*3^336 which is long enough for the flag (which is 50 characters) and only has small prime factors, so we sent that number to the server.

Last weekend I played on the Google CTF 2018 Quals which was one of the best CTFs I played recently. They separated the easy challenges i...… Continue reading