Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the concept behind AES's finite field? I understand most of you will laugh at my lack of understanding of the concept. I'm trying to learn a greater amount of higher math concepts and I am implementing AES to do so. I understand that in a basic term, polynomial is an equation of only positive integer expodetials and variables but what does it mean by treated as a polynomial over GF(2^8) and is 2^8, 2 to the power of 8 or 2 XOR 8?

Corrected: from Wikipedia AES

In more general sense, each column is treated as a polynomial over $GF(2^8)$ and is then multiplied modulo $x^4 + 1$ with a fixed polynomial $c(x) = 0x03*x^3 + x^2 + x + 0x02$. The coefficients are displayed in their hexadecimal equivalent of the binary representation of bit polynomials from $GF(2)[x]$.

share|improve this question
2  
It's 2 to the power of 8. A polynomial over $GF(2^8)$ is a polynomial with coefficients in $Z$ modulo $2^8$. Finite means it doesn't have infinitely many elements. $GF(2^8)$ has $2^8$ elements. –  Rudy the Reindeer May 25 '11 at 22:01
3  
@Matt: $\mathbb{Z}/2^8 \mathbb{Z}$ is not a finite field. The finite field with $2^8$ elements has characteristic $2$, for one thing. –  Qiaochu Yuan May 25 '11 at 22:05
    
3  
@Will03uk: I don't know why you expect us to laugh. There is no shame in not knowing things: all of us had to learn these things at some point. The only shame (possibly) is in not being willing to learn. –  Qiaochu Yuan May 25 '11 at 22:15
1  
Willo3uk excerpted the highlighted portion of the post from Wikipedia, leaving out some context, etc. I inserted a link to the AES entry in Wikipedia, and edited the excerpt (with exponents etc intact). I included a sentence which directly followed the original excerpt, which closed the paragraph. Hopefully the edit will be accepted soon so you can "see" the update. –  amWhy May 25 '11 at 22:15

4 Answers 4

up vote 2 down vote accepted

Basic definitions

Before you can understand finite fields, you need to understand what a field is. Fields are algebraic structures, meant to generalize things like the real or rational numbers, where you have two operations, addition and multiplication, such that the following hold:

  • Addition and multiplication are both commutative and associative operations.
  • Multiplication distributes over addition, i.e. $a(b+c)=ab+ac$.
  • There are distinguished elements $0$ and $1$ such that $0+a=a$ and $1*a=a$.
  • For every $a$ we have an element $-a$ such that $a+(-a)=0$. If $a\neq 0$, we have an element $(1/a)$ such that $a(1/a)=1$.

Phrased differently, $(\mathbb{F},+)$ and $(\mathbb{F}\setminus 0,\cdot)$ are abelian groups, and we the operations distribute.

Given a field, we can define a vector space to be an abelian group such that we can multiply vectors by field elements (and we satisfy various associativity and distributivity conditions).

Some examples of fields are the real numbers $\mathbb{R}$, the complex numbers $\mathbb{C}$, the rational numbers $\mathbb{Q}$, and the the integers modulo a prime $\mathbb{F}_p=\mathbb{Z}/(p)$. If $\mathbb{F}$ is a field, then the collection of $n$-tuples of $\mathbb{F}$, written $\mathbb{F}^n$, is a vector space. Every finite dimensional vector space can be written in this form.

Constructing new fields from old ones

Given a field $\mathbb{F}$, we can construct a new field by adding new elements to the $\mathbb{F}$, creating what is called a field extension of $\mathbb{F}$. For example, if we adjoin $\sqrt[3]{2}$ to $\mathbb{Q}$, we get a new field $\mathbb{Q}[\sqrt[3]{2}]$ which is the subset of $\mathbb{R}$ consisting of all elements of the form $a+b\sqrt[3]{2}+c\sqrt[3]{4}$ with $a,b,c\in \mathbb{Q}$. More generally, if we have an irreducible polynomial, we can formally adjoin the root of the polynomial to the field. In the example above, the polynomial would be $x^3-2$.

