This is short intro to Galois fields which is important for cryptography. For example, AES uses in section 4

each byte in the state array is interpreted as one of the 256 elements of a fnite feld, also known as a Galois Field, denoted by GF(28). 1

In order to defne addition and multiplication in GF(28), each byte {b7 b6 b5 b4 b3 b2 b1 b0} is interpreted as a polynomial, denoted by b(x), as follows:

For example, {01100011} is represented by the polynomial x6 +x5 +x+1.

Addition Link to heading

Addition is defined as adding the coeff of the polynomial with modulo 2.

In order to add two elements in the fnite feld GF(28), the coeffcients of the polynomials that represent the elements are added modulo 2 (i.e., with the exclusive-OR operation, denoted by ⊕), so that 1⊕1 = 0, 1⊕0 = 1, and 0 ⊕0 = 0

Equivalently, two bytes can be added by applying the exclusive-OR operation to each pair of corresponding bits in the bytes. T

Multiplication Link to heading

Multiplication is more complicated and is defined as follows:

this multiplication is defned on two bytes in two steps: 1) the two polynomials that represent the bytes are multiplied as polynomials, and 2) the resulting polynomial is reduced modulo the following fxed polynomial: m(x) = x^8 + x^4 + x^3 + 1

Exmamples Link to heading

To show the python implementation, This is one of AES Mix column operations for first row.

s0,c = ({02} • s0,c) ⊕ ({03} • s1,c)⊕ s2,c ⊕ s3,c

So, addition is XOR but {03} * S is broken down to

S * ({02} + {01})

S * {02} + S * {01}

xtimes(S) + S

And the python code would be implemented as follows

def xtimes(a):
    return (((a << 1) ^ 0x1b) & 0xff) if (a & 0x80) else (a << 1)

 xtimes(a[0]) ^ xtimes(a[1]) ^ a[1] ^ a[2] ^ a[3]