For this challenge we’re only given a netcat connection and the following description:

Crypto mecha gnomes love random polynomial functions, can you guess what’s hidden in there?

Solution

Connecting to netcat we’re given a modulus and the possibility to evaluate a polynomial at 50 points. The first thing that comes in mind is interpolation: we can retrieve the whole polynomial if the degree is at most 49 (spoiler: it is). In order to do this we use Lagrange’s interpolation method, that basically is: given , then the interpolation polynomial in Lagrange’s form is

Basically all works also with polynomials in the ring. Fortunately, we found out that one of the organizers (Gabies) has, on his github page, a class to work with polynomials in , so using his code we can do the following script to obtain the flag:

for i in range(len(self.coeffs)): q=Polynomial(p.coeffs) q.raise_degree(i) q.multiply(self.coeffs[i]) coeffs.add_poly(q) self.coeffs=coeffs.coeffs

defcalculate_derivative(self): p=Polynomial([]) for i in range(1,len(self.coeffs)): p.coeffs.append((self.coeffs[i]*i)%MOD) return p

defcompose(self,p): P=Polynomial([]) q=Polynomial([1]) for i in range(len(self.coeffs)): q2=Polynomial(q.coeffs) q2.multiply(self.coeffs[i]) P.add_poly(q2) q.multiply_with_poly(p) self.coeffs=P.coeffs

defprint_poly(self): return self.coeffs

#Lagrange Interpolation part defLagrange_Basis_Polynomial(xlist,index): l=Polynomial([1]) for i in range(len(xlist)): if(i==index): continue p=Polynomial([(MOD-xlist[i])%MOD,1]) p.multiply(inverse((MOD+xlist[index]-xlist[i])%MOD,MOD)) l.multiply_with_poly(p) return l

defLagrange_Polynomial(xylist): xlist=[] ylist=[] L=Polynomial([]) for a in xylist: xlist.append(a[0]) ylist.append(a[1]) for i in range(len(ylist)): l=Lagrange_Basis_Polynomial(xlist,i) l.multiply(ylist[i]) L.add_poly(l) return L

r = remote("199.247.6.180", 16000) r.recvuntil("modulo is ") n = int(r.recvline().decode().split(".")[0]) print(n) MOD = n for i in range(50): r.recvuntil(":") r.sendline(str(i)) t = int(r.recvline().decode().split(":")[1].rstrip("\n").lstrip(" ")) print((i,t)) xy.append((i,t)) print(xy) coeffs = Lagrange_Polynomial(xy).print_poly() print(coeffs) c = "" for i in range(len(coeffs)): print(chr(coeffs[49-i]), end="")