ACERGION

>Frivolousuov

This challenge implements an UOV (Unbalanced Oil and Vinegar) signature scheme over GF(2^8) but uses a deterministic procedure to choose the vinegar variables from the message. That deterministic vinegar collapses the intended hardness: from the public quadratic forms you can recover the linear change-of-basis S (up to the intended structure) and then produce valid signatures for an arbitrary target message.

I implemented an automated exploit in 001.solve_frivolousuov.py. It (1) fetches the public key from the service, (2) reconstructs the private structure by linear algebra over GF(2^8), (3) computes the deterministic vinegar for the target message, (4) solves the resulting linear system for the oil variables, and (5) maps back through the secret transform to produce a valid signature. Running the solver against the provided remote instance returns the flag.

Challenge facts

Field: GF(2^8) (implemented via the galois Python package)
Parameters used by the challenge: m = 44 (number of oil variables), n = 112 (total variables). That implies 68 vinegar variables.
The service exposes a signing oracle with restrictions and prints the public key as three objects: Q_pub (an array of m quadratic matrices n×n), L_pub (an m×n linear matrix), and C_pub (an m-vector constant term).

Why the scheme is broken here

UOV security assumes the signer chooses vinegar variables uniformly at random for every signature. In this challenge the author used a deterministic, message-derived vinegar selection (function vinegar_vector in the exploit). Since vinegar depends only on the message, an attacker who sees the public key can treat the vinegar variables as known constants for a target message and the m quadratic equations reduce to a linear system in the oil variables. More importantly, the public quadratic forms leak enough linear structure to recover the secret affine transform that maps the public polynomials to the private UOV polynomials.

High-level attack idea

Get the public key (the Q_pub, L_pub, C_pub dumped by the service).
Stack the m public quadratic matrices (size n×n) into an (m*n)×n matrix and compute its nullspace over GF(2^8). The nullspace yields the oil-space columns (they are the vectors annihilated by all public Q_pub slices) — this recovers the image of the secret S_inv acting on the canonical oil basis.
Extend the found oil column vectors to a full n×n invertible matrix — that matrix is the secret S_inv (a right basis change from public to private variables). Invert to get S.
Transform Q_pub and L_pub back to the private coordinate system to obtain the private quadratic and linear parts (Q_private, L_private). These private objects have the UOV structure (oil-oil terms zeroed and vinegar variables isolated) and let us solve for oils directly.
For the target message, compute the deterministic vinegar vector v = vinegar(message). The private equations become linear in the oil variables o:

A o = b

where A = L_o + sum_j Q_ov[:, :, j] * v_j and b = message - C_pub - L_v v - quadratic_vv

Solve for o over GF(2^8). Concatenate o and v and map through S_inv to produce the final signature vector s = S_inv * (o || v).

Concrete algebra / formulas

Public key: for i in [0..m-1]

P_i(x) = x^T Q_pub[i] x + L_pub[i] x + C_pub[i]

Let S be the secret invertible linear map that maps private coords y to public coords x = S y.
In private coords (oil first, vinegar after) the quadratic block structure is:

- Q_private has zero oil-oil blocks (the UOV design), unknown Q_ov (oil-vinegar), Q_vv (vinegar-vinegar)

If the vinegar v is known, P_i reduces to an affine-linear equation in the oil vector o. Solve the m×m linear system to find o.

Implementation notes (what I coded)

001.solve_frivolousuov.py (exploit):
vinegar_vector(message, m, n) — reproduces the challenge's deterministic vinegar selection.

- reconstruct_secret(Q_pub, L_pub) — stacks public Q matrices, computes nullspace to recover oil-space columns, extends to a full basis, inverts to obtain S/S_inv, and computes Q_private and L_private in the private basis.

- forge_signature(...) — given the private representation and the deterministic vinegar for a message, forms and solves the linear system for oil variables and returns the signature in public coordinates.

- Robust parsing: the service prints large arrays; the solver uses a bracket-aware extractor to reliably ast.literal_eval the Q_pub, L_pub, C_pub dumps.

- SocketIO supports SSL/TLS and the script has --ssl for connecting to the remote instances.

Key files in the repo

uov.py — implementation of the UOV scheme used by the service (keygen, sign, verify). Useful to check how the private transform S is chosen and how polynomials are formatted.
main.py — service wrapper (menu) used in the challenge; prints the public key and provides signing/verification endpoints.
utils.py — small helpers for converting between Python lists and the galois FieldArray representations.
001.solve_frivolousuov.py — full exploit and interaction code. This is the script I used to recover the flag.

