Finite Field Arithmetic

Groups, Rings, Fields

• Finite field is a set containing a finite number of elements
• This is sometimes called Galois Field
• Can; add, subtract, multiple and invert(divide)
• Fields are an extension to rings and groups

Groups

A group is a set of elements $G$ together with an operation that combines two elements of $G$

1. The operation is closed
2. Operation is associative
3. There is an element $1\in G$ called a neutral element such that..
4. For each $a\in G$ there exists an element $a^{-1} \in G$ called the inverse of $a$ such that ...
5. A group $G$ is abelian(commutative) if ...

Fields

A field $F$ is a set of elements with the following properties:

1. All elements of $F$ form an additive group with the group operation + and the neutral element 0
2. All elements of $F$ except 0 form a multiplicative group with the group operation $\times$ (or -) ..
3. ....

Always interest in Finite Fields, fields with a finite number of elements

Finite Fields

Finite field only exists if it has $p^m$ elements $p$ = prime $m$ = Positive Integer

Prime Fields

• Contains the integers {0,1,...,$p-1$}
• All members of a prime field have a multiplicative inverse

Extension Fields

• In prime fields, the elements of integers
• Elements in extension fields GF($2^m$) are polynomials of degree less than $m$

GF($2^3$)

• Add = XOR???

Inversion is performed in a similar way to prime fields

AES' Finite Field

• AES uses the extension field GF($2^8$)/GF(254) for many of its operations
• Operations are the same as those in other GF($2^m$) fields, using the irreducible polynomial ...
• Polynomials are typically represented as single bytes