Fourpass

First we need to understand what the token does. Throwing it into a python beautifier, we get

#!/usr/bin/python3.8
a, b, c, d = list(map(int, input().split()))
print(
    sum(
        filter(
            lambda x: x == 1,
            map(
                lambda x: (
                    lambda f: (lambda x: x(x))(lambda x: f(lambda *y: x(x)(*y)))
                )(lambda f: lambda x, y: x if not y else f(y, x % y))(*x),
                [(f, x) for f in range(a, b) for x in range(c, d)],
            ),
        )
    )
)

Notice that (lambda f:(...)) implements the Y combinator and it’s input is essentially the GCD algorithm. This tells us that lambda x:() implements GCD which can easily be verified in python.

Next, the array loops over all \(a\leq f<b,c\leq x<d\) and then map computes GCD(f,x), then finally the filter and sum counts how many pairs have GCD \(1\), i.e. coprime pairs. Hence we need to write an efficient algorithm to count the number of coprime pairs within a fixed range.

To solve this problem efficiently, we can simply implement an efficient algorithm for the function

and then given \(a,b,c,d\), we can compute \(f(b,d)-f(a,d)-f(b,c)+f(a,c)\) and send to the server.

This can be done via inclusion-exclusion by counting pairs sharing one prime factor, primes sharing two, etc:

\[f(A,B)=AB-\sum_{p_i}\left\lfloor\frac A{p_i}\right\rfloor\left\lfloor\frac B{p_i}\right\rfloor+\sum_{p_i\neq p_j}\left\lfloor\frac A{p_ip_j}\right\rfloor\left\lfloor\frac B{p_ip_j}\right\rfloor+\dots\]

To make this efficient, we can precompute all the products up to a certain bound using a slightly modified Eratosthenes sieve:

for(i=2;i<MAX;++i){
    if(sieve[i] == -1)continue;
    if(sieve[i] == 0){
        for(j=2;i*j<MAX;++j){
            if(j%i==0)sieve[j*i]=-1;
            else{
                if(sieve[j*i]!=-1)sieve[j*i]++;
            }
        }
        sieve[i] = 1;
    }
}

Here the final result in sieve[i] would be the number of prime factors that i has, and -1 if i has a repeated factor.

Using this, we can compute \(f\) pretty quickly, fast enough for the server to accept, giving us the flag:

Correct OTP. Have your flag: CTFSG{c_4_c0pR1me_Int3geRs}

We can optimize the solution a bit further by computing the output directly instead of having to call f four times, but this turns out to be fast enough.

The C script can be found at solver.c and to hook up to the server, I’ve written a quick pwntools script at solve.py.

FourPass