solve_substitution.sage

from sock import Sock
from sage.all import *

so = Sock('crypto.2021.chall.actf.co:21601')
res = []
for i in range(100):
    so.read_until(b"> ")
    so.send_line(str(i))
    res.append((i, int(so.read_line()[3:-1])))
for n in range(10, 100):
    mat = []
    right = []
    for i in range(n):
        value, v = res[i]
        row = [pow(value, i, 691) for i in range(n)]
        mat.append(row)
        right.append(v)
    A = matrix(GF(691), mat)
    B = vector(GF(691), right)

    try:
        C = A.inverse() * B
        print("".join(chr(i) for i in list(C))[::-1])
    except:
        pass