idk ctf hssp challenge

solve.sage

from sage.all import *
from Crypto.Util.number import *
from os import urandom
from cpmpy import *
from lll_cvp import flatter

flag = b"flag{test_flag}"


def pad(msg, length):
    return msg + urandom(length - len(msg))


n = 10
p = getPrime(256)
A = Matrix(Zmod(p), n, n, pad(flag, n**2))
PR = PolynomialRing(Zmod(p), "x")
f = PR.random_element(degree=n)
f -= f.constant_coefficient()
B = f(A)

# B = f0*I + f1*A + f2*A^2 + ... + f10*A^10
# flat(B) = f0*flat(I) + f1*flat(A) + f2*flat(A^2) + ... + f10*flat(A^10)
# B^2 = f0^2*I + f0*f1*A + ...
# flat(B^2) = f0^2*flat(I) + f0*f1*flat(A) + ...

def find_ortho(mod=None, *vecs):
    assert len(set(len(v) for v in vecs)) == 1, "vectors have different lengths"
    base = [[matrix(vecs).T, matrix.identity(len(vecs[0]))]]
    if mod is not None:
        base += [[ZZ(mod), 0]]
    L = block_matrix(ZZ, base)
    nv = len(vecs)
    L[:, :nv] *= mod if mod is not None else 2**1024
    L = flatter(L)
    ret = []
    for row in L:
        if row[:nv] == 0:
            ret.append(row[nv:])
    return matrix(ret)


ortho = find_ortho(p, vector(B.list()), vector((B**2).list()))
print([o * vector(A.list()) for o in ortho])
print(ortho[0])
ortho2 = find_ortho(None, *ortho[: n * (n - 1)])
print(ortho2.solve_left(vector(A.list())))
tgt = cpm_array(list(intvar(-256, 256, 2))) @ ortho2[:2]


def check():
    flag = bytes(tgt.value().tolist())
    if flag.startswith(b"flag{"):
        print(flag)


Model([0 <= tgt, tgt < 256]).solveAll(display=check)

task.sage

from Crypto.Util.number import *
from os import urandom
from secret import flag

def pad(msg, length):
    return msg + urandom(length - len(msg))

n = 10
p = getPrime(256)
A = Matrix(Zmod(p), n, n, pad(flag,n^2))
PR.<x> = PolynomialRing(Zmod(p))
B = PR.random_element(degree=n)(A)

print("p =", p)
print("B =", B.list())