# FINITE FIELDS / GALOIS FIELDS

## Motivation

The Advanced Encryption Standard (AES) / Rijndael algorithm is the most widely used symmetric/private/secret key cryptographic protocol. The only feasible way of breaking it up to date is by a brute force attack. This does not include implementation flaws by the implementor and side channel attacks due to physical access of the device implementing AES.

The AES works on a block size of 16 bytes but since binary math happens on bytes/octets on a digital computer, AES works in the finite extension field GF(2^{8}) where q=2 and m=8. More information on this in a later post.

To work in finite fields, the arithmetic is different from normal binary arithmetic as it involves modular arithmetic as read from the previous post.

## Theory

A field is basically a set of numbers where addition, subtraction(additive inverse), multiplication and division(multiplicative inverse) are defined. This means that using any of these operations on the numbers will not break any mathematical properties of the oprations.

If a set of numbers is an algebraic group under both multiplication and addition, therefore the set of numbers become a field. The existence of an additive group automatically defines its inverse operation(subtraction). The same with the definition of division via the existence of a multiplicative group. Where both exist on a given set of numbers, the numbers become a field. The distributive law holds for fields. a(b+c)=ab+bc

As a field is simply a set. we define a version of a field called a finite field. A finite field is a field with a finite number of elements. The number of elements of a finite field is called the order/cardinality of the field.

A finite field is also known as a **Galois field** in honor of its creator, Évariste Galois

For a Finite/Galois field to exist. The order of the field must be prime.(Number of elements in the finite field must be a prime number)- A mathematical proof exists but is outside the scope of this discussion. See the error control coding book referenced.

A Finite/Galois field is summarized as **GF(q)**, where q is a general prime number representation. The simplest finite field is the field of binary numbers {0,1} represented as GF(2).

In addition to prime field, there also exist extension fields that are extensions of prime fields. The order of an extension field is simply the prime number raised to an integer power m>2, This is represented as **GF(q ^{m}).**

We use the term prime fields to differentiate **GF(q)** from extension fields **GF(q ^{m})**.

## PRIME FIELD GF(q) ARITHMETIC

Example: GF(q) = GF(5) – {0,1,2,3,4} and GF(q)=GF(2) – {0,1}

This operation (prime field arithmetic) refers to a single digit of a field. For arithmetic on a tuple of digits from a field we can use field extensions GF(q^{m}).

### GF(q) ADDITION (a+b)mod q

GF(q) addition is a mod q operation.

+ | 0 | 1 |
---|---|---|

0 | 0 | 1 |

1 | 1 | 0 |

Figure: GF(2) addition. The above is the same as a binary XOR operation.

+ | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 1 | 2 | 3 | 4 |

1 | 1 | 2 | 3 | 4 | 0 |

2 | 2 | 3 | 4 | 0 | 1 |

3 | 3 | 4 | 0 | 1 | 2 |

4 | 4 | 0 | 1 | 2 | 3 |

Figure: GF(5) addition.

### GF(q) SUBTRACTION (a-b)mod q

GF(q) Subtraction is an additive inverse and can be represented as a + (-b) = c.

Thus b + (-b)=0 is an operation to finds the additive inverse where 0 is the additive neutral/identity element.

Example: In GF(5), 5 – 2 ≡ 5 + (-2) = 5 + 3 ≡ 8 mod 5 = 3 mod 5

Therefore additive inverse of 2 in GF(5) is 3. Addition and subtraction operations give same result if the operands are unchanged in mod 2 operation.

– | 0 | 1 |
---|---|---|

0 | 0 | 1 |

1 | 1 | 0 |

Figure: Modulo GF(2) subtraction. Similar to GF(2) addition.

row-column | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 4 | 3 | 2 | 1 |

1 | 1 | 0 | 4 | 3 | 2 |

2 | 2 | 1 | 0 | 4 | 3 |

3 | 3 | 2 | 1 | 0 | 4 |

4 | 4 | 3 | 2 | 1 | 0 |

Figure: GF(5) subtraction (column-row) because subtraction is non commutative unless when viewed as an additive inverse.

### GF(q) MULTIPLICATION (axb)mod q

GF(q) multiplication is a mod q operation.

x | 0 | 1 |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

Figure: GF(2) multiplication. This is similar to a binary AND operation.

x | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|

0 | 0 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 2 | 3 | 4 |

2 | 0 | 2 | 4 | 1 | 3 |

3 | 0 | 3 | 1 | 4 | 2 |

4 | 0 | 4 | 3 | 2 | 1 |

Figure: GF(5) multiplication

### GF(q) MULTIPLICATIVE INVERSE axa^{-1}=1 mod q

GF(q) division is an multiplicative inverse and can be represented as (1/b)

Thus bx(1/b)=1mod q is an operation that finds the multiplicative inverse where 1 is the multiplicative neutral/identity element.

Example: In GF(5), 5/2 ≡ 5 x (1/2)

(1/2) should be read as “**the additive inverse of 2**“. The value of (1/2) is not 0.5 as 0.5 is not in GF(q) as it is not an integer.

To obtain the multiplicative inverse of 2 (1/2), we obtain the value which when multiplied by 2 gives 1. This can be done via a lookup on the multiplicative table. The value is seen to be 3. Therefore multiplicative inverse of 2 in GF(5) is 3.

The multiplicative inverse of an element in GF(2) is the same as its complement via a binary NOT operation on the element.

Example: Multiplicative inverse of 1 is 0 and vice versa.

row x (1/column) | 0 | 1 |
---|---|---|

0 | 0 | 0 |

1 | 1 | 0 |

Figure: GF(2) division

## Difference between prime fields and extension fields

The difference between working in a prime fields **GF(q)** and an extension field **GF(q ^{m})** can be summarised as below with addition(Remember: q

^{0}=1 and q

^{1}=q):

GF(2) addition: 1+1=0

GF(2^{8}) addition: 11011110+11111111=00100001

GF(2^{4}) addition: 1101+1111=0010

## Difference between field arithmetic and normal integer arithmetic(2’s complement arithmetic)

The difference between the above is that normal integer arithmetic does not involve modular arithmetic therefore does not wrap around.

**Bit wide arithmetic**

Normal binary arithmetic: 1+1 = 10 (3 in decimal)

vs

GF(2) arithmetic: 1+1 = 0 (0 in decimal)

**Byte wide arithmetic**

Normal binary arithmetic: 10110101+11111111 = 110110100 (436 in decimal)

vs

GF(2^{8}) arithmetic: 10110101+11111111=01001010(74 in decimal). The value never goes beyond outside the range [0, 2^{m}-1]

**Note:**To implement prime field and extension fields in software, a class that abides by finite field arithmetic can be formed that has methods named add, subtract, divide, multiply.

The next post shall deal with extension field arithmetic before getting into AES cryptography.

An analysis of various cryptographic implementations shall be discussed including:

An analysis of cryptographic compliance based on NIST standards shall be made.

## References

- Book: Paar, C., Pelzl, J. and Preneel, B. (2014). Understanding Cryptography. Berlin: Springer Berlin.
- Book: Lin, S. and Costello, D. (2004). Error control coding. Upper Saddle River, N.J.: Pearson Prentice Hall.
- Web article: Elliptic curve cryptography and discrete logarithm by Andrea Corbellini
- Video: ECCHacks – A gentle introduction to elliptic-curve cryptography [31c3]