text: ## 3/19/2015
  
  ### cryptography8
  
  Cryptography 8
  
  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          ---> If a and b belong to S, then a+b is also in S.
  2- Associativity of addition        ---> a+(b+c) = (a+b)+c and a,b,c in S.
  3- Additive identity                   ---> There is an element 0 in R such that a+0 = 0+a = a for all in S.
  4- Additive inverse               ---> For each a in S there is an element -a in S such that a+(-a)=(-a)+a =0.
  5- Commutativity of addition     ---> a+b=b+a for all a.b in S.
  6- Closure under multiplication  ---> if a and b belong to S , then ab is also in S.
  7- Associativity of multiplication ---> a(bc) = (ab)c for all a,b,c in S.
  8- Distributed laws                   ---> a(b+c) = ab+ac for all a,b,c in S.
  9- Multiplication Identity           ---> There is an element 1 in S such that a1 = 1a = a for all in S.
  10- No zero division                 ---> if a,b in S and ab=0, then either a=0 or b=0.
  11- Multiplication inverse          ---> 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.
  
  Polynomial Representation :
  
  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
  
  Mathematical operations (addition and multiplication) :
  
  - Addition operation in polynomial representation in GF(2^8) Form :
  
  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                          ----> 1
  249 = 11111001 = x^7+x^6+x^5+x^4+x^3+1    ----> 2
  (x^7+2x^6+x^5+2x^4+x^3+x+2)mod(2)
  remove 2 coefficients (2x^6+2x^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) Form :
  
  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) form :
  
  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                             -----> 1
  249 = x^6+x^6+x^5+x^4+x^3+x+1   -----> 2
  
  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^5+x^4+x     Remainder = x^5+x^4+x^3+x^2+1
  x^8+x^4+x^3+x+1
  
  The result
  = x^5+x^4+x^3+x^2+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) form https://github.com/Hamza-Megahed/gf-calculator
  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.