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.

This came up when I read FIPS-197, "Advanced Encryption Standard." It
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

See also

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

... they are talking about this polynomial:

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

And when they write ...

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

... they are talking about this polynomial:

     (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.

If you have any questions about this or need more help, please write back
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/