| Line 91: | Line 91: | ||
In AES, we use <math> GF(2^8) </math> which has exactly 256 elements each corresponding to a polynomial of the form <math> A(x) = a_{7}x^{7} + a_{6}x^{6} + a_{5}x^5 + a_4x^4+a_3x^3+a_2x^2 + a_1x + a_0 </math>. We can equivalently consider these as 8-bit vectors of the form <math> <a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0> </math>. | In AES, we use <math> GF(2^8) </math> which has exactly 256 elements each corresponding to a polynomial of the form <math> A(x) = a_{7}x^{7} + a_{6}x^{6} + a_{5}x^5 + a_4x^4+a_3x^3+a_2x^2 + a_1x + a_0 </math>. We can equivalently consider these as 8-bit vectors of the form <math> <a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0> </math>. | ||
| + | |||
| + | Addition and subtraction in extension fields are performed the same as polynomial addition and subtraction with coefficients modulo p. | ||
| + | |||
| + | ''Example 1.2'': Let <math> A(x), B(x) \in GF(2^8) </math> where <math> A(x) = x^6+x^3+1 </math> and <math> B(x) = x^3+x+1 </math> | ||
| + | |||
==[[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 07:34, 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
A prime field $ GF(p) $ is represented by the numbers 0 through p-1.
$ 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 |
Note that additive and multiplicative inverses can be read of the tables.
Extension Fields
Extension fields are a bit more complicated. An element $ A(x) $ in an extension field $ GF(p^m) $ is described by a polynomial as follows:
$ A(x) = a_{m-1}x^{m-1} + a_{m-2}x^{m-2} + ... + a_1x + a_0 $ where $ a_i \in GF(p) $
In AES, we use $ GF(2^8) $ which has exactly 256 elements each corresponding to a polynomial of the form $ A(x) = a_{7}x^{7} + a_{6}x^{6} + a_{5}x^5 + a_4x^4+a_3x^3+a_2x^2 + a_1x + a_0 $. We can equivalently consider these as 8-bit vectors of the form $ <a_7,a_6,a_5,a_4,a_3,a_2,a_1,a_0> $.
Addition and subtraction in extension fields are performed the same as polynomial addition and subtraction with coefficients modulo p.
Example 1.2: Let $ A(x), B(x) \in GF(2^8) $ where $ A(x) = x^6+x^3+1 $ and $ B(x) = x^3+x+1 $
Questions and comments
If you have any questions, comments, etc. please post them here.
Back to 2015 Summer Cryptography Paar
