Basic Algebra Theory for Advance Encryption Standards (AES)

Basic Algebra Theory for Advance Encryption Standards (AES) 

Outline:

1. Group

2. Ring 

3. Integral Domain

4. Field

5. Galois Field

1. Group : A group 'G' is denoted as {G, .} is defined over binary operation '.' such that . : GxG-->G follows the below axioms

1.1 Closure : if a, b E G then a.b E G.   

1.2 Associative : If a.(b.c) = (a.b).c      for all a,b,c E G.

1.3 There exists an element e such that

1.3.1 Identity : a.e=e.a=e                for all a E G

1.3.2 Inverse : a.A = A.a = e             for all a,A E G   {Here A = inverse of a}

1.x Abelian Group : Every Group is called abelian group if it follows the following additional Criterion: 

1.x.1 Commutative : a.b = b.a    for all a,b E G

Note 1:                                                                                                                                                      

 --if only 1.1 and 1.2 satisfies is called semigroup. example : {N,+} where N belongs to the set of natural numbers.                                                                                                                                      

 -- if only 1.1, 1.2, and 1.3.1 satisfies is called monoid. example : {W, +} where W belongs to the set of whole numbers.                                                                                                                                            

-- Example of Group is {S,+} where S is the set of set of Even numbers. 

2. Ring : A ring 'R' is denoted as {R,+,*} with two binary +,* such that +,* : RxR-->R follows the below axioms

2.1 {R,+} should be abelian group.

2.2 {R,*} should be semigroup.

2.3. Operation * should be distributed over +.                                                                                                                                           i.e. a(b+c) = ab+ac

Example : 1. {S,+,x} where S is the set of Even numbers and +, x are the addition and multiplication operations.                                                                                                                                                  

2. {M,+,x} Here M is the set of square matrices defined over Real numbers. 

3. Integral Domain : {R,+,*} is called integral domain if it satisfies the following properties

3.1 {R,+} should be an abelian group.

3.2 The operation * is commutative. Furthermore, if c!=0 and c.a=c.b then a=b and 0 is the additive identity,

3.3 The Operation * is distributed over +.

Example : {Z,+,x} where Z is the set of integers.

4. Field : {F,+,*} is called field if it follows the following properties:

4.1 {F,+} should be an abelian group.

4.2 {F-{0},x} should be an abelian group.

4.3 The operation x is distributed over +. 

Example : 1. {I,+,x} here I is the set of real numbers.                                                                              

                  2. {M,+,x} here M be the square Invertible Matrix over real numbers. 

5. Galois Field : A field that contain finite number of elements and it always prime or power of a prime.  i.e. GF(2^p) where p E {1,2,3,-----n}.

if p>1 is called the extended galois field. 

since Z(8), Z(256) are not a field but GF(2^3), and GF(2^8) are galois field. 

Note 2:                                                                                                                                                      

-- In AES we use GF(2^8) but the calculation part of GF(2^8) is quite long so will deal with the GF(2^3) in this blog. The procedure regarding the calculation is same but for time consuming purpose i will use GF(2^3) for calculation portion.                                                                                                  

-- In Galois field the addition operation is used as bitwise E-Xor. 

Proof GF(2^3) is a field. 

GF(2^3) = {000,001,010,011,100,101,110,111}   or                                                                                     {0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1}        or                                                                                     {0,1,2,3,4,5,6,7}

since irreducible polynomial of degree 3 are {x^3+x^2+1, and x^3+x+1}. 

But when we compute the Galois field with x^3+x^2+1 then it doesn't hold the property of field so x^3+x+1 is consider for the Calculation of GF(2^3).

So under addition operation {Here I'm using decimal representation and in actual the addition is done by bitwise E-Xor}

+	0	1	2	3	4	5	6	7
0	0	1	2	3	4	5	6	7
1	1	0	3	2	5	4	7	6
2	2	3	0	1	6	7	4	5
3	3	2	1	0	7	6	5	4
4	4	5	6	7	0	1	2	3
5	5	4	7	6	1	0	3	2
6	6	7	4	5	2	3	0	1
7	7	6	5	4	3	2	1	0

 so under Multiplication operation 

×	1	2	3	4	5	6	7
1	1	2	3	4	5	6	7
2	2	4	6	3	1	7	5
3	3	6	5	7	4	1	2
4	4	3	7	6	2	5	1
5	5	1	4	2	7	3	6
6	6	7	1	5	3	2	4
7	7	5	2	1	6	4	3

Since this shows that this is a field. 

Note 3: 

   -- Suppose under addition operation say (7 + 4) or ((x^2+x+1)+(x^2)) or (111+100) is (3) or (x+1) or (011).

  --  Suppose under multi plication say (7 x 4) or ((x^2+x+1) x (x^2)) or (111 x 100) is (1) or (1) or (001). Entire procedure shown below..

Note 4 : In case of AES we deal with GF(2^8). There are total of 30 irreducible polynomial of degree 8 but we choose (x^8+x^4+x^3+x+1) because it shows the properties of field.