This is my response to a certain telco’s OnePass. I call it “Fourpass” (because it takes *four* inputs instead of *one*).
I don’t think it’ll get accepted because it is so slow though…
Files given:
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 map
computes GCD(f,x)
, then finally the filter and sum counts how many pairs have GCD
To solve this problem efficiently, we can simply implement an efficient algorithm for the function
and then given
This can be done via inclusion-exclusion by counting pairs sharing one prime factor, primes sharing two, etc:
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
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.
Flag:
CTFSG{c_4_c0pR1me_Int3geRs}