Finite Field

In this section we will talk about something in abstract algebra, and i’m trying to make it painless and simple.
Finite Fields is a vary important topic in cryptography and it is used in many encryption algorithms such as AES encryption algorithm.
I will skip a lot of branches in abstract algebra such as (modular, arithmetic Euclidean algorithms … etc) and you can find it easily on Wikipedia.
Starting with some terminology

• A set : Is a group of elements or members represented as a unit, set can be described in several ways such as braces {5,13,27,30}.
• A field : Is a set of elements with two binary operations addition and multiplication.
  Fields have the following properties:

1. Closure under addition which if a and b belong to S, then a+b is also in S.
2. Associativity of addition which a+(b+c) = (a+b)+c and a,b,c in S.
3. Additive identity which there is an element 0 in R such that a+0 = 0+a = a for all in S.
4. Additive inverse which for each a in S there is an element -a in S such that a+(-a)=(-a)+a =0.
5. Commutativity of addition which a+b=b+a for all a.b in S.
6. Closure under multiplication which if a and b belong to S , then ab is also in S.
7. Associativity of multiplication which a(bc) = (ab)c for all a,b,c in S.
8. Distributed laws which a(b+c) = ab+ac for all a,b,c in S.
9. Multiplication Identity which there is an element 1 in S such that a1 = 1a = a for all in S.
10. No zero division which if a,b in S and ab=0, then either a=0 or b=0.
11. Multiplication inverse which if a belongs to S and a != 0 ,there is an element \({a}^{-1}\) is S such that \({aa}^{-1}\) =1.

Finite Fields have a property called “order”, order in finite field is the number of the elements in the filed and this order must be a power of a prime number GF(\({P}^{n}\)) GF is stands for Galois Field , and Galois is a mathematician who create the finite field, P is a prime number, n : is a positive integer.
In finite field we preform operations such as addition and multiplication without leaving the set
For example:
in GF(7), so the set will be {0,1,2,3,4,5,6} six elements start from 0 to p-1, if we preform addition operation 5+4=9 mod(7) = 2 and 2 is in the set.

AES encryption algorithm work under GF(\({2}^{8}\)) but in a binary representation, we will represent Galois Field by using polynomial, and it’s much easier.
In GF(\({2}^{8}\)), if we want to represent GF(91) first we need to convert it into a binary 01011011, second convert it into a polynomial under one variable x \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+({x}^{2})+({x}^{1})+1\) and all zeros are discarded from the polynomial, so the polynomial representation will be \(({x}^{6})+({x}^{4})+({x}^{3})+x+1\)

• Addition operation in polynomial representation in GF(\({2}^{8}\)): To preform addition operation simply we will add two polynomials and then we take mod(2) to reduce 2 coefficients (remove any 2 coefficients).
  For example:
  In GF(\({2}^{8}\)) add 83 and 249
  83 = 01010011 = \(({x}^{6})+({x}^{4})+x+1\)
  249 = 11111001 = \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+1\)
  add 1 and 2 = \((({x}^{7})+2({x}^{6})+({x}^{5})+2({x}^{4})+({x}^{3})+x+2)mod(2)\)
  remove 2 coefficients \(2({x}^{6})+2({x}^{4})+2\)
  = \(({x}^{7})+({x}^{5})+({x}^{3})+x\) (polynomial representation)
  = 10101010 (binary representation)
  = 170 (decimal representation)

• Addition operation in binary representation in GF(\({2}^{8}\)): To add two numbers in binary representation in GF(\({2}^{8}\)) form we just preform XOR operation instead of arithmetic addition.
  For example :
  In GF(\({2}^{8}\)) add 83 and 249
  83 = 01010011
  249 = 11111001
  01010011 ⊕ 11111001 = 10101010 = 170

• Multiplication in polynomial representation in GF(\({2}^{8}\)): Here we will multiply two polynomials and then we take mod(2) to reduce 2 coefficients, but if the results exceed 255 in binary or 11111111 in binary or \({x}^{7}\) in polynomial then we use irreducible polynomial to reduce the results by a long division the result over the irreducible polynomial and the result is the reminder of division, and in GF(\({2}^{8}\)) irreducible polynomial \(m(x) = ({x}^{8})+({x}^{4})+({x}^{3})+x+1\)
  For example :
  In GF(\({2}^{8}\)) multiply 83 and 249
  83 = \(({x}^{6})+({x}^{4})+x+1\)
  249 = \(({x}^{7})+({x}^{6})+({x}^{5})+({x}^{4})+({x}^{3})+x+1\)
  multiply 1 and 2 and take mod(2)
  = \(({x}^{13})+({x}^{12})+({x}^{7})+({x}^{6})+({x}^{4})+({x}^{3})+x+1\)
  OR by using MATLAB and get the same result
  a = gf( [1 0 1 0 0 1 1] );
  b = gf( [1 1 1 1 1 0 0 1] );
  c = conv(a,b)

The results here exceed \({x}^{7}\) then we preform a long division by the irreducible polynomial and the result is the reminder

\(({x}^{13})+({x}^{12})+({x}^{7})+({x}^{6})+({x}^{4})+({x}^{3})+x+1\)
—————————————————————————*
\(({x}^{8})+({x}^{4})+({x}^{3})+x+1\)
Result = \(({x}^{5})+({x}^{4})+x\)
Remainder = \(({x}^{5})+({x}^{4})+({x}^{3})+({x}^{2})+1\)

The result
= \(({x}^{5})+({x}^{4})+({x}^{3})+({x}^{3})+1\) (polynomial representation)
= 00111101 (binary form)
= 61 (decimal form)

OR by using MATLAB and get the same result
a = gf( [1 1 0 0 0 0 1 1 0 1 1 0 1 1] );
b = gf( [1 0 0 0 1 1 0 1 1] );
[q,r] = deconv(a,b)

Note 1: If you found this hard to understand you can use GF-Calculator to preform addition and multiplication on two decimal numbers in GF(\({2}^{8}\))
Note 2: You can multiply two polynomials by using Euclidean algorithm (Extended Euclid).
Note 3: A polynomial is irreducible if it cannot be expressed as the product of two or more such polynomials.
Note 4: \(m(x) = ({x}^{8})+({x}^{4})+({x}^{3})+x +1\) is one of 30 possible irreducible polynomials of degree 8.