Tags: polynomial crypto

Rating:

## Solution

Since there are at most 50 requests, it is a reasonable assumption that the degree of the polynomial is at most 49.

But to illustrate the solution, let us say we only have a quadratic polynomial


f(x) = a + bx + cx^2


The if we evaluate f(x1) we get,


f(x1) = a + b*(x1) + c*(x1^2)


We can evaluate f(.) several times to get a system of linear equations, and solve for the coefficients.


f(0) = 2
f(1) = 39
f(2) = 99

then


2 = a + 0b + 0c
39 = a + 39b + 1521c
99 = a + 99b + 9802c


This can be solved this using gaussian elimination, and we extend this to polynomial degree 49, and the coefficients of the polynomial represent the flag

__For full implementation see the url__

Original writeup (https://github.com/pberba/ctf-solutions/tree/master/20181223_xmasctf/crypto-383-xn_mas).