Inverses in the Field GF(2^8)
Date: 11/07/2000 at 07:12:20 From: mmcl Subject: Multiplicative Inverse in GF(2^8) I have 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: 11/07/2000 at 13:40:17 From: Doctor Rob Subject: Re: Multiplicative Inverse in GF(2^8) Thanks for writing to Ask Dr. Math. It is just the same, as long as you do all your arithmetic in GF(2^8). Your first job is to figure out the map that carries bytes into field elements, and vice versa. Map the byte matrix into a field element matrix, do the inversion, then map the result back into bytes. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Date: 11/09/2000 at 05:45:07 From: Maire McLoone Subject: Re: Multiplicative Inverse in GF(2^8) I would like to obtain the multiplicative inverse of each individual byte in GF(2^8). How do I do this?
Date: 11/09/2000 at 11:28:45 From: Doctor Rob Subject: Re: Multiplicative Inverse in GF(2^8) Thanks for writing back. The field GF(2^8) is usually defined in the following way. Find a polynomial f(x) of degree 8 which is irreducible over GF(2). There are 30 of these to choose from. Then the polynomials of degree less than 8 over GF(2) form a set of size 2^8. "Addition" is the usual addition of polynomials (reducing coefficients modulo 2), and "multiplication" is the usual multiplication of polynomials (reducing coefficients modulo 2), followed by a reduction modulo f(x) (and further coefficient reduction modulo 2) until the result has degree less than 8. Using these operations, this set forms a field isomorphic to GF(2^8). For example, suppose the polynomial were f(x) = x^8 + x^6 + x^5 + x + 1 which is irreducible over GF(2). Then to add x^7 + x^3 + x + 1 and x^4 + 1, you would get x^7 + x^4 + x^3 + x + 2, and reducing the coefficients modulo 2, you get x^7 + x^4 + x^3 + x, which is the sum. To multiply these same polynomials, you get: x^11 + 2*x^7 + x^5 + x^4 + x^3 + x + 1 -> x^11 + x^5 + x^4 + x^3 + x + 1 -> x^7 + x^2 + x which is the product. Now suppose one of the entries in your matrix is the byte 11001001. You have to figure out whether this means x^7 + x^6 + x^3 + 1 (so the bits from left to right are the coefficients of the powers of x in decreasing order) or x^7 + x^4 + x + 1 (so the bits from left to right are the coefficients of the powers of x in increasing order). Then you have to determine what polynomial f(x) is being used to do the arithmetic. Once you know these data, you can construct the multiplicative inverses you seek in the following way. First figure out what polynomial a(x) the byte you want to invert is equivalent to. Given a polynomial a(x) whose inverse you seek, perform the Extended Euclidean Algorithm on a(x) and f(x). If a(x) is not zero, you will obtain polynomials r(x) and s(x) such that r(x)*a(x) + s(x)*f(x) = 1 Then reduce this equation modulo f(x): r(x)*a(x) = 1 (mod f(x)) a(x) will be the multiplicative inverse of r(x). Example: Inverse of x^4 + 1. x^8 + x^6 + x^5 + x + 1 = (x^4+x^2+x+1)*(x^4+1) + (x^2) x^4 + 1 = (x^2)*(x^2) + 1 and, working backwards, 1 = 1*(x^4+1) + (x^2)*(x^2) = 1*(x^4+1) + (x^2)*([x^4+x^2+x+1]*[x^4+1]+[x^8+x^6+x^5+x+1]) = (x^6+x^4+x^3+x^2+1)*(x^4+1) + (x^2)*(x^8+x^6+x^5+x+1) so, reducing modulo f(x), 1 = (x^6+x^4+x^3+x^2+1)*(x^4+1) (mod f(x)) Thus the multiplicative inverse sought is x^6 + x^4 + x^3 + x^2 + 1. You can remove the need to work backwards by keeping track of some auxiliary quantities as you perform the Euclidean Algorithm. Remainder Quotient Auxiliary x^8+x^6+x^5+x+1 0 x^4+1 1 x^2 x^4+x^2+x+1 x^4+x^2+x+1 1 x^2 x^6+x^4+x^3+x^2+1 The Auxiliary column always starts with 0 and 1. The Remainder column always starts with f(x) and a(x). To fill in any subsequent row, divide the remainders in the previous two rows, and put the quotient in the Quotient column and the remainder in the Remainder column. Then multiply the quotient times the Auxiliary number in the previous row and add the Auxiliary number in the row before that, putting the result in the Auxiliary column. When the remainder is reduced to 1, the content of the Auxiliary column in that row is the inverse of a(x). This is a version of the Extended Euclidean Algorithm which you can use to advantage here. Of course, once you have the inverse, you have to convert that polynomial back to a byte. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.