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
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.

No comments:

Post a Comment