A field extension of $\mathbb{F}$ is naturally a vector space over $\mathbb{F}$. If it is finite dimensional, it is called a finite field extension. If we obtained the extension by adjoining a single root of a polynomial, the dimension will be the degree of the polynomial, and is called the degree of the extension. Additionally, every finite field extension can be obtained by adjoining elements, possibly several times (in stages).

An example of all this is $\mathbb{Q}[x]/(x^2+x+1)$, where we have adjoined a root of the polynomial $x^2+x+1$ to the rationals. The elements of the field are polynomials with coefficients in $\mathbb{Q}$, modulo the relation that two polynomials represent the same thing if their difference is a multiple of $x^2+x+1$. For example, $(x+1)(x-1)=x^2-1=(x^2-1)-(x^2+x+1)=-x-2$. The fact that we have multiplicative inverses comes from $x^2+x+1$ being irreducible and the Euclidean algorithm.

Finite fields

Suppose that a field $\mathbb{F}_q$ has a finite number of elements $q$. Then considering the sequence of elements $1, 1+1, 1+1+1, \ldots$, we eventually have to get repetition, so we have a smallest number $p$ such that $1+1+\ldots +1$ ($p$ times) is equal to $0$. Thus, the field contains the ring $\mathbb{Z}/(p)$, and because we are a field, it must be the case that $p$ is prime. We call $p$ the characteristic of the field, and we call $\mathbb{F}_p$ the prime field of $\mathbb{F}_q$. Since every finite dimensional vector space can be written as $\mathbb{F}^n$, we must have that $q=p^n$ for some p$.

