c3=a3·b©a2·b⊕a1·b2⊕a·b3. The result,c(x),does not represent a four-byte word.Therefore,the second step of the multiplication is to reduce c(x)modulo a polynomial of degree 4;the result can be reduced to a polynomial of degree less than 4.For the AES algorithm,this is accomplished with the polynomialx+1,so that xmod(x+1)=ximod4 (4.10) The modular product of a(x)and b(x),denoted by a(x)b(x),is given by the four-term polynomial d(x),defined as follows: d(x)=dx'+d,x2+d x +do (4.11) with d=(a·b)©(a3·b)©(a2·b2)©(a1·b) d1=(a1·b)©(a·b)⊕(a3·b2)⊕(a2·b3) (4.12) d2=(a2b)©(a1b)©(ab2)⊕(a3b) d3=(a3b)©(a2·b)⊕(a1·b2)©(a·b) When a(x)is a fixed polynomial,the operation defined in equation (4.11)can be written in matrix form as: d ao a;a a 「b d a a2 b (4.13) d az a ao a3 b2 a2 a aoJ儿b」 Because x+1 is not an irreducible polynomial over GF(2),multiplication by a fixed four-term polynomial is not necessarily invertible.However,the AES algorithm specifies a fixed four-term polynomial that does have an inverse (see Sec.5.1.3 and Sec.5.3.3): a(x)={03x3+{01}x2+{01x+{02} (4.14) a'(x)={0bx3+{0d}x2+{09}x+{0e} (4.15) Another polynomial used in the AES algorithm(see the Rotword (function in Sec.5.2)has ao =a=a2={00)and a3=(01),which is the polynomial x.Inspection of equation(4.13)above will show that its effect is to form the output word by rotating bytes in the input word.This means that [bo,b1,b2,b3]is transformed into [bi,b2,b3,bol. 5.Algorithm Specification For the AES algorithm,the length of the input block,the output block and the State is 128 bits.This is represented by Nb=4,which reflects the number of 32-bit words (number of columns)in the State. 1313 3 a3 b0 a2 b1 a1 b2 a0 b3 c = · Å · Å · Å · . The result, c(x), does not represent a four-byte word. Therefore, the second step of the multiplication is to reduce c(x) modulo a polynomial of degree 4; the result can be reduced to a polynomial of degree less than 4. For the AES algorithm, this is accomplished with the polynomial x 4 + 1, so that 4 mod 4 mod( 1) i i x x + = x . (4.10) The modular product of a(x) and b(x), denoted by a(x) Ä b(x), is given by the four-term polynomial d(x), defined as follows: 1 0 2 2 3 3 d(x) = d x + d x + d x + d (4.11) with ( ) ( ) ( ) ( ) d0 a0 b0 a3 b1 a2 b2 a1 b3 = · Å · Å · Å · ( ) ( ) ( ) ( ) d1 a1 b0 a0 b1 a3 b2 a2 b3 = · Å · Å · Å · (4.12) ( ) ( ) ( ) ( ) d2 a2 b0 a1 b1 a0 b2 a3 b3 = · Å · Å · Å · ( ) ( ) ( ) ( ) d3 a3 b0 a2 b1 a1 b2 a0 b3 = · Å · Å · Å · When a(x) is a fixed polynomial, the operation defined in equation (4.11) can be written in matrix form as: ú ú ú ú û ù ê ê ê ê ë é ú ú ú ú û ù ê ê ê ê ë é = ú ú ú ú û ù ê ê ê ê ë é 3 2 1 0 3 2 1 0 2 1 0 3 1 0 3 2 0 3 2 1 3 2 1 0 b b b b a a a a a a a a a a a a a a a a d d d d (4.13) Because 1 4 x + is not an irreducible polynomial over GF(28 ), multiplication by a fixed four-term polynomial is not necessarily invertible. However, the AES algorithm specifies a fixed four-term polynomial that does have an inverse (see Sec. 5.1.3 and Sec. 5.3.3): a(x) = {03}x 3 + {01}x 2 + {01}x + {02} (4.14) a -1(x) = {0b}x 3 + {0d}x 2 + {09}x + {0e}. (4.15) Another polynomial used in the AES algorithm (see the RotWord() function in Sec. 5.2) has a0 = a1 = a2 = {00} and a3 = {01}, which is the polynomial x 3 . Inspection of equation (4.13) above will show that its effect is to form the output word by rotating bytes in the input word. This means that [b0, b1, b2, b3] is transformed into [b1, b2, b3, b0]. 5. Algorithm Specification For the AES algorithm, the length of the input block, the output block and the State is 128 bits. This is represented by Nb = 4, which reflects the number of 32-bit words (number of columns) in the State