Question

How to find multiplicative inverse in gf 2 8?

Answer 1

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






2 How do I find the multiplicative inverse in GF(2^8) using extended Euclidean algo? Please elaborate on choosing values of a and b?

Answer

2

Interesting

Request

More

1 ANSWER

John Falvey

Answered Jun 13, 2016

2^8 = 256 = a mod b , pick a,b such that gcd( a ,b) =1 

256 = 25 mod 33 , gcd( 25, 33) =1 ,   ( what is GF ?)

We must find the inverse of 25 mod 33

We need an x ,such that x(25) = 1 mod 33
of course from the outset we know that x = 4 ,in so far as that 
 4(25) = 100 =1 mod 33

Now use the algo. Starting with step (0) we will calculate an auxiliary number p(I) where

p(I)  = p(i-2) - p(i-1)×q(i-1) mod n ,   q is each quotient at each step of the algorithm. ,and p(0)=0 and p(1)=1

It is necessary that the final remainder is 1 ,otherwise the process will not work. We know from above that (25,33) will work.

33 = q(1)25 +r(1) ,       step (0)
33 = (1)(25) +8 ,           p0)=0

25  = q(2)(8) +r(2) ,      step (1)
25  =  (3) (8) +1 ,          p(1) =1 (this has nothing to do with r(2)=1)

                                   step (2)
8     =  q(3)(8) + r(3) ,   p(2) = p(0) -p(1)q(1) mod 33
8     =    (1)(8)  + 0  ,      p(2) =  0    -  (1) (1) mod 33  =+32

Go forward one step past the end of the algorithm to p(3) , in this case, in order to get the inverse

p(3) = p(1)-p(2)×q(2) mod n , ( information in steps (1) and (2) above

p(3)  = 1   -   32 × 3 mod 33 = 1 - 96 mod 33

 p(3) = - 95 mod 33 = 4

 p(3) = 4

So the inverse of 25 mod 33 = 4 mod 33

4(25) =100 =1 mod 33

(I don't know what GF above means I hope all of this in not in vain.

If you draw a Cayley diagram you will find that 

G ={ 1,4,16,25,31} , × ,mod 33 is closed and that

4^(-1) = 25 ,      25^(-1) = 4 ,       16^(-1)= 31 and 31^(-1) = 16 mod 33

  Another set can be generated from 256 = 3 mod 11

 F = { 1, 3 , 4 , 5 ,  9 } , × mod 11

3^(-1) mod 11 = 4 mod 11 ,      3(4) =1 mod 11 etc