Implementing AES Galois field operations in Python

In this blog post we’ll go through the steps of creating a class for performing basic operations in Rijndael’s (AES) finite field. AES a widely used symmetric encryption algorithm uses Rijndael’s field in its core.

Theoretical minimum

A field is a set of elements with operations of addition, subtraction, multiplication and division defined for elements of the set. Elements of AES field are bytes, meaning there are 256 of them. Operations in the field however are not standard arithmetic addition and multiplication.

Data structure

Let’s create a class with a byte value

class GaloisAES:
    def get_value(self):
        return self.value

    def __init__(self, value):
        self.value = value

Addition

Addition in AES field is defined as XOR

    def __add__(self, other):
        return GaloisAES(self.value ^ other.value)

Multiplication

AES field is a Galois field of polynomials. Multiplication in this field is defined as multiplication of polynomials modulo some other polynomial. We use modulo operation to keep product element within the field. We use this polynomial for modulo operation $$ x^8 + x^4 + x^3 + x^1 + x^0 $$ Multiplication is implemented using bit operations - we use standard long multiplication but in binary. 0x80 corresponds to x⁸ part of the polynomial and catches when we overflow. 0x1B corresponds to x⁴ + x³ + x¹ part of the polynomial we take modulo operation with.

    def __mul__(self, other):
        a = self.value
        b = other.value
        product = 0
        for i in range(8):
            if (b & 1) == 1: 
                product ^= a
            hi_bit_set = a & 0x80
            a = (a << 1) & 0xFF
            if hi_bit_set == 0x80:
                a ^= 0x1B
            b >>= 1
        return GaloisAES(product)

Inverse

This is a lazy implementation of inverse operation that just goes through all values in the field until it finds the one that produces 1 when multiplied with the input.

    def inverse(self):
        if self.value == 0:
            return GaloisAES(0)
        for i in range(1, 255):
            mult = self * GaloisAES(i)
            if mult.get_value() == 1:
                return GaloisAES(i)

References

[1] Description of AES standard

[2] Detailed description of multiplication