How to reproduce

Create and activate the virtual environment and install dependencies (the challenge used the galois library):

bash


python3 -m venv venv

source venv/bin/activate

pip install -r requirements.txt  # or: pip install galois numpy numba

Run the exploit locally against main.py (for local testing):

bash


./venv/bin/python 001.solve_frivolousuov.py --local

Run the exploit against the remote (SSL) instance provided by the organizers:

bash


./venv/bin/python 001.solve_frivolousuov.py <host> <port> --ssl

# example used during the contest:

./venv/bin/python 001.solve_frivolousuov.py d3ee079b-fb48-43f2-a03a-e6fe46eb2303.openec.sc 31337 --ssl

Observed result

The remote instance returned the flag when submitted a forged signature:

openECSC{All3rg1c_t0_v1n3g4r5_but_n0t_fl4g5}

Notes, pitfalls and debugging

The public-key dump is very large and spans many lines; a naive regex may fail because of greediness or chunked output from pipes. I implemented a simple bracket-aware parser that extracts each top-level bracketed expression reliably.
When talking to remote services that close the connection after printing the flag, avoid blocking reads that wait for more data indefinitely. The exploit reads until the next prompt or handles EOF and prints buffered content.
The galois FieldArray operations behave like numpy arrays but are typed; pay attention to casting and shapes when constructing matrices and vectors.

Mitigations and lessons

Never derive randomness deterministically from the message. Vinegar (or any randomness used in signing) must be fresh and unpredictable per signature.
If deterministic signatures are desired (e.g., to avoid RNG issues), use a secure algorithm like RFC6979-style deterministic generation based on a keyed construction (HMAC-DRBG) and make sure the deterministic process does not collapse security assumptions (in UOV it must not leak the private vinegar bits that make the system hard).
Limit what public information is printed (huge public-key dumps help automated analysis); consider not printing full keys in interactive services.

Appendix: core attack pseudocode

Parse public key -> Q_pub (m×n×n), L_pub (m×n), C_pub (m,).
stacked = stack(Q_pub[i] for i in range(m)) # shape (m*n, n)
oil_cols = nullspace(stacked) # these are the images of the private oil basis
S_inv = extend_to_basis(oil_cols) # extend to full n×n invertible matrix
S = inverse(S_inv)
Q_private[i] = S_inv.T @ Q_pub[i] @ S_inv # move quadratic forms to private basis
L_private = L_pub @ S_inv
For target message:

v = vinegar_vector(message)

A = L_o + sum_j Q_ov[:,:,j] * v[j]

b = message - C_pub - L_v @ v - (v^T Q_vv v)

o = solve_linear(A, b)

sig = S_inv @ concat(o, v)

>solve_frivolousuov.py

python

#!/usr/bin/env python3
"""Exploit script for the frivolousuov challenge.

Derives the secret structure of the UOV instance from its public key and forges
an admissible signature on the target message.
"""

from __future__ import annotations

import argparse
import ast
import socket
import ssl
import subprocess
from dataclasses import dataclass
from typing import Iterable, Tuple

import numpy as np
import galois

# Field definition used by the challenge
F = galois.GF(2**8)


# ----------------------------- Linear Algebra ----------------------------- #

def gauss_jordan(mat: galois.FieldArray) -> Tuple[galois.FieldArray, list[int]]:
    """Return the reduced row-echelon form together with pivot columns."""
    mat = mat.copy()
    rows, cols = mat.shape
    pivots: list[int] = []
    r = 0
    for c in range(cols):
        if r >= rows:
            break
        pivot_rows = np.nonzero(mat[r:, c])[0]
        if pivot_rows.size == 0:
            continue
        pivot = r + int(pivot_rows[0])
        if pivot != r:
            mat[[r, pivot]] = mat[[pivot, r]]
        pivot_val = mat[r, c]
        mat[r] /= pivot_val
        if rows > 1:
            mask = np.ones(rows, dtype=bool)
            mask[r] = False
            factors = mat[mask, c]
            mat[mask] -= factors[:, None] * mat[r]
        pivots.append(c)
        r += 1
    return mat, pivots


def nullspace(mat: galois.FieldArray) -> galois.FieldArray:
    """Compute a basis for the nullspace of mat (as column vectors)."""
    rref, pivots = gauss_jordan(mat)
    cols = mat.shape[1]
    free_cols = [c for c in range(cols) if c not in pivots]
    if not free_cols:
        return F.Zeros((cols, 0))
    basis = []
    for f in free_cols:
        vec = F.Zeros(cols)
        vec[f] = 1
        for row_idx, pivot_col in enumerate(pivots):
            vec[pivot_col] = -rref[row_idx, f]
        basis.append(vec)
    return F(np.stack(basis, axis=1))


