Associated Topics || Dr. Math Home || Search Dr. Math

### Inverses in the Field GF(2^8) in AES

```Date: 03/29/2010 at 05:49:17
From: Monica
Subject: Inverses in the Field GF(2^8) in AES

Dear Dr. Math:

I know how to compute the inverse of a polynomial. For example, if I use
the irreduciale polynomial ...

X^8 + X^4 + X^3 + X + 1,

... then the inverse of ...

X^6 + X^4 + X + 1

is

X^7 + X^6 + X^3 + X.

But how do I compute the inverse if the coefficient is not only {00} and
{01}? For example, what is the inverse of this polynomial?

{03}X^3 + {01}X^2 + {01}X + {02}

There's a lot of stuff on the Internet, but I can't find details about my
specific problem. I asked my friend who has a doctorate, but I still don't
know how to compute such inverses.

In my job, I just to do programming. The theory is hard for me to
understand -- but I still need to know how the inverse is to be computed.

tells us the inverse of ...

{03}X^3 + {01}X^2 + {01}X + {02}

is

{0B}X^3 + {0D}X^2 + {09} + {0E}

Thanks very much!

```

```
Date: 03/30/2010 at 16:57:47
From: Doctor Vogler
Subject: Re: Inverses in the Field GF(2^8) in AES

Hi Monica,

Thanks for writing to Dr Math. That's a good question.

I think that most of the confusion comes from the fact that the FIPS
document uses the same variable (x) for both an element of GF(2^8) and for
a polynomial with coefficients in GF(2^8). I think it would have been
clearer to use different variables for those two types of polynomials. So
let me explain again -- without using x.

AES deals with elements of the finite field GF(2^8), which are polynomials
in t, the coefficients of which are elements of the finite field GF(2), or
the integers mod 2, modulo the polynomial

t^8 + t^4 + t^3 + t + 1.

I think you understand what this field is, so I won't belabor the point,
though I will remind you that the notation {xy} used in FIPS -- where xy
is a 2-digit hex number -- refers to an element of this field, with each
bit corresponding to a coefficient. So, for example, some elements of
GF(2^8) are

{00} = 0
{01} = 1
{02} = t
{03} = t + 1
...
{6d} = t^6 + t^5 + t^3 + t^2 + 1

http://mathforum.org/library/drmath/view/66982.html

Then AES deals with polynomials the coefficients of which are elements of
the finite field GF(2^8), modulo the reducible polynomial X^4 + 1.

So when they write ...

{03}X^3 + {01}X^2 + {01}X + {02},

(t + 1)X^3 + X^2 + X + t

And when they write ...

{0B}X^3 + {0D}X^2 + {09} + {0E},

(t^3 + t + 1)X^3 + (t^3 + t^2 + 1)X^2
+ (t^3 + 1)X + (t^3 + t^2 + t)

If you multiply those two polynomials together . ..

(t + 1)X^3 + X^2 + X + t
* (t^3 + t + 1)X^3 + (t^3 + t^2 + 1)X^2
+ (t^3 + 1)X + (t^3 + t^2 + t),

... you get this polynomial:

(t^4 + t^3 + t^2 + 1)X^6
+ (t^4 + t^2 + t + 1)X^5
+ (t^4 + t^3 + t + 1)X^4
+ (t^4 + t)*X^3
+ (t^3 + t + 1)X^5
+ (t^3 + t^2 + 1)X^4
+ (t^3 + 1)X^3
+ (t^3 + t^2 + t)*X^2
+ (t^3 + t + 1)X^4
+ (t^3 + t^2 + 1)X^3
+ (t^3 + 1)X^2
+ (t^3 + t^2 + t)*X
+ (t^4 + t^2 + t)X^3
+ (t^4 + t^3 + t)X^2
+ (t^4 + t)X
+ (t^4 + t^3 + t^2)

=

(t^4 + t^3 + t^2 + 1)X^6
+ (t^4 + t^3 + t^2)X^5
+ (t^4 + t^3 + t^2 + 1)X^4
+ (t^4 + t^3 + t^2 + 1)X^2
+ (t^4 + t^3 + t^2)X
+ (t^4 + t^3 + t^2)

And if you reduce this mod X^4 + 1, you get ...

(t^4 + t^3 + t^2 + 1)X^2
+ (t^4 + t^3 + t^2)X
+ (t^4 + t^3 + t^2 + 1)
+ (t^4 + t^3 + t^2 + 1)X^2
+ (t^4 + t^3 + t^2)X
+ (t^4 + t^3 + t^2)

... which equals 1.

Does this make sense? I hope it clears things up.

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Modern Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search