# Poly Playground
### Challenge Details
> Author: jloh02 \
Category: Misc \
Title: Poly Playground \
Description: Magicians love to create things out of thin air. This time our secret wizards have created a playground. Test out your wizardry here! \
Points at the end of CTF: 100 \
Instance: `nc challs.nusgreyhats.org 31113` \
Download: -
----
### Writeup
When we connect to the ip and port, we are greeted with this message:

And we are presented with our first problem:

Here's your first problem...
--------------------
Level 1:
Roots: -732
Present the coefficients of your amazing equation:

What it's asking for here is for the coefficients of a polynomial which has a root of `-732`.
For example, the polynomial $x^2+2x-8$ has roots $2$ and $-4$ because they are solutions of the equation \
$x^2+2x-8 = 0$ \
As seen with, \
$(2)^2+2(2)-8 = 0$ \
and \
$(-4)^2+2(-4)-8 = 0$

Meaning, if $p(x) = 0$, $x$ is a root of the polynomial

But how can we get polynomials from roots?
Let $p(x)$ be our desired polynomial

Suppose we divide $p(x)$ by some linear polynomial $(x - a)$.

$p(x) = (x - a)q(x) + r(x)$ \
Where $q(x)$ is the quotient polynomial and $r(x)$ is the remainder.

Substitute $x = a$. We get: \
$p(a) = (a - a)q(x) + r(x)$ \
$p(a) = r(x)$. \
Hence, the remainder of $p(x)$ when divided by $(x - a)$ is equal to $p(a)$

Meaning that if $(x - a)$ is a factor of $p(x)$, $p(a) = 0$ \
Recall that if $p(x) = 0$, then $x$ is a root of $p(x)$.

Thus, if $r$ is a root of $p(x)$, \
$p(x) = 0$ \
$p(r) = 0$ \
$(x - r)$ is a factor of $p(x)$

Hence, with a list of roots $[r_1, r_2, ... r_n]$, we can conclude that: \
$p(x) = (x - r_1)(x - r_2)...(x - r_n)$

if none of that made sense, it's probably cause i didn't explain it well LOL.

Back to our task, what we have to do is find the product of $(x - r_1), (x - r_2), ..., (x - r_n)$ for all the given roots.
Luckily, there's a very cool tool for that from the `numpy` library.

Here's my function for generating polynomials from roots:

from numpy.polynomial import polynomial as P

def roots_to_polynomial(roots: list) -> list:
  polynomial = P.polyfromroots(roots)
  int_str = lambda x: str(int(x))
  return ', '.join(map(int_str, polynomial[::-1]))

Numpy by default returns the coefficients ordered lowest power to highest, but we want it in descending powers so we reverse the list with `polynomial[::-1]`. It also returns them as a list of floats, but we want them to be a list of integers, so I defined a lambda function `int_str` to convert floats into string integers.

You can use the `pwn` library to interact with the ip and port like how you would by netcatting it, but programmatically to send and receive data.

from pwn import *
conn = remote('challs.nusgreyhats.org',31113)
conn.recvuntil(b"Here's your first problem...")
while True:
  try:
    print(conn.recvuntil(b"Roots: ").decode()) 
    roots = list(map(int, conn.recvline().decode().strip().split(',')))
    print(roots)
    out = roots_to_polynomial(roots)
    out = (out + '\n').encode()
    print(conn.recvuntil(b"Present the coefficients of your amazing equation: ").decode())
    print(out)
    conn.send(out)
  except EOFError:
    break

After 100 levels, we finally get:

Flag: `grey{l0oks_lik3_sOm3one_c4n_b3_a_po1ynomia1_w1z4rd}`

### Comments
I sincerely apologize to the math nerds if my math is incorrect, i wrote this at 3am lol.