GF(2^m) multiplication

gf2_demo.py

def gf2_mult_intermed(a, b, m):
    result = 0
    for biti in range(m):
        if a & (1 << biti):
            result ^= (b << biti)
    return result

def gf2_reduce(c, p, m):
    # polynomial has an implicit, unspecified x^m term
    c_bits = 2*m-1
    for biti in reversed(range(m, c_bits)):
        if c & (1 << biti):
            c ^= (p << (biti - m))
    mask = (1 << m) - 1
    return c & mask

def aes_gf2_wikipedia_example(a, b):
    p = 0
    for counter in range(8):
        if b & 1:
            p ^= a
        hi_bit_set = a & 0x80
        a = (a << 1) & 0xff
        if hi_bit_set:
            a ^= 0x1b
        b >>= 1
    return p

def aes_gf2_ours(a, b):
    c_ = gf2_mult_intermed(a, b, 8)
    c = gf2_reduce(c_, 0x1b, 8)
    return c

for a in range(256):
    for b in range(256):
        assert aes_gf2_wikipedia_example(a, b) == aes_gf2_ours(a, b)