# This embeds a secret message in the secret key
def embed(message, n, o, F):
    # Convert message to enough bytes:
    message = message.encode().ljust((o*(n-o))//2, b"\x00")
    assert len(message) == (o*(n-o))//2
    
    # Write bytes into O from left to right and top to bottom:
    O = matrix(F, o, n-o)
    i = 0
    j = 0
    for b in message:
        O[i,j] = F.from_integer(b >> 4)
        j += 1
        if j == n-o:
            i += 1
            j = 0
        O[i,j] = F.from_integer(b & 0xf)
        j += 1
        if j == n-o:
            i += 1
            j = 0

    # Append identity matrix to make it full rank:
    O = O.augment(identity_matrix(F, o))

    # Enumerate the Oil-Space and sort it lexicographically:
    OS = sorted([x*O for x in VectorSpace(F,o)])

    # Find the rows of O in the sorted oil-Space:
    positions = [OS.index(row) for row in O]
    return O, positions

# This extracts a secret message from the secret key and a list of row positions
def unembed(O, positions, n, o, F):
    # Check if O has the right format:
    #assert len(O) == o, f"There should be {o} many basis vectors."
    #for row in O:
    #    assert len(row) == n, f"Each vector should have {n} entries."
    #    row = vector(F, row)
    #O = parse_matrix(O)

    # Enumerate the Oil-Space and sort it lexicographically:
    OS = sorted([x*O for x in VectorSpace(F,o)])

    # Find the original basis vectors:
    basis = [OS[p][:n-o] for p in positions]
    basis = [b.to_integer() for vec in basis for b in vec]

    # Decode:
    message = ""
    for i in range(len(basis)//2):
        character = (basis[2*i] << 4) | (basis[2*i+1])
        message += chr(character)

    return message