[2018 X-MAS CTF] Xⁿ-Mas

정말 이게 다입니다. 매 실행마다 값이 달라지지 않는다는 점으로 보아, polynomial의 계수를 구하고 나면 그게 왠지 flag일 것 같다는 킹리적 갓심을 할 수 있습니다. 또 최대 50번의 질의를 하라는 점에서 뭔가 49차 다항식일 것 같습니다. 그러면 그냥 행렬을 만들어서 풀이를 하면 됩니다. 한 20개만 되었어도 그냥 직접 손으로 복붙한 다음 sage에서 계산했을텐데 50개여서 간단하게 파이썬 코드를 작성했습니다.

이 이후로는 sage에서 처리를 해주면 됩니다.

sz = 50
mod = 4109151247
A = Matrix(IntegerModRing(mod), sz)
for i in range(sz):
    for j in range(sz):
        A[i,j] = pow(i+1,j,mod)

b = vector(IntegerModRing(4109151247), [3458, 1785121792, 2993914695, 2262842519, 3514980949, 731612334, 1039513180, 1221307243, 175536861, 1093492218, 3642227580, 1499052940, 2622275053, 759450776, 210206349, 580100870, 784949049, 1766215172, 2416413541, 417239776, 916812787, 2727649683, 1041277215, 1745232362, 64716067, 1531284352, 3522292020, 2441861395, 1267143724, 4107819393, 3088353815, 3508812480, 3505134902, 2375686921, 3499089797, 1903361805, 3552501983, 436672127, 2359513422, 2253398298,
2081166476, 983350284, 108427053, 2768067791, 96823767, 3681543950, 2375023029, 4094918538, 1751121821, 297027069])
ans = A.solve_right(b)
flag = ''
for i in ans:
    flag += chr(i)
print flag[::-1]