Line 45: | Line 45: | ||
==== Prime Fields ==== | ==== Prime Fields ==== | ||
+ | <math> GF(p) = {0,1,2,3,...,p-1} </math> | ||
+ | |||
+ | Addition and Multiplication operations in <math> GF(p) </math> are just performed modulo <math> p </math>. | ||
+ | |||
+ | ''Example 1.1'': <math> GF(5) = {0,1,2,3,4} </math> | ||
+ | {| class="wikitable" border="1" style="border-collapse:collapse;" | ||
+ | |- | ||
+ | ! + !! 0 !! 1 !! 2 !! 3 !! 4 | ||
+ | |- | ||
+ | |''' 0 ''' || 0 || 1 || 2 || 3 ||4 | ||
+ | |- | ||
+ | |''' 1 '''|| 1 || 2 || 3 || 4 || 0 | ||
+ | |- | ||
+ | |''' 2''' || 2 || 3 || 4 || 0 || 1 | ||
+ | |- | ||
+ | |''' 3''' || 3 || 4 || 0 || 1 || 2 | ||
+ | |- | ||
+ | |''' 4''' || 4 || 0 || 1 || 2 || 3 | ||
+ | |} | ||
+ | |||
+ | |||
+ | {| class="wikitable" border="1" style="border-collapse:collapse;" | ||
+ | |- | ||
+ | ! * !! 1 !! 2 !! 3 !! 4 | ||
+ | |- | ||
+ | |''' 1 '''|| 1 || 2 || 3 || 4 | ||
+ | |- | ||
+ | |''' 2''' || 2 || 4 || 1 || 3 | ||
+ | |- | ||
+ | |''' 3''' || 3 || 1 || 4 || 2 | ||
+ | |- | ||
+ | |''' 4''' || 4 || 3 || 2 || 1 | ||
+ | |} | ||
==[[2015_Summer_Cryptography_Paar_Introduction to Galois Fields for AES_Katie Marsh_comments | Questions and comments]]== | ==[[2015_Summer_Cryptography_Paar_Introduction to Galois Fields for AES_Katie Marsh_comments | Questions and comments]]== |
Revision as of 05:40, 11 June 2015
Introduction to Galois Fields for AES
A slecture by student Katie Marsh
Based on the Cryptography lecture material of Prof. Paar.
Contents
Link to video on youtube
Accompanying Notes
Finite Field/Galois Field: a finite set together with operations + and * with the following properties:
1. The set forms an additive group with neutral element 0
2. The set without 0 forms a multiplicative group with neutral element 1
3. The distributive law $ a(b+c)= (ab)+(ac) $
A finite field exist if and only if it has size $ p^m $ where $ p $ is prime and $ m \in \N $
This is to say, there exist a Galois field with 11 elements (11 is prime, m=1) called $ GF(11) $ but you can not construct a Galois field with 12 elements.
There are two distinct types of Galois Fields: Prime Fields and Extension Fields
Prime Field : $ GF(p) $ so m = 1 and the field has a prime number of elements.
Extension Field : $ GF(p^m) $ where m > 1 and the field does not have a prime number of elements.
In AES, the two important fields we need to work with are $ GF(2) $ and $ GF(2^8) $.
Prime Fields
$ GF(p) = {0,1,2,3,...,p-1} $
Addition and Multiplication operations in $ GF(p) $ are just performed modulo $ p $.
Example 1.1: $ GF(5) = {0,1,2,3,4} $
+ | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 0 | 1 | 2 | 3 | 4 |
1 | 1 | 2 | 3 | 4 | 0 |
2 | 2 | 3 | 4 | 0 | 1 |
3 | 3 | 4 | 0 | 1 | 2 |
4 | 4 | 0 | 1 | 2 | 3 |
* | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 1 | 2 | 3 | 4 |
2 | 2 | 4 | 1 | 3 |
3 | 3 | 1 | 4 | 2 |
4 | 4 | 3 | 2 | 1 |
Questions and comments
If you have any questions, comments, etc. please post them here.
Back to 2015 Summer Cryptography Paar