import random


def PKCS1_encode(message, total_bytes):
    """
    Encodes the given message using PKCS1 v1.5 scheme:
    PKCS1(M) = 0x00 | 0x02 | [non-zero padding bytes] | 0x00 | [M]
    length(PKCS1(M)) = total_bytes
    """

    # 11 = 3 constant bytes and at aleast 8 bytes for padding
    if len(message) > total_bytes - 11:
        raise Exception("Message to big for encoding scheme!")

    pad_len = total_bytes - 3 - len(message)

    # non-zero padding bytes
    padding = bytes(random.sample(range(1, 256), pad_len))

    encoded = b"\x00\x02" + padding + b"\x00" + message

    return encoded