or (01){1b}in hexadecimal notation. For example,(57)83)={c1),because (x6+x4+x2+x+1)(x7+x+1)= xB+x"+x9+x8+x7+ x7+x3+x3+x2+x+ x6+x4+x2+x+1 xB+x1+x9+x8+x6+x3+x4+x3+1 and x3+x+x+x+x+x+x+x3+1 modulo (x+x+x+x+1) =x7+x6+1. The modular reduction by m(x)ensures that the result will be a binary polynomial of degree less than 8,and thus can be represented by a byte.Unlike addition,there is no simple operation at the byte level that corresponds to this multiplication. The multiplication defined above is associative,and the element {01 is the multiplicative identity.For any non-zero binary polynomial b(x)of degree less than 8,the multiplicative inverse of b(x),denoted b"(x),can be found as follows:the extended Euclidean algorithm [7]is used to compute polynomials a(x)and c(x)such that b(x)a(x)+m(x)c(x)=1. (4.2) Hence,a(x).b(x)mod m(x)=1,which means b-(x)=a(x)mod m(x) (4.3) Moreover,for any a(x),b(x)and c(x)in the field,it holds that a(x)·(b(x)+c(x)=a(x)·b(x)+a(x)·c(x). It follows that the set of 256 possible byte values,with XOR used as addition and the multiplication defined as above,has the structure of the finite field GF(25). 4.2.1 Multiplication by x Multiplying the binary polynomial defined in equation(3.1)with the polynomial x results in b7x8+b6x7+b5x6+b4xs+b3x+b2x3+b1x2+box. (4.4) The result x.b(x)is obtained by reducing the above result modulo m(x),as defined in equation (4.1).If b7=0,the result is already in reduced form.If b7=1,the reduction is accomplished by subtracting (i.e.,XORing)the polynomial m(x).It follows that multiplication by x(i.e., (00000010)or (02))can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with (1b).This operation on bytes is denoted by xtime(). Multiplication by higher powers ofx can be implemented by repeated application of xtime(). By adding intermediate results,multiplication by any constant can be implemented. For example,(57).13)={fe)because 1111 or {01}{1b} in hexadecimal notation. For example, {57} · {83} = {c1}, because ( 1) 6 4 2 x + x + x + x + ( 1) 7 x + x + = + + + + + 13 11 9 8 7 x x x x x x + x + x + x + x + 7 5 3 2 1 6 4 2 x + x + x + x + = 1 13 11 9 8 6 5 4 3 x + x + x + x + x + x + x + x + and 1 13 11 9 8 6 5 4 3 x + x + x + x + x + x + x + x + modulo ( 1 8 4 3 x + x + x + x + ) = 1 7 6 x + x + . The modular reduction by m(x) ensures that the result will be a binary polynomial of degree less than 8, and thus can be represented by a byte. Unlike addition, there is no simple operation at the byte level that corresponds to this multiplication. The multiplication defined above is associative, and the element {01} is the multiplicative identity. For any non-zero binary polynomial b(x) of degree less than 8, the multiplicative inverse of b(x), denoted b -1(x), can be found as follows: the extended Euclidean algorithm [7] is used to compute polynomials a(x) and c(x) such that b(x)a(x) + m(x)c(x) = 1. (4.2) Hence, a(x) · b(x) mod m(x) = 1, which means ( ) ( ) mod ( ) 1 b x = a x m x - . (4.3) Moreover, for any a(x), b(x) and c(x) in the field, it holds that a(x) · (b(x) + c(x)) = a(x) · b(x) + a(x) · c(x) . It follows that the set of 256 possible byte values, with XOR used as addition and the multiplication defined as above, has the structure of the finite field GF(28 ). 4.2.1 Multiplication by x Multiplying the binary polynomial defined in equation (3.1) with the polynomial x results in b x b x b x b x b x b x b x b x0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 + + + + + + + . (4.4) The result x · b(x)is obtained by reducing the above result modulo m(x), as defined in equation (4.1). If b7 = 0, the result is already in reduced form. If b7 = 1, the reduction is accomplished by subtracting (i.e., XORing) the polynomial m(x). It follows that multiplication by x (i.e., {00000010} or {02}) can be implemented at the byte level as a left shift and a subsequent conditional bitwise XOR with {1b}. This operation on bytes is denoted by xtime(). Multiplication by higher powers of x can be implemented by repeated application of xtime(). By adding intermediate results, multiplication by any constant can be implemented. For example, {57} · {13} = {fe} because