Multiplicative Inverse in Finite Field GF(2^8)

Date: 02/23/2005 at 06:52:17
From: ambica
Subject: multiplicative inverse in finite field

How do you calculate an s-box which involves

1. the multiplicative inverse in the finite field with the {00} 
element mapped to itself.

2. the affine transformation over GF(2) for Rijndael, the AES 
algorithm in cryptography.

The most confusing part is the calculation of multiplicative inverse 
in the finite field with the {00} element mapped to itself.

I'd like to implement an s-box (without using look up table) going for 
direct calculations.  I'd like to know the steps involved in it, since 
AES sub-bytes operation involves a 4x4 matrix of bytes:

     [B0  B4  B8   B12]
     [B1  B5  B9   B13]
     [B2  B6  B10  B14]
     [B3  B7  B11  B15]

I need to get the multiplicative inverse of this matrix in GF(2^8).  
Is this the same as obtaining the inverse of a 4x4 matrix?

Date: 02/23/2005 at 15:10:50
From: Doctor Vogler
Subject: Re: multiplicative inverse in finite field

Hi Ambica,

Thanks for writing to Dr. Math.  Unfortunately, no, it is not the same
as computing the inverse of a matrix.  Also, there are at least two
issues involved here.  One is what are elements of this finite field
GF(2^8)?  The other is how are they represented on the computer (i.e.
in binary)?  And then we can get to the question of how to invert them.

First of all, an element of GF(2^8) is a polynomial of degree less 
than 8 over GF(2) (with coefficients in GF(2)) modulo an irreducible 
polynomial of degree 8.  So the first thing you have to do is pick a
polynomial of degree 8, and use this as your field modulus.  The AES
standard says what this modulus is.  Then you represent these
polynomials in binary as follows:

  01 = 00000001 = 1
  02 = 00000010 = t
  03 = 00000011 = t + 1
  09 = 00001001 = t^3 + 1
  2b = 00101011 = t^5 + t^3 + t + 1
  6d = 01101101 = t^6 + t^5 + t^3 + t^2 + 1
  8e = 10001110 = t^7 + t^3 + t^2 + t

For example, to multiply two polynomials, you have something like this:

  2b * 09 = (t^5 + t^3 + t + 1) * (t^3 + 1)
          = t^8 + t^6 + t^4 + t^3 + t^5 + t^3 + t + 1
          = t^8 + t^6 + t^5 + t^4 + 2*t^3 + t + 1.

But then since the coefficients are in GF(2), that means that odd
coefficients turn into 1 and even coefficients turn into 0, so this
reduces to

  2b * 09 = t^8 + t^6 + t^5 + t^4 + t + 1.

Finally, you have to reduce modulo your modulus (the irreducible
eighth-degree polynomial).  You should think of the modulus as
equaling zero, and you use it to reduce the degree of the product
below 8.  In this case, you only have to add the modulus to your
polynomial, since the two t^8 terms will cancel, and you have degree
less than 8.  (You should notice that adding two polynomials in this
way is the same as the "xor" operation on your computer.)  More
generally, if the degree of your product is m which is 8 or more, then
you multiply the modulus by t^(m-8) and then add it to your product,
which will reduce the degree of the product by at least one.  Then you
repeat until the degree is less than 8.

If you've understood all of that, then you're on a roll.  (If not,
then you should practice by trying to multiply some elements of
GF(2^8).)  Now comes the hard part.  It will involve a lot of
multiplying and adding in GF(2^8), so make sure you can do those two
operations.

If you are given one polynomial, and you wish to find its inverse mod 
some other polynomial (the eighth-degree irreducible modulus), then
the best way is by the Extended GCD Algorithm, that is, using the
Euclidean Algorithm but keeping track of the coefficients to get

  p(t) a(t) + q(t) m(t) = gcd(a(t), m(t)),

and then if a(t) and m(t) are relatively prime (which will always
happen if m(t) is irreducible and a(t) has lower degree than m(t)),
then the gcd is 1, and so

  a^-1(t) = p(t) mod m(t).

(If they are not relatively prime, then a(t) has no inverse.)

I won't give the details of the Extended Euclidean Algorithm here,
since you can find it by searching our archives or the Internet, and
the only difference between using regular numbers and GF(2^8) numbers
is how you add and multiply.  (Be sure to use a version that uses
subtraction instead of division; subtraction is the same as addition
in GF(2^8) since -1 = 1.)

Also, you can find more details from our archives at

  Inverses in the Field GF(2^8)
    http://mathforum.org/library/drmath/view/51675.html 

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/