有限域

GF(28)的定义

假设一个字节bb7b6b5b4b3b2b1b0组成,我们可将bi看作一个7次多项式的系数,而这些系数不是0就是1:

b7 x7+ b6 x6+ b5 x5+ b4 x4+ b3 x3+ b2 x2+ b1 x + b0

例如,(57)16的二进制表示法为(0101,0111)2表示成多项式,则为:

x6+ x4+ x2+ x + 1.

加法

两个多项式的加法,则是定义为相同指数项的系数和再模2,简单的说就是作XOR运算(如, 1+1=0)。例如:

(57)16+(83)16=(01010111)2+(10000011)2 = (11010100)2 = (D4)16

或是(x6+x4+x2+x+1) + (x7+x+1) = x7+x6+x4+x2

乘法

在乘法里面,多项式相乘之后的结果很容易造成溢位的问题,解决溢位的方式是把相乘的结果,再模余一个不可分解的多项式m(x)。在Rijndael中,定义一个这样子的多项式为

m(x)=x8+x4+x3+x+1或是(11B)16

例如:

(57)16(83)16 = ( x6+ x4+ x2+ x + 1)(x7+ x + 1)

= x13+ x11+ x9+ x8+ x7+x7+ x5+ x3+ x2+x+x6+ x4+ x2+ x + 1

= (x13+ x11+ x9+ x8+ x6+ x5+ x4+ x3+ 1)

                        (x7+ x6+ 1)mod (x8+ x4+ x3+ x + 1)=(C1)16

若把b(x)乘上x,得到b7 x8+ b6 x7+ b5 x6+ b4 x5+ b3 x4+ b2 x3+ b1 x2 + b0x

若b7=0,不会发生溢位问题,答案即是正确的;

若b7=1,发生溢位问题,必须减去m(x)。

我们可以把这种运算表示为xtime(x),其运算方式为left shift(若溢位,则和(1B)16做XOR运算),例如:

‘57’ • ‘13’ = ‘FE’

‘57’ • ‘02’ = xtime(57) = ‘AE’

‘57’ • ‘04’ = xtime(AE) = ‘47’

‘57’ • ‘08’ = xtime(47) = ‘8E’

‘57’ • ‘10’ = xtime(8E) = ‘07’

‘57’ • ‘13’ = ‘57’ • (‘01’⊕‘02’⊕‘10’) = ‘57’ ⊕ ‘AE’ ⊕ ‘07’ = ‘FE’

原文地址:https://www.cnblogs.com/whl2012/p/3341725.html