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/ |
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/