Zukane CTF

import ast

F        = GF(127)
n, v, l  = 48, 120, 6
N        = n + v          # 168
G        = (n+v)//l       # 28 blocks
pow2     = [pow(2,k,127) for k in range(l)]

# read the compressed key
with open("public_key.txt") as f:
    pk_raw = ast.literal_eval(f.read())
C = [[vector(F, col) for col in pk_raw[i]] for i in range(n)]

def sign(target):
    while True:
        # 1) choose a non-zero vector
        s = [F.random_element() for _ in range(G)]
        if all(si == 0 for si in s):
            continue

        rows, rhs = [], []

        # 2) 48 linearised quadratic equations
        for i in range(n):
            coeff = [sum(s[g]*C[i][g][k] for g in range(G))  for k in range(N)]
            rows.append(coeff)
            rhs.append(F(target[i]))

        # 3) 28 block-sum equations
        for g in range(G):
            coeff = [0]*N
            for k in range(l):
                coeff[g*l+k] = pow2[k]
            rows.append(coeff)
            rhs.append(s[g])

        A   = Matrix(F, rows)
        b   = vector(F, rhs)

        x = A.solve_right(b)   
        return list(map(int, x))

# Message to sign
target = [48, 124, 82, 23, 117, 80, 75, 101, 118, 16, 24, 91, 0, 87, 17, 112, 68, 2, 119, 48, 49, 89, 115, 112, 42, 122, 116, 52, 61, 67, 69, 66, 63, 110, 83, 85, 47, 22, 92, 117, 98, 16, 44, 63, 108, 114, 11, 80]

sig = sign(target)
print(sig)