## problem

shares = 9 / threshold = 5 のShamir秘密共有した結果から4個だけ与えられるので割れ

## solution

There is a polynomial $f_k(x) = a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + k$ on $GF(2^8)$. For each char $k$ of the flag, random $8$ points $x_0, x_1, \dots, x_7$ are chosen, and values $f(x_0), f(x_1), \dots, f(x_7)$ are computed. Then, $4$ of them, $f(x_0), f(x_1), \dots, f(x_3)$ is given.

Therefore, these polynomials are the same up to constants. If you can guess the flag is like midnight{???????????????????}, there is enough information ($4 \times 10$ points) to fix $a_4, \dots, a_1$, with the gaussian elimination.

## implementation

# Python Version: 3.x
import os
import json
import base64

FLAG = 'midnight{???????????????????}'
from point import Point
numshares = 9
threshold = 5

with open('shares.txt') as fh:
shares = []
for line in fh:
assert len(shares) == threshold - 1 == 4

def point_pow(x, n):
y = Point(1)
while n:
y *= Point(x)
n -= 1
return y

def point_negate(x):
return x

def gaussian_elimination(f, v):
n = len(v)
for y in range(n):
pivot = y
while pivot < n and not f[pivot][y].value:
pivot += 1
assert pivot < n
f[y], f[pivot] = f[pivot], f[y]
v[y].__idiv__(f[y][y])
for x in range(y + 1, n):
f[y][x].__idiv__(f[y][y])
f[y][y] = Point(1)
for ny in range(n):
if ny != y:
v[ny] += point_negate(f[ny][y] * v[y])
for x in range(y + 1, n):
f[ny][x] += point_negate(f[ny][y] * f[y][x])
f[ny][y] = Point(0)

def apply_poly(coeffs, coord):
B = Point(1)
S = Point(0)
X = Point(coord)
for coeff in coeffs:
S += (B * Point(coeff))
B *= X
return S.value

graph = []
for i, char in enumerate(FLAG):
if char == '?':
continue
for j in range(4):
x = base64.b64decode(shares[j]['split'])[i]
y = base64.b64decode(shares[j]['split'])[i]
graph += [ ( x, y ^ ord(char)) ]

matrix = []
vector = []
for x, y in graph[: 4]:
matrix += [ [ point_pow(x, 1), point_pow(x, 2), point_pow(x, 3), point_pow(x, 4) ] ]
vector += [ Point(y) ]
gaussian_elimination(matrix, vector)
base_poly = [ x.value for x in vector ]

flag = ''
for i, char in enumerate(FLAG):
j = 0
x = base64.b64decode(shares[j]['split'])[i]
y = base64.b64decode(shares[j]['split'])[i]
c = chr(apply_poly([ 0 ] + base_poly, x) ^ y)
if char != '?':
assert c == char
print(i, ':', c)
flag += c
print(flag)