"""
AES-128 on one 16-byte block, with one step optionally removed.

This is the AES from the lecture. Use it to test ideas for the four
challenges. Run it once to check it:

    python3 aes.py

encrypt_block(pt, key, skip) and decrypt_block(ct, key, skip) take an
optional skip: one of "SubBytes", "ShiftRows", "MixColumns",
"AddRoundKey". That step is removed from all ten rounds. Skipping
AddRoundKey also removes the first XOR with K0. Round 10 never has
MixColumns, as in real AES. There is no mode of operation: one block only.

The state is a list of 16 bytes in the standard AES order:
state[4*c + r] is the byte in row r, column c.
"""

STEPS = ("SubBytes", "ShiftRows", "MixColumns", "AddRoundKey")


def xtime(a):
    """Multiply a byte by 2 (the 'double' from the lecture)."""
    a <<= 1
    return a ^ 0x11b if a & 0x100 else a


def gmul(a, b):
    """Multiply two bytes: shift and add, with XOR as the addition."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a = xtime(a)
        b >>= 1
    return r


def _make_sbox():
    inv = [0] * 256
    for a in range(1, 256):
        for b in range(1, 256):
            if gmul(a, b) == 1:
                inv[a] = b
                break
    sbox = []
    for x in range(256):
        b, r = inv[x], 0x63
        for i in range(5):
            r ^= ((b << i) | (b >> (8 - i))) & 0xff
        sbox.append(r)
    return sbox


SBOX = _make_sbox()
INV_SBOX = [0] * 256
for _i, _v in enumerate(SBOX):
    INV_SBOX[_v] = _i
RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]


def key_expansion(key):
    """Return the round keys K0 .. K10, each a list of 16 bytes."""
    w = [list(key[4 * i:4 * i + 4]) for i in range(4)]
    for i in range(4, 44):
        t = list(w[i - 1])
        if i % 4 == 0:                       # g: rotate, S-box, Rcon
            t = t[1:] + t[:1]
            t = [SBOX[b] for b in t]
            t[0] ^= RCON[i // 4 - 1]
        w.append([a ^ b for a, b in zip(w[i - 4], t)])
    return [sum(w[4 * r:4 * r + 4], []) for r in range(11)]


def sub_bytes(s):       return [SBOX[b] for b in s]
def inv_sub_bytes(s):   return [INV_SBOX[b] for b in s]
def shift_rows(s):      return [s[4 * ((i // 4 + i % 4) % 4) + i % 4] for i in range(16)]  # row r left by r
def inv_shift_rows(s):  return [s[4 * ((i // 4 - i % 4) % 4) + i % 4] for i in range(16)]  # row r right by r
def add_round_key(s, k): return [a ^ b for a, b in zip(s, k)]


def _mix(s, m):
    out = []
    for c in range(4):
        col = s[4 * c:4 * c + 4]
        for r in range(4):
            v = 0
            for j in range(4):
                v ^= gmul(col[j], m[(j - r) % 4])
            out.append(v)
    return out


def mix_columns(s):     return _mix(s, (2, 3, 1, 1))      # matrix rows 02 03 01 01
def inv_mix_columns(s): return _mix(s, (14, 11, 13, 9))   # matrix rows 0e 0b 0d 09


def encrypt_block(pt, key, skip=None):
    assert len(pt) == 16 and len(key) == 16 and skip in (None,) + STEPS
    K = key_expansion(key)
    s = list(pt)
    if skip != "AddRoundKey":
        s = add_round_key(s, K[0])
    for r in range(1, 11):
        if skip != "SubBytes":
            s = sub_bytes(s)
        if skip != "ShiftRows":
            s = shift_rows(s)
        if skip != "MixColumns" and r < 10:
            s = mix_columns(s)
        if skip != "AddRoundKey":
            s = add_round_key(s, K[r])
    return bytes(s)


def decrypt_block(ct, key, skip=None):
    assert len(ct) == 16 and len(key) == 16 and skip in (None,) + STEPS
    K = key_expansion(key)
    s = list(ct)
    for r in range(10, 0, -1):
        if skip != "AddRoundKey":
            s = add_round_key(s, K[r])
        if skip != "MixColumns" and r < 10:
            s = inv_mix_columns(s)
        if skip != "ShiftRows":
            s = inv_shift_rows(s)
        if skip != "SubBytes":
            s = inv_sub_bytes(s)
    if skip != "AddRoundKey":
        s = add_round_key(s, K[0])
    return bytes(s)


if __name__ == "__main__":
    key = bytes(range(16))                                   # 00 01 02 ... 0f
    pt = bytes.fromhex("00112233445566778899aabbccddeeff")
    expected = {
        None:          "69c4e0d86a7b0430d8cdb78070b4c55a",   # FIPS-197, appendix C.1
        "SubBytes":    "b60c4e707d338ca91e252895a5914de4",
        "ShiftRows":   "5300bda29c7e35fbca37eb5f48c9fbef",
        "MixColumns":  "5cec2b6ff8595c257f0cc5620b901e90",
        "AddRoundKey": "8c34c7e2358383edd3da9b3d23cca3b3",
    }
    for skip, want in expected.items():
        ct = encrypt_block(pt, key, skip)
        ok = ct.hex() == want and decrypt_block(ct, key, skip) == pt
        print(f"skip={str(skip):12} {ct.hex()}  {'ok' if ok else 'WRONG'}")
