## 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.
The text passage provides an overview of finite fields in the context of cryptography, including definitions, properties, and examples of operations in Galois Fields (GF). It includes several examples of addition and multiplication in GF(2^8).
multiple_questions_with_answers

the passage contains multiple examples of mathematical operations, such as addition and multiplication in gf(2^8), and provides answers to these operations.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
## 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.
user
The text passage provides an overview of finite fields in the context of cryptography, including definitions, properties, and examples of operations in Galois Fields (GF). It includes several examples of addition and multiplication in GF(2^8).

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS

The passage contains multiple examples of mathematical operations, such as addition and multiplication in GF(2^8), and provides answers to these operations.