$\mathbb{F}_q$ is a finite field extension of $\mathbb{F}_p$, and so we can obtain $\mathbb{F}_q$ by adjoining roots of polynomials. It can be shown that every element of $\mathbb{F}_q$ is a root of the polynomial $x^q-x$. If we take just one irreducible factor $f(x)\mid x^q-x$ of maximal degree, then we have $\mathbb F_q=\mathbb{F}_p[x]/(f(x))$ (it doesn't matter which factor we took), and so there is a unique finite field with $q=p^n$ elements. We can obtain it by taking ANY irreducible polynomial of degree $n$ over $\mathbb{F}_p$, and adjoining the root.

The field used in AES

In AES, they have fixed a particular irreducible polynomial of degree 8 over the field $\mathbb{F}_2$. While there are many different choices, you need to have picked one to be able to do computations. By dividing out by this polynomial and taking the remainder, every element of the field is represented uniquely by a polynomial $a_7 x^7 + a_6 x^6 + \ldots +a_0$ with each $a_i= 0 \text{ or } 1$. and the coefficients can be viewed as a byte. Addition is accomplished via XOR, and multiplication comes from taking a certain convolution of two bytes, then subtracting off bitshifts of the defining polynomial.

One subtle point to make is that we have essentially defined our field to be polynomials modulo relations. However, we can define polynomials over this field too by writing out $a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n$ where each $a_0$ is an element of $\mathbb{F}_{256}$ = GF(2^8)$. So we have polynomials whose coefficients are polynomials. Thinking in this way is NOT helpful, and it is better to think of GF(2^8) abstractly, as just some thing that has elements which can be added and multiplied. If you don't abstract the definition of GF(2^8) away, you will end up confusing yourself.

share|improve this answer

I will try to give a layman's terms description; hoping this helps clarify some of your confusions. But you should be warned that this is not a precise definition.

$\mathbb{Z}$ is the set of all integers. $\mathbb{Z}_2$ is the set of all integers modulo 2. That is, ${0,1}.$ Arithmetic operations in $\mathbb{Z}_2$ are performed modulo $2.$ Consider a vector of length 8, whose entries are elements in $\mathbb{Z}_2$. In other words, it's a bit vector of length 8. A given vector $(b_1,b_2,\dots,b_8) \in (\mathbb{Z}_2)^8$ can be represented as a polynomial: $b_1 x^7 + b_2 x^6 + \dots + b_7 x + b_8.$ That is, a polynomial in $x$ with coeffiecients from $\mathbb{Z}_2.$ $\mathrm{GF}(2^8)$ is defined as a set of such vectors (equivalently such polynomials. This is what the article refers to as each column is treated as a polynomial..). In order to construct $\mathbb{Z}_2$ we need the element $2,$ and performed all arithmetic modulo $2.$ If you want to construct $\mathbb{Z}_5,$ will perform operations mod $5$ etc. Similarly, In order to construct $\mathrm{GF}(2^8)$, you need a specific (irreducible) polynomial $p$ of degree $8.$ All arithmetic operations in $\mathrm{GF}(2^8)$ are then performed modulo $p.$

share|improve this answer

Finite fields are constructed by the following : A field has a characteristic, which is the smallest positive integer for which $1 + 1 + .... + 1 = 0$. If this equality never stands the field is said to have characteristic $0$ (for instance, $\mathbb Q$ has characteristic $0$). Since fields are also integral domains, we cannot have a characteristic which is a composite number, so that the characteristic is always a prime number.

Given any prime number, there exists a field of characteristic $p$ : take the numbers $0, 1, ..., p-1$, with addition and multiplication $\mod p$. Those fields are finite because they contain precisely $p$ elements. There are also fields which contain $p^n$ elements for all $n \ge 1$ ; those are called the "splitting fields" of the polynomials $x^{p^n}-x$ over the field I've described just before. It requires a little bit of field theory to understand the concept of splitting fields, but I suggest you read the chapter 13 of the book "Abstract Algebra" by Dummit & Foote, an excellent reference in algebra. Section 13.5 illustrates existence and uniqueness (up to isomorphism) of finite fields.

share|improve this answer

a field, like the real or complex numbers, is a collection of numbers where you can add, subtract, multiply and divide (i.e. you have 0 and 1 and for any element $x$ you have $-x$ and $x^{-1}$). a finite field is is field that consists of finitely many numbers. they necessarily have $p^n$ numbers for some prime $p$ and positive integer $n$ and any two with the same number of elements are isomorphic (basically the same thing).

the easiest way to implement a finite field is to take the collection of polynomials with coefficients from $\{0,1,..,p-1\}$ and do add/sub mult/div using the remainder after division by a fixed irreducible polynomial of degree $n$.

for instance consider $\{0,1\}$ with multiplication and division $0*0=0,0*1=1*0=0,1*1=1$ and addition $0+1=1+0=1, 0+0=0$ (the finite field with two elements). now take the polynomial $x^2+x+1$ which is irreducible (since it is quadratic and has no roots). then the collection of polynomials with $0,1$ coefficients is a finite field with 4 elements with addition and multiplication modulo $x^2+x+1$, i.e. you add/sub mult/div elements as normal and then take the remainder after dividing by $x^2+x+1$. you can identify this with the set of linear polynomials $\{0,1,x,x+1\}$ since if you had degree two or bigger, you could do polynomial division by $x^2+x+1$ to find an equivalent polynomial in this set.

for example:

$x*(x+1)=x^2+x=-1=1$ after dividing by $x^2+x+1$ so we have $1/x=x+1$ and $1/(x+1)=x$ in this field.

getting rid of the $x$'s you can make this into a simple collection of vectors $\{(0,0),(0,1),(1,0),(1,1)\}$ (the coefficient of $x$ in the first spot, the coefficient of $1$ in the second). then the addition is point wise addition (mod 2) and our example of multiplication above becomes $$ (1,0)*(1,1)=(0,1) $$ you could work out the multiplication table as an exercise and then try the same thing with the polynomial $x^3+x+1$ which will give you a field with 8 elements.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.