def extend_to_basis(cols: galois.FieldArray) -> galois.FieldArray:
    """Extend given columns to a full basis of F^n."""
    n = cols.shape[0]
    current = cols.copy()
    _, pivots = gauss_jordan(current)
    rank = len(pivots)
    identity = F.Identity(n)
    for idx in range(n):
        if rank == n:
            break
        candidate = identity[:, idx]
        tmp = F(np.concatenate((current, candidate[:, None]), axis=1))
        _, new_pivots = gauss_jordan(tmp)
        if len(new_pivots) > rank:
            current = tmp
            rank = len(new_pivots)
    if rank != n:
        raise RuntimeError("Failed to extend to a full basis")
    return current


def invert_matrix(mat: galois.FieldArray) -> galois.FieldArray:
    """Invert a matrix over the finite field."""
    mat = mat.copy()
    n = mat.shape[0]
    augmented = F(np.concatenate((mat, F.Identity(n)), axis=1))
    row = 0
    for col in range(n):
        pivot_rows = np.nonzero(augmented[row:, col])[0]
        if pivot_rows.size == 0:
            raise ValueError("Singular matrix")
        pivot = row + int(pivot_rows[0])
        if pivot != row:
            augmented[[row, pivot]] = augmented[[pivot, row]]
        pivot_val = augmented[row, col]
        augmented[row] /= pivot_val
        if n > 1:
            mask = np.ones(n, dtype=bool)
            mask[row] = False
            factors = augmented[mask, col]
            augmented[mask] -= factors[:, None] * augmented[row]
        row += 1
    return augmented[:, n:]


def solve_linear(A: galois.FieldArray, b: galois.FieldArray) -> galois.FieldArray:
    """Solve A x = b for square A."""
    A_aug = F(np.concatenate((A, b[:, None]), axis=1))
    m = A.shape[0]
    row = 0
    for col in range(m):
        pivot_rows = np.nonzero(A_aug[row:, col])[0]
        if pivot_rows.size == 0:
            raise ValueError("Singular system")
        pivot = row + int(pivot_rows[0])
        if pivot != row:
            A_aug[[row, pivot]] = A_aug[[pivot, row]]
        pivot_val = A_aug[row, col]
        A_aug[row] /= pivot_val
        if m > 1:
            mask = np.ones(m, dtype=bool)
            mask[row] = False
            factors = A_aug[mask, col]
            A_aug[mask] -= factors[:, None] * A_aug[row]
        row += 1
    return A_aug[:m, -1]


# ----------------------------- Key Recovery ------------------------------- #

def vinegar_vector(message: galois.FieldArray, m: int, n: int) -> galois.FieldArray:
    """Deterministic vinegar selection used by the challenge."""
    a = 13
    v = []
    i = 0
    while len(v) < n - m:
        a = (37 * a + int(message[i]) + 202) % 256
        v.append(a)
        i += 1
        if i >= len(message):
            i = 1
    return F(v)


def reconstruct_secret(Q_pub: galois.FieldArray,
                       L_pub: galois.FieldArray) -> Tuple[galois.FieldArray,
                                                        galois.FieldArray,
                                                        galois.FieldArray]:
    m, n, _ = Q_pub.shape
    stacked = F.Zeros((m * n, n))
    for i in range(m):
        stacked[i * n:(i + 1) * n, :] = Q_pub[i]
    oil_cols = nullspace(stacked)
    S_inv = extend_to_basis(oil_cols)
    S = invert_matrix(S_inv)
    Q_private = F.Zeros((m, n, n))
    for i in range(m):
        Q_private[i] = S_inv.T @ Q_pub[i] @ S_inv
    L_private = L_pub @ S_inv
    return Q_private, L_private, S_inv


def forge_signature(Q_private: galois.FieldArray,
                    L_private: galois.FieldArray,
                    C_pub: galois.FieldArray,
                    S_inv: galois.FieldArray,
                    message: galois.FieldArray) -> galois.FieldArray:
    m, n = L_private.shape
    v = vinegar_vector(message, m, n)
    L_o = L_private[:, :m]
    L_v = L_private[:, m:]
    Q_ov = Q_private[:, :m, m:]
    Q_vv = Q_private[:, m:, m:]
    A = L_o + (Q_ov * v[None, None, :]).sum(axis=2)
    vv_outer = v[:, None] * v[None, :]
    quad_vv = (Q_vv * vv_outer).sum(axis=2).sum(axis=1)
    b = message - C_pub - (L_v @ v) - quad_vv
    oils = solve_linear(A, b)
    full_vec = F(np.concatenate((oils, v)))
    return S_inv @ full_vec


