AES加密(2)：GF(256)域
从域的定义出发理解 AES 的数学基础 GF(256)：多项式表示、加法、乘法与 xtime。
GF(256)域是一个有限域，在密码学中非常常用
什么是有限域/伽罗瓦域(Galois Field)?
顾名思义，有限域就是含有有限个元素的域。
既然是含有有限个元素的域，那么关键点就在于有限和域两个概念。
首先我们看一下域的定义(来自维基百科):
在抽象代数中，域(Field)是一种可以进行加，减，乘，除（除了除以加法单位元“0”）运算的代数结构。域的概念是数域以及四则运算的推广。
在这里加法和乘法并不是我们所熟悉的加法和乘法。我们把这个域记作\(F\)，其中加法和乘法满足以下几种特性：
\[\begin{align*} &(1)\qquad\forall a,b\in F,\ a+b\in F,\ a\cdot b\in F \\ &(2)\qquad\forall a,b\in F,\ a+b=b+a,\ a\cdot b=b\cdot a \\ &(3)\qquad\forall a,b,c\in F,\ (a+b)+c=a+(b+c),\ (a\cdot b)\cdot c=a\cdot (b\cdot c) \\ &(4)\qquad\forall a,b,c\in F,\ a\cdot (b+c)=a\cdot b+a\cdot c \\ &(5)\qquad\exists 0,1\in F,\ \text{使}\forall a\in F,\ a+0=a,\ a\cdot 1=a \\ &(6)\qquad\forall a\in F,a\not=0,\exists -a,a^{-1}\text{使}a+(-a)=0,a\cdot a^{-1}=1 \end{align*}\]这其中(1)描述了加法与乘法的封闭性，(2),(3),(4)则是我们所熟悉的交换律、结合律和分配律，而(4),(5)分别是对单位元与逆元的定义。
看到这，我们可以很容易的发现：实数集就是一个满足域的定义的集合。确实，域的概念就是由数域推广发展而来的。
但是很显然，实数域并不是一个有限的域。
那么有限域又是怎么回事呢？
有限域显而易见也是满足域的定义的一个集合，但是这个集合却是一个有限集。在有限域上定义的加和乘仍然满足封闭性。这看起来不可能，但实际上这样的域是存在的。有限域中元素的个数叫做阶，任意有限域的阶必然是一个素数的幂。
那GF(256)又是什么呢？
\(GF(256)\)，就是阶为256的有限域。因为\(2^8=256\)，所以这个域是存在的。
在\(GF(256)\)中的任意元素都可以表示成以下形式：
\[b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0\]其中\(b_i\in\{0,1\}\)。比如说十六进制数0x57，转换为二进制之后是01010111，就可以表示成以下形式：
接下来我们来看看\(GF(256)\)上的运算
加法
我们有两个数0x57和0x83，它们都是\(GF(256)\)的元素。把0x57+0x83用上面所述的方式表达出来，有下面的式子：
但是由于\(b_i\in\{0,1\}\)，所以结果里的每一项的系数都要模2，也就是变为他除以二的余数，得到：
\[x^7+x^6+x^4+x^2\]再将其变回16进制形式得到0xd4。我们把这种运算记作\(a\oplus b\)。
注意到0x57 ^ 0x83=0xd4，这里^指异或。所以我们可以知道\(\oplus\)与异或是同种运算。
这里看起来有点草率，但这是有道理的。因为异或本质上就是不带进位的二进制加法，而\(\oplus\)运算也一样，所以这两种确实就是同种运算。
乘法
首先我们得到\(GF(2^8)\)的本原多项式：
\[m(x)=x^8+x^4+x^3+x+1\]由此得到在\(GF(256)\)上，\(x^8=x^4+x^3+x+1\) （在\(GF(256)\)上加法与减法是同一种运算，这是由于异或运算是自己的逆运算导致的）。
现在我们有两个数0x57和0x83，我们用多项式形式表示出来：
然后：
\[(x^{13}+x^{11}+x^9+x^8+x^6+x^5+x^4+x^3+1) \bmod (x^8+x^4+x^3+x+1)=x^7+x^6+1\]得到最终结果0xc1
可以证明这种运算在\(GF(256)\)上满足分配律。
xtime函数
我们定义函数xtime，其中xtime(a)=a·0x02 ，也就是说这个函数的返回值 (或者说是因变量) 是这个函数的参数 (自变量) 在\(GF(256)\)上与0x02的乘积。
那这有什么用呢？
我们又有两个数0x57和0x13，要求他们在\(GF(256)\)上的积
首先我们知道：
xtime(0x57)=0xAE
xtime(0xAE)=0x47
xtime(0x47)=0x8E
xtime(0x8E)=0x07然后我们应用分配律有:
\[57\cdot 13=57\cdot(01\oplus 02\oplus 10)=57\oplus AE\ \oplus 07\]这样可以简化计算。
GF(256)上的多项式乘法
我们现在有两个多项式如下：
\[\begin{align*} &a(x)=a_3x^3+a_2x^2+a_1x+a_0\\ &b(x)=b_3x^3+b_2x^2+b_1x+b_0 \end{align*}\]接着又有一个多项式\(c(x)=a(x)b(x)\)，于是有：
\[\begin{align*} c(x)\quad&=\quad c_6x^6+c_5x^5+c_4x^4+c_3x^3+c_2x^2+c_1x+c_0 \\ c_0 \quad&=\quad a_0\cdot b_0 \\ c_1 \quad&=\quad a_1\cdot b_0\oplus a_0\cdot b_1 \\ c_2 \quad&=\quad a_2\cdot b_0\oplus a_1\cdot b_1\oplus a_0\cdot b_2 \\ c_3 \quad&=\quad a_3\cdot b_0\oplus a_2\cdot b_1\oplus a_1\cdot b_2 \oplus a_0\cdot b_3\\ c_4 \quad&=\quad a_3\cdot b_2\oplus a_2\cdot b_2\oplus a_1\cdot b_3 \\ c_5 \quad&=\quad a_3\cdot b_2\oplus a_2\cdot b_3 \\ c_6 \quad&=\quad a_3\cdot b_3 \end{align*}\]我们再定义一个多项式 (这个多项式也是\(GF(16)\)上的本原多项式) ：
\[M(x)=x^4+1\]将\(c(x)\)模去\(M(x)\)，得到多项式\(d(x)\)：
\[\begin{align*} d(x)\quad&=\quad d_3x^3+d_2x^2+d_1x+d_0 \\ d_0 \quad&=\quad a_0\cdot b_0\oplus a_3\cdot b_1\oplus a_2\cdot b_2\oplus a_1\cdot b_3\\ d_1 \quad&=\quad a_1\cdot b_0\oplus a_0\cdot b_1\oplus a_3\cdot b_2\oplus a_2\cdot b_3\\ d_2 \quad&=\quad a_2\cdot b_0\oplus a_1\cdot b_1\oplus a_0\cdot b_2\oplus a_3\cdot b_3\\ d_3 \quad&=\quad a_3\cdot b_0\oplus a_2\cdot b_1\oplus a_1\cdot b_2\oplus a_0\cdot b_3 \end{align*}\]同时也可以写成：
\[\left[ \begin{array}{c} d_0\\ d_1\\ d_2\\ d_3 \end{array} \right]= \left[ \begin{array}{cccc} a_0 & a_3 & a_2 & a_1\\ a_1 & a_0 & a_3 & a_2\\ a_2 & a_1 & a_0 & a_3\\ a_3 & a_2 & a_1 & a_0 \end{array} \right] \left[ \begin{array}{c} b_0\\b_1\\b_2\\b_3 \end{array} \right]\]我们把这种运算记作\(\otimes\)，即\(a(x)\otimes b(x)=d(x)\)
现在我们设\(c(x)=x\otimes b(x)\)，那么我们有：
\[\begin{aligned} b(x)&=b_3x^3+b_2x^2+b_1x+b_0\\ c(x)&=b_2x^3+b_1x^2+b_0x+b_3 \end{aligned}\]把他们转换为二进制形式，可以看到\(c\)就是将\(b\)左环移一位得到的结果，也就是说左环移就是在\(GF(256)\)上乘以0x01。
GF(256)有什么用？
\(GF(256)\)上的四则运算是AES加密算法的数学基础，在密码学中有广泛应用。
参考资料：