super-tomato

Gluttony pink needs the tomato...

We are given the challenge page, the server.py source code and a netcat service.

When we read the server.py file we can see that the server generates a random prime p and another random prime a. The flag is printed only if pow(a, choice, p) == 1.

p = getPrime(2048)
a = getPrime(1024)

if pow(a, choice, p) == 1:
    print(f"here is the flag: {flag}")

This means we need an exponent that makes a^choice mod p equal to 1.

Because p is prime, we can use Fermat's Little Theorem. If a is not divisible by p, then a^(p-1) = 1 (mod p).

So the solution is very simple: we take the given tomato number and subtract 1 from it. Then we send that new value to the server.

choice = p - 1

After sending p - 1, the condition becomes true and the server gives us the flag.

Alpaca{Fully_restores_HP!!}