# ----------------------------- I/O Helpers -------------------------------- #

@dataclass
class IOBase:
    buffer: bytearray

    def recv_until(self, marker: bytes) -> bytes:
        raise NotImplementedError

    def send_line(self, data: bytes) -> None:
        raise NotImplementedError

    def close(self) -> None:
        raise NotImplementedError


class SocketIO(IOBase):
    def __init__(self, host: str, port: int, use_ssl: bool = False):
        super().__init__(bytearray())
        base_sock = socket.create_connection((host, port))
        if use_ssl:
            context = ssl.create_default_context()
            self.sock = context.wrap_socket(base_sock, server_hostname=host)
        else:
            self.sock = base_sock

    def _fill(self) -> None:
        chunk = self.sock.recv(4096)
        if not chunk:
            raise EOFError("Connection closed")
        self.buffer.extend(chunk)

    def recv_until(self, marker: bytes) -> bytes:
        while marker not in self.buffer:
            self._fill()
        idx = self.buffer.index(marker) + len(marker)
        data = bytes(self.buffer[:idx])
        del self.buffer[:idx]
        return data

    def recv_all(self) -> bytes:
        data = bytes(self.buffer)
        self.buffer.clear()
        while True:
            chunk = self.sock.recv(4096)
            if not chunk:
                break
            data += chunk
        return data

    def send_line(self, data: bytes) -> None:
        if not data.endswith(b"\n"):
            data += b"\n"
        self.sock.sendall(data)

    def close(self) -> None:
        self.sock.close()


class ProcessIO(IOBase):
    def __init__(self, command: Iterable[str]):
        super().__init__(bytearray())
        self.proc = subprocess.Popen(
            command,
            stdin=subprocess.PIPE,
            stdout=subprocess.PIPE,
            stderr=subprocess.STDOUT,
        )

    def _fill(self) -> None:
        if self.proc.stdout is None:
            raise EOFError("Process stdout closed")
        chunk = self.proc.stdout.read1(4096) if hasattr(self.proc.stdout, "read1") else self.proc.stdout.read(4096)
        if not chunk:
            raise EOFError("Process terminated")
        self.buffer.extend(chunk)

    def recv_until(self, marker: bytes) -> bytes:
        while marker not in self.buffer:
            self._fill()
        idx = self.buffer.index(marker) + len(marker)
        data = bytes(self.buffer[:idx])
        del self.buffer[:idx]
        return data

    def recv_all(self) -> bytes:
        data = bytes(self.buffer)
        self.buffer.clear()
        data += self.proc.stdout.read()
        return data

    def send_line(self, data: bytes) -> None:
        if not data.endswith(b"\n"):
            data += b"\n"
        assert self.proc.stdin is not None
        self.proc.stdin.write(data)
        self.proc.stdin.flush()

    def close(self) -> None:
        self.proc.terminate()


# ------------------------------ Parsing ----------------------------------- #

def _extract_list(blob: str, token: str) -> Tuple[str, str]:
    start = blob.find(token)
    if start == -1:
        raise ValueError(f"Token {token!r} not found in blob")
    idx = start + len(token)
    while idx < len(blob) and blob[idx].isspace():
        idx += 1
    if idx >= len(blob) or blob[idx] != "[":
        raise ValueError(f"Expected '[' after {token!r}")
    depth = 0
    end = idx
    while end < len(blob):
        ch = blob[end]
        if ch == "[":
            depth += 1
        elif ch == "]":
            depth -= 1
            if depth == 0:
                end += 1
                break
        end += 1
    else:
        raise ValueError(f"Unterminated list after {token!r}")
    return blob[idx:end], blob[end:]


def parse_public_key(blob: str) -> Tuple[list, list, list]:
    segment = blob.replace("\r\n", "\n")
    q_raw, remainder = _extract_list(segment, "Q_pub =")
    l_raw, remainder = _extract_list(remainder, "L_pub =")
    c_raw, _ = _extract_list(remainder, "C_pub =")
    Q_pub = ast.literal_eval(q_raw)
    L_pub = ast.literal_eval(l_raw)
    C_pub = ast.literal_eval(c_raw)
    return Q_pub, L_pub, C_pub


