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,使\forall a\in F,\ a+0=a,\ a\cdot 1=a \\ &(6)\qquad\forall a\in F,a\not=,\exists -a,a^{-1}使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，就可以表示成以下形式：

$x^6+x^4+x^2+x+1$

接下来我们来看看$GF(256)$上的运算

加法

我们有两个数0x57和0x83，它们都是$GF(256)$的元素。把0x57+0x83用上面所述的方式表达出来，有下面的式子：

$(x^6+x^4+x^2+x+1)+(x^7+x+1)=x^7+x^6+x^4+x^2+2x+2$

但是由于$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，我们用多项式形式表示出来：

$\begin{align*} (x^6+x^4+x^2+x+1)(x^7+x+1)\qquad=\qquad& x^{13}+x^{11}+x^9+x^8+x^7+ \\ & x^7+x^5+x^3+x^2+x+ \\ & x^6+x^4+x^2+x+1 \\ =\qquad& x^{13}+x^{11}+x^9+x^8+x^6+x^5+x^4+x^3+1 \end{align*}$

然后：

$(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+x_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_0 \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_0 \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_0 \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\quad a_3\quad a_2 \quad a_1\\ a_1\quad a_0\quad a_3 \quad a_2\\ a_2\quad a_1\quad a_0 \quad a_3\\ a_3\quad a_2\quad a_1 \quad 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)$，那么我们有：

$b(x)=b_3x^3+b_2x^2+b_1x+b_0\\ c(x)=b_2x^3+b_1x^2+b_0x+b_3\\$

把他们转换为二进制形式，可以看到$c$就是将$b$左环移一位得到的结果，也就是说左环移就是在$GF(256)$上乘以0x01。

GF(256)有什么用？

$GF(256)$上的四则运算是AES加密算法的数学基础，在密码学中有广泛应用。

参考资料：

The Rijndeal Block Cipher

维基百科-有限域

维基百科-域)