exploit.py

#!/usr/bin/python

# nc crypto.2021.chall.actf.co 21601

from functools import reduce
from Crypto.Util.number import inverse
from pwn import *
from sage.all import *

def f_send(text):
	r.sendlineafter('> ', text)
	r.recvuntil('>> ')
	resp = r.recvuntil('\n')
	return int(resp[:-1])

r = remote("crypto.2021.chall.actf.co", 21601)
max_len = 50

def create_X(n):
	output = []
	for i in range(n):
		output_row = []
		for j in range(n):
			output_row.append(pow(i, j))
		output_row.reverse()
		output.append(output_row)
		
	return Matrix(output)


print ('[*] Getting Y space')
Y = []
for i in range(max_len):
	Y.append(f_send(str(i)))
Y = vector(Y)
	
print ('[*] Bruteforce on flag length')
for i in range(7, max_len):
	print ('\t| Flag length: {0}'.format(i))
	
	X = create_X(i)
	ans = (X.solve_right(Y[:i])) % 691
	
	flag = ''
	for c in ans:
		flag += chr(c)

	if ('actf{' in flag):
		print ('[+] Flag: {0}'.format(flag))
		break