Revision as of 08:16, 19 June 2015

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} $

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 $. Find $ A(x) + B(x) \in GF(2^8) $.

$ A(x) + B(x) = x^6 + 2 \bmod 2 x^3 + x + 2 \bmod 2 = x^6 + x $

Notice that addition modulo 2 is equivalent to an XOR gate.

Multiplication in extension fields is more complicated because when you multiply polynomials you end up with higher powers so it is possible to end up outside the finite field. Similar to modular arithmetic with numbers, we will need to do a modulo reduction. For example, $ 3*5 \pmod {10} = 15 \pmod {10} \equiv 5 \bmod {10} $. We know we must divide by 10 and take the remainder because 10 is the modulus but what is the modulus in an extension field? It turns out we may use any irreducible polynomial of degree m as our modulus. Therefore in order to multiply elements in an extension field, we must multiply using regular polynomial multiplication and then divide my some irreducible polynomial of degree m and take the remainder. Making different choices of irreducible polynomials for the modulus results in equal extension fields under isomorphism but in order to keep things simple, a specific irreducible polynomial is specified for AES. For AES, the irreducible polynomial is $ P(x) = x^8+x^4+x^3+x+1 $.

Example 1.3 : Let $ A(x), B(x) \in GF(2^8) $ where $ A(x) = x^6+x^3+1 $ and $ B(x) = x^3+x+1 $. Find $ A(x)*B(x) \in GF(2^8) $.

$ (x^6+x^3+1)(x^3+x+1)=x^9+x^7+x^4+x+1 $

Notice that $ x^9+x^7+x^4+x+1 $ is not in $ GF(2^8) $ so we must divide by $ P(x) $.

When we divide we get a remainder of $ x^7+x^5+x^2+1 $.

References

• C. Paar. Understanding Cryptography. Lecture Notes. Dept. of Electr. Eng. and In­for­ma­ti­on Sci­en­ces, Ruhr University.
• C. Paar and J. Pelzl. Understanding Cryptography. A textbook for Student and Practitioners. Springer 2010.

Questions and comments

If you have any questions, comments, etc. please post them here.

Back to 2015 Summer Cryptography Paar