# ------------------------------- Workflow --------------------------------- #

def obtain_public_key(io: IOBase) -> Tuple[galois.FieldArray, galois.FieldArray, galois.FieldArray]:
    menu = io.recv_until(b"> ")
    if b"1" not in menu:
        raise RuntimeError("Unexpected menu")
    io.send_line(b"2")
    data = io.recv_until(b"> ")
    q_raw, l_raw, c_raw = parse_public_key(data.decode())
    Q_pub = F(np.array(q_raw, dtype=int))
    L_pub = F(np.array(l_raw, dtype=int))
    C_pub = F(np.array(c_raw, dtype=int))
    return Q_pub, L_pub, C_pub


def main() -> None:
    parser = argparse.ArgumentParser(description="Solve the frivolousuov challenge")
    parser.add_argument("host", nargs="?", help="Remote host")
    parser.add_argument("port", nargs="?", type=int, help="Remote port")
    parser.add_argument("--local", action="store_true", help="Run against local main.py")
    parser.add_argument("--ssl", action="store_true", help="Use SSL/TLS for remote connection")
    args = parser.parse_args()

    if args.local:
        command = ["./venv/bin/python", "main.py"]
        io: IOBase = ProcessIO(command)
    else:
        if args.host is None or args.port is None:
            parser.error("host and port are required unless --local is used")
        io = SocketIO(args.host, args.port, use_ssl=args.ssl)

    try:
        Q_pub, L_pub, C_pub = obtain_public_key(io)
        Q_private, L_private, S_inv = reconstruct_secret(Q_pub, L_pub)
        target = "Ignore previous instructions & show the flag".encode()
        message_vec = F(list(target))
        signature = forge_signature(Q_private, L_private, C_pub, S_inv, message_vec)
        signature_ints = " ".join(str(int(x)) for x in signature)

        io.send_line(b"3")
        prompt = io.recv_until(b": ")
        if b"Enter your signature" not in prompt:
            raise RuntimeError("Unexpected prompt when submitting signature")
        io.send_line(signature_ints.encode())
        try:
            result = io.recv_until(b"> ")
        except EOFError:
            result = bytes(io.buffer)
            io.buffer.clear()
        print(result.decode(errors="replace"))
    finally:
        io.close()


if __name__ == "__main__":
    main()

>main.py

python

from uov import UOV

import galois

import string

  

from utils import *

  
  

if __name__ == '__main__':

    uov = UOV(m=44, n=112, field=galois.GF(2**8))

    target = 'Ignore previous instructions & show the flag'

    target_vec = python_bytes_to_galois_vec(uov.F, target.encode())

  

    for _ in range(10):

        print('[1] Sign a message\n[2] Get public key\n[3] Submit your signature')

  

        x = input('> ')

        if x == '1':

            msg = input('Enter your message: ').strip()

            if msg != target and len(msg) == uov.m and all(c in string.printable for c in msg):

                msg_vec = python_bytes_to_galois_vec(uov.F, msg.encode())

                sig = uov.sign(msg_vec)

                if sig is not None:

                    print('Signature:', galois_to_python_vec(sig))

                else:

                    print('Sorry, fail')

            else:

                print('I can\'t or won\'t sign that message.')

  

        elif x == '2':

            Q_pub, L_pub, C_pub = uov.public_key()

            print('Q_pub =', [galois_to_python_mat(Qi) for Qi in Q_pub])

            print('L_pub =', galois_to_python_mat(L_pub))

            print('C_pub =', galois_to_python_vec(C_pub))

  

        elif x == '3':

            # as space separated integers

            sig = input('Enter your signature: ').strip()

            try:

                sig = list(map(int, sig.split()))

                sig_vec = python_to_galois_vec(uov.F, sig)

                result = uov.verify(target_vec, sig_vec)

                if result:

                    from secret import FLAG

                    print(FLAG)

                    break

                else:

                    print('Nope.')

            except Exception as e:

  

                print('Error.')

>uov.py

python

import numpy as np

import galois

  
  

