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

add 1 and 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.