1.GF(2)域上的多项式

　　在有限域GF(28)中的元素操作运算可采用几种不同的方法来表示，AES算法主要选择传统的多项式表示法进行的。因为不同的表示对GF(28)的运算复杂度是有影响的。

　　一个由b7b6b5b4b3b2b1b0组成的字节b可表示成系数为[0, 1]的二进制多项式

　　b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x1 + b0

　　例如：十六进制数“6B”对应的二进数为01101011，作为一个字节对应于多项式为：

　　x6 + x5 + x3 + x + 1

　　1.1.多项式加法

　　在GF(28)上的加法定义为二进制多项式的加法，其系数满足模2加(即异或)。例如：“6B”和“71”的和为：6B + 71 = 1A，或采用多项式记法:

　　(x6 + x5 + x3 + x + 1) + (x6 + x5 + x4 +1) = x4 + x3 + x

　　显然，多项式加法与以字节为单位的比特异或结果是一致的。

　　1.2.多项式的乘法

　　在GF(28)上的乘法(用符节“.”表示)定义为二进制多项式的乘积以8次不可约多项式为模的积，此8次不可约多项式为：

　　m(x) = x8 + x4 + x3 + x + 1

　　十六进制为“11B”，二进制表示为100011011，此乘法在GF(28)上满足结合律，且有一个本原元(“01”)，例如：

　　(x6 + x5 + x3 + x + 1)(x6 + x5 + x4 + 1)

　　= x12 + x8 + x6 + x5 + x4 + x + 1(mod m(x))

　　= x7 + x6 + x + 1

　　或者：6B71 = C3

　　显而易见，模的结果是一个低于8阶的多项式，与加法不同的是，乘法并不是在字节上的简单运算。

　　1.3.函数xtime()

　　函数xtime()定义为GF(28)上的xb(x)，若b7 = 0，则字节b左移一位;若b7 = 1，则字节b左移一位，再异或“1B”。

　　设b(x)为GF(28)域中次数小于8的多项式，由欧几里德扩充算法知，存在a(x)和c(x)，满足：

　　a(x)b(x) + c(x)m(x) = 1 ( 2 – 1 )

　　因此有： a(x)b(x)mod m(x) = 1 ( 2 – 2 )

　　或： a(x)b(x) = 1 mod(m(x)) ( 2 – 3 )

　　由此，我们可以获得b(x)的逆元：b-1(x) = a(x) mod m(x)

　　假设：b(x) = b7x7 + b6x6 + x5b5 + b4x4 + b3x3 + b2x2 + b1x1 + b0

　　若把b(x)乘上x，得到：xb(x) = b7x8+ b6x7 + x5b6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x

　　相乘的结果再与m(x)相模的结果有如下规律性：

　　若b7 = 0， 则(b(x)x) mod m(x) = b(x) x

　　若b7 = 0， 则(b(x)x) mod m(x) = (b(x)x) ⊕m(x)

　　由此，(b(x)x) mod m(x)可以被认为是先进行字节的左移操作，根据移位结果对该字节与“1B”(m(x))进行条件异或运算不了。 这种类型的操作记为：b = xtime()。

　　例如：计算6317 = 58

　　计算步骤如下：

　　6317 = 63(01 + 02 + 04 + 10)= 6301 + 6302 + 63 04 + 6310

　　6301 = xtime(63) = C6;(01100011， b7=0， 左移一位)

　　6302 = xtime(C6) = 97;(11000110，b7=1，左移一位，异或1B)

　　6304 = xtime(97) = 35;(10010111，b7=1，左移一位，异或1B)

　　6310 = xtime(35) = 6A;(00110101，b7=0，左移一位)

　　所以，6317 = 6301 + 6302 + 63 04 + 6310

　　= 63 + C6 + 97 + 6A

　　=58

　　这样，通过分解可将复杂的相乘操作转化为简单的移位和异或操作。

　　2.GF(28)域上的多项式

　　在有限域GF(28)上的多项式系统定义为取自GF(28)元素的多项式，则一个4字节的字对应于一个次数小于4的多项式。

　　2.1.加法运算

　　GF(28)上的多项式的加法定义为对应项系数相加，即两个带有系数的多项式之各等于相应系数之和的多项式，在GF(28)上的和运算等于异或运算。

　　2.2.乘法运算

　　带有系数的多项式相乘与不带系数的多项式相乘相比，稍为复杂一些。设在GF(28)上有两个多项式：

　　a(x) = a3x3 + a2x2 + a1x + a0

　　b(x) = b3x3 + b2x2+ b1x + b0

　　两者关于模x4+1的乘积为：c(x) = a(x) ⊕ b(x) = c3x3 + c2x2 + c1x + c0

　　其中系数由下面4个式子得到：

　　c0 = a0b0⊕a3b1⊕a2b2⊕a1b3

　　c1 = a1b0⊕a0b1⊕a3b2⊕a2b3

　　c2 = a2b0⊕a1b1⊕a0b2⊕a3b3

　　c3 = a3b0⊕a2b1⊕a1a2⊕a0b3

　　很显然，一个固定多项式a(x)与多项式b(x)相乘所构成的运算可以用矩阵乘法表述：

　　c0 a0 a3 a2 a1 b0

　　c1 a1 a0 a3 a2 b1

　　c2 = a2 a1 a0 a3 b2

　　c3 a3 a2 a1 a0 b3

　　其中的矩阵是一个循环矩阵。应当注意，M(x) = x4 + 1 不是GF(28)上的不可约多项式(也不是GF(2)上的不可约多项式)，因为x4 + 1 = (x +1)(x3 + x2 + x +1)。所以，被一个固定多项式相乘的乘法不一定是可逆的。在AES算法中，乘法算法只限于乘一个固定的有逆元的多项式a3x3 +b2x2 +b1x + b0才能进行乘法，从而保证乘法的可逆性。

3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/