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
或者:6B·71 = C3
显而易见,模的结果是一个低于8阶的多项式,与加法不同的是,乘法并不是在字节上的简单运算。
1.3.函数xtime()
函数xtime()定义为GF(28)上的x·b(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,得到:x·b(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()。
例如:计算63·17 = 58
计算步骤如下:
63·17 = 63·(01 + 02 + 04 + 10)= 63·01 + 63·02 + 63 ·04 + 63·10
63·01 = xtime(63) = C6;(01100011, b7=0, 左移一位)
63·02 = xtime(C6) = 97;(11000110,b7=1,左移一位,异或1B)
63·04 = xtime(97) = 35;(10010111,b7=1,左移一位,异或1B)
63·10 = xtime(35) = 6A;(00110101,b7=0,左移一位)
所以,63·17 = 63·01 + 63·02 + 63 ·04 + 63·10
= 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才能进行乘法,从而保证乘法的可逆性。
责任编辑:小草