Crypto mecha gnomes love random polynomial functions, can you guess what’s hidden in there? Server: nc 220.127.116.11 16000
When connected to the server it reply with a welcome message:
Hello to the most amazing Christmas event. The X^n-Mas! You can send at most 50 requests to the server. The modulo is 1705110751. Good luck!
Then we can ask to the server to compute for some
x the value
f(x), for example:
Enter a integer:0 The output is: 125
Enter a integer:1 The output is: 3458
Enter a integer:2 The output is: 26558034
All the numbers written are modulo
1705110751 and the inserted integer should be in the range
Fortunately we see that if reconnect to the server all the values, including the modulo, remain the same, so the limit of 50 requests is only fictitious, as we can reopen the connection and ask the value for more
Now let’s start to do some math!
The random polynomial function is in the form:
f(x) = c_0*x^0 + c_1*x^1 + c_2*x^2 + ... + c_d*x^d (mod 1705110751)
For some degree
d and we want to retrieve all the values of
Now we have that :
f(x) = c_0
f(1) = c_0 + c_1 + c_2 + ... + c_d.
f(2) = c_0 + 2^1*c_1 + 2^2*c_2 + ... + 2^d*c_d.
c_0 is equal to
125 the ASCII-code of
}, so we are in the right path!)
We can create the matrix
d X d called
M = [M_1, M_2, M_3, ..., M_d] where:
M_i = [i^0, i^1, i^2, i^3, ..., i^d]
and create the vector
b = [f(1), f(2), f(3), ..., f(d)] with the asked values to the server.
To retrieve all the coefficients we have to solve the system
M * c = b, so it’s enough to invert
M and multiply it by
c = M^-1 * b).
Using the sagemath library for python we found that the coefficients are:
(125, 115, 97, 109, 116, 115, 105, 114, 104, 67, 95, 121, 114, 114, 51, 109, 95, 52, 95, 117, 111, 121, 95, 104, 115, 49, 119, 95, 51, 87, 123, 83, 65, 77, 45, 88, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
The function has degree 36, and after converting all the coefficients to their ASCII values we finally recover the flag!
The flag is
#!/bin/env python2.7 from pwn import * from sage.all import * import gmpy r = None MAX_QUERY = 50 qc = 0 def query(num): global qc global r if qc % MAX_QUERY == 0: r = remote("18.104.22.168", 16000) l1 = r.recvline() l2 = r.recvline() l3 = r.recvline() qc += 1 r.recvuntil("Enter a integer:") r.sendline(str(num)) r.recvuntil("he output is: ") return int(r.recvline().strip()) modulo = 1705110751 lun = 50 M =  # Create the matrix M for i in range(1, lun+1): p = [pow(i, x, modulo) for x in range(0, lun)] p.append(query(i)) M.append(p) # Separate M' = [ M | b ] n1 = len(M)-1 M = M[0:n1] b = [t[n1] for t in M] M = [t[0:n1] for t in M] # Invert the matrix M inv = Matrix(IntegerModRing(modulo), M).inverse() # Solve the linear system sol = inv*vector(b) # Convert coefficient to ascii sol = "".join([chr(o) for o in sol][::-1]) print(sol)