Inverses in the Field GF(2^8) in AESDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/