# The challenge
Note that the intended solution for this problem was much simpler and intuitive. I somehow missed that obsevration during the contest and opted for a meet in the middle solution instead
Before I go to my solution, I would explain some approaches that I tried and why they failed. This is the code that we were provided with```python
#!/usr/local/bin/pythonimport random
with open('flag.txt', 'r') as f:	FLAG = f.read()
assert all(c.isascii() and c.isprintable() for c in FLAG), 'Malformed flag'N = len(FLAG)assert N <= 18, 'I\'m too lazy to store a flag that long.'p = Nonea = NoneM = (1 << 127) - 1
def query1(s):	if len(s) > 100:		return 'I\'m too lazy to read a query that long.'	x = s.split()	if len(x) > 10:		return 'I\'m too lazy to process that many inputs.'	if any(not x_i.isdecimal() for x_i in x):		return 'I\'m too lazy to decipher strange inputs.'	x = (int(x_i) for x_i in x)	global p, a	p = random.sample(range(N), k=N)	a = [ord(FLAG[p[i]]) for i in range(N)]	res = ''	for x_i in x:		res += f'{sum(a[j] * x_i ** j for j in range(N)) % M}\n'	return res
query1('0')
def query2(s):	if len(s) > 100:		return 'I\'m too lazy to read a query that long.'	x = s.split()	if any(not x_i.isdecimal() for x_i in x):		return 'I\'m too lazy to decipher strange inputs.'	x = [int(x_i) for x_i in x]	while len(x) < N:		x.append(0)	z = 1	for i in range(N):		z *= not x[i] - a[i]	return ' '.join(str(p_i * z) for p_i in p)
while True:	try:		choice = int(input(": "))		assert 1 <= choice <= 2		match choice:			case 1:				print(query1(input("\t> ")))			case 2:				print(query2(input("\t> ")))	except Exception as e:		print("Bad input, exiting", e)		break```# Some failed approaches
This is a classic interpolation problem(almost). The 18 characters of the flag ($a_0, a_1, a_2, .., a_{16}, a_{17}$) are used as coefficients of a 17 degree polynomial like this:$$a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + ... + a_{16}x^{16} + a_{17}x^{17} $$All too simple, if we could just get values at 18 points. But there is a catch, we can get values at maximum of 10 points from each ```query1```. That too would not have been a problem, we could have just obtained the remaining 8 points from a second call to ```query1```. What makes this approach infeasible, is that everytime we call ```query1```, the co-efficiets are randomlyshifted and so we get a different polynomial each time.
I wrote a script for ```query1('0')``` to check what are the characters of my flag. ```quer1('0')``` means the $a_0$ of the polynomial, which gives us the first character of the permutation. Running it a few hundred times ensures that all the constituent characters witll be spit out. Here is the script :
```pythonfrom pwn import *from tqdm import tqdm
io = remote('challs.actf.co', 32100)
def query(io, to_send):    io.recvuntil(b':')    io.sendline(b'1')    io.recvuntil(b'>')    io.sendline(to_send)    m = int(io.recvline().strip())    return m
so_far = set()for _ in tqdm(range(100)):    try:        r = query(io, '0'.encode())        so_far.add(r)    except:        io = remote('challs.actf.co', 32100)
print(so_far)```The ouput was ```{'8', 'b', 't', '}', '7', '{', 'f', 'c', '6', 'a', '0'}```
Not much, just 11 unique characters. Using them, I tried to write a partial burte force using ```z3```. Since I can have 10 equations, I bruteforced for the 8 remaining characters. Later I tried a similar approach using matrices. Brute-forcing for the 8 remaining characters, I formed a ```10 by 10``` matrix and solving it under GF(M). But both the approaches were too slow and hence, not feasible.
# The working approach
Notice that I can somewhat reduce the search space  using ```query1('x')``` and ```query1('-x')``` where `x` is an integer. $$f(x)  = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + ... + a_{16}x^{16} + a_{17}x^{17} $$$$f(-x) = a_0 - a_1x + a_2x^2 - a_3x^3 + a_4x^4 + ... + a_{16}x^{16} - a_{17}x^{17} $$
Adding them cancels out the indices with odd powers:
$$f(x) + f(-x) = 2a_0 + 2a_2x^2 + 2a_4x^4 + 2a_6x^6 + ... + 2a_{14}x^{14} + 2a_{16}x^{16}$$
Allthough we can't directly query for ```query1('-x')```, we can do ```M - x``` instead, since $$M \ - \ x \ \equiv \ -x \ mod \ M$$
But how does this help us? Not that we can brute force all combinations, it's $O(n^9)$ which is too costly.Instead, we can divide it into two parts, $$g_1(x) \ = \ a_0 + a_2x^2 + a_4x^4 + a_6x^6 + a_8x^8$$ $$g_2(x) \ = \ a_{10}x^{10} + a_{12}x^{12} + a_{14}x^{14} + a_{16}x^{16} $$
We now brute force all combinations of ```g1(p)``` where the ```p``` is fixed(supposedly a prime) and ($a_0, a_2, a_4, a_6, a_8$) are chosen from the flag characters which we got initially. The values are stored in a dictionary where ```g1(p)``` is the key and the combination of co-efficients is the value.
```pythonimport itertools
opt = ['8', 'b', 't', '}', '7', '{', 'f', 'c', '6', 'a', '0']opts = [ord(c) for c in opt]perms5 = list(itertools.product(opts, repeat = 5)) # all permuations and combinatons of length 5perms4 = list(itertools.product(opts, repeat = 5)) # all permuations and combinatons of length 4, will be used later
M = (1 << 127) - 1d1 = dict()p1 = 23for perm in tqdm(perms5):    pwL = [0, 2, 4, 6, 8]    sm = sum([perm[i] * (p1 ** pwL[i]) for i in range(5)])    d1[sm] = perm```
The complexity for this part is $O(n^5)$ which is affordable.
Let's say $$z \ = \ g_1(p) \ + \ g_2(p)$$Since we have all permuations for $g_1$, we can write the above equation as $$g_1(p) \ = \ z \ - \ g_2(p)$$
Now we brute force all permuations and combinations of length 4 and find different values of $g_2(p)$ For each value of $g_2(p)$, we check if $z \ - \ g_2(p)$ is in dictionary ```d1```. If yes, we have found the proper combinations of co-efficients for $a_0, a_2, a_4, ...., a_{14}, a_{16}$ 
```pythonRHS = [r1, r2] # r1 = query1(p) r2 = query1(M - p)
p1_sm = (RHS[0] + RHS[1]) % Mp1_sm = (pow(2, -1, M) * p1_sm) % Meven_pow = Nonefor perm in tqdm(perms4):    pwR = [10, 12, 14, 16]    sm = sum([perm[i] * (p1 ** pwR[i]) for i in range(4)])    need = (p1_sm - sm + M) % M    if need in d1:        even_pow = d1[need] + perm        break```
How much time does it take? The brute forcing take $O(n^4)$ and the search to see if a values belongs in the dictionary takes $O(\log{} n)$. In total it is $O(n^4 \log{} n)$ which is way faster than $O(n^9)$
The exact same approach is repeated to recover the odd indexed co-efficients$$a_{1}x + a_{3}x^3 + a_{5}x^5 + a_{7}x^7 + ... + a_{15}x^{15} + a_{17}x^{17}$$ 
After all the co-efficients are recovered, we send them to ```query2``` in order to get the permuations revealed. Using that, we can rearrange the co-efficients and hence, recover the flag.
```pythonflag = [0 for _ in range(len(coeffs))]for idx, val in enumerate(perms):    flag[val] = coeffs[idx]
flag = ''.join([chr(c) for c in flag])print(flag)```
```FLAG : actf{f80f6086a77b}```