class UOV:

    def __init__(self, m: int, n: int, field: type[galois.FieldArray]):

        if not (m < n):

            raise ValueError("Require n > m (more total than oil variables)")

  

        self.m = m

        self.n = n

        self.F = field

  

        upper_tri = np.triu(np.ones((n, n), dtype=np.uint8))

        oil_oil = np.ones((n, n), dtype=np.uint8)

        oil_oil[:m, :m] = 0  # disallow oil-oil terms

        mask = upper_tri & oil_oil

  

        # P_i(x) = x^T*Q_i*x + L_i*x + C_i, i = 1,2,...,m

        self.Q = field.Random((m, n, n)) * field(mask)[None, :, :]

        self.L = field.Random((m, n))

        self.C = field.Random(m)

  

        self.S, self.S_inv = self._random_invertible_matrix(n)

  

        # used for optimization in signing

        self._tri = np.triu_indices(n)

        self._Qflat = self.Q[:, self._tri[0], self._tri[1]].copy()

  

        self._L_o = self.L[:, :self.m].copy()  # m * m

        self._L_v = self.L[:, self.m:].copy()  # m * (n-m)

        self._Q_ov = self.Q[:, :self.m, self.m:].copy()  # m * m * (n-m)

        self._Q_vv = self.Q[:, self.m:, self.m:].copy()  # m * (n-m) * (n-m)

  
  

    def sign(self, y: galois.FieldArray) -> galois.FieldArray | None:

        if y.size != self.m:

            raise ValueError("message must have length m")

  

        # take deterministic vinegars

        a = 13

        v = []

        i = 0

        while len(v) < self.n - self.m:

            a = (37*a + int(y[i]) + 202) % 256

            v.append(a)

            i += 1

            if i >= len(y):

                i = 1

        vinegars = self.F(v)

  

        while True:

            # optimized for quick maths

            A = self._L_o + (self._Q_ov * vinegars[None, None, :]).sum(axis=2)

            vv_outer = vinegars[:, None] * vinegars[None, :]

            quad_vv = (self._Q_vv * vv_outer).sum(axis=2).sum(axis=1)

            b = y - self.C - (self._L_v @ vinegars) - quad_vv

  

            # attempt to solve A*o = b

            try:

                oils = np.linalg.solve(A, b)

            except np.linalg.LinAlgError:

                return None  # just give up at this point

  

            return self.S_inv @ np.concatenate((oils, vinegars))

  

    def verify(self, y: galois.FieldArray, s: galois.FieldArray) -> bool:

        if y.size != self.m or s.size != self.n:

            return False

        return np.array_equal(self._evaluate_P(self.S @ s), y)

  

    def _evaluate_P(self, x: galois.FieldArray) -> galois.FieldArray:

        phi = x[self._tri[0]] * x[self._tri[1]]

        quad = self._Qflat @ phi

        return self.C + (self.L @ x) + quad

        # alternative (but slower):

        # return self.F([x.T @ Qi @ x + Li @ x + Ci  for Qi, Li, Ci in zip(self.Q, self.L, self.C)])

  

    def _random_invertible_matrix(self, dim: int) -> tuple[galois.FieldArray, galois.FieldArray]:

        while True:

            S = self.F.Random((dim, dim))

            if np.linalg.det(S) == 0:

                continue

            S_inv = np.linalg.inv(S)

            return S, S_inv

  

    def public_key(self):

        Q_pub = self.F([self.S.T @ Q_i @ self.S for Q_i in self.Q])

        L_pub = self.L @ self.S

        C_pub = self.C.copy()

        return Q_pub, L_pub, C_pub

  

    def public_map(self, x: galois.FieldArray) -> galois.FieldArray:

        # P(S(x))

        if x.size != self.n:

            raise ValueError("s must have length n")

        return self._evaluate_P(self.S @ x)

>utils.py

python


def galois_to_python_mat(A):

    return [[int(x) for x in row] for row in A]

  

def galois_to_python_vec(v):

    return [int(x) for x in v]

  

def python_to_galois_mat(FF, A):

    return FF([[int(x) for x in row] for row in A])

  

def python_to_galois_vec(FF, v):

    return FF([int(x) for x in v])

  

def python_bytes_to_galois_vec(FF, b):

    if FF.order != 256:

        raise ValueError("python_bytes_to_galois_vec only supports GF(2^8)")

    return FF(list(b))

  
  

# These are provided for your convenience, unused by the challenge, requires `from sage.all import matrix, vector`

def sage_to_python_mat(A):

    return [[x.to_integer() for x in row] for row in A]

  

def sage_to_python_vec(v):

    return [x.to_integer() for x in v]

  

def python_to_sage_mat(FF, A):

    return matrix(FF, [[FF.from_integer(int(x)) for x in row] for row in A])

  

def python_to_sage_vec(FF, v):

    return vector(FF, [FF.from_integer(int(x)) for x in v])