伽罗瓦域

依旧是网事如烟云的密码学专栏中讲述的内容，这个专栏对于几种常见密码算法的介绍比较详细，我阅读了之后有了许多收获。

这篇文章将描述一下密码学中常用的有限域(伽罗瓦域)。

域的概念

首先，假设你有部分基础，即简单了解过群、环、域，那么你可以通过下方的简述快速复习一下相关的概念，如果没有基础，请寻找一些公开课，例如信安数学基础，学习一下群的相关内容再继续阅读。

群(group)

群的概念可以理解为：一个集合以及定义在这个集合上的二元运算，满足群的四条公理，封闭性、结合性、单位元、反元素。

交换群就是在满足群的”四公理“的基础上还满足交换律，通常把满足交换律的群称作阿贝尔群(Abelian Group)，如整数集合和加法运算，$(Z,+)$，是一个阿贝尔群。

环(ring)

环在阿贝尔群的基础上，添加一种二元运算乘法$\cdot$​​(虽叫乘法，但不同于初等代数的乘法)。一个代数结构是环$(R, +, \cdot)$​，

域(field)

域在交换环的基础上，还增加了二元运算除法，要求元素(除零元以外)可以作除法运算，即每个非零的元素都要有乘法逆元。如有理数集合、实数集合、复数集合都是域。而显然，整数集合不是域，因为两个整数相除，有可能得到分数。

有限域，顾名思义，就是该域中只包含有限个元素。有限域中元素的个数，称为有限域的阶。如果有限域的阶可以表示为$p^n$，其中，p 是素数，n 是正整数，那么该有限域通常被称为伽罗瓦域（Galois Field，GF），记为 $GF(p^n)$。

有限域的计算

一切有限域都有加法和乘法两种运算，并必须满足以下条件：

1．封闭性：若任意两元素 $a \cdot b \in GF(q)$，则有

$$\begin{aligned} a + b \in GF(q) \\ a \cdot b \in GF(q) \end{aligned}$$

2．结合律：若任意 $a , b , c \in GF(q)$​​，则有

$$\begin{aligned} ( a + b ) + c &= a + ( b + c ) \\ ( a \cdot b ) \cdot c &= a \cdot ( b \cdot c ) \end{aligned}$$

3．交换律：若任意 $a , b \in GF(q)$​​，则有

$$\begin{aligned} a + b &= b + a \\ a \cdot b &= b \cdot a \end{aligned}$$

4．有乘法恒等元 e 和加法恒等元 0 ，使任意元素 $a \in GF(q)$​​​都有：

$$\begin{aligned} a + 0 &= a \\ a \cdot e &= a \end{aligned}$$

5．任意元素 $a \in GF(q) $​​都有乘法逆元素 $a^{-1}$​​ 和加法负元素$-a$​​，使

$$\begin{aligned} a + (-a) &= 0 \\ a \cdot a ^ {-1} &= e \end{aligned}$$

但$0^{-1}$无定义。

6．乘对加分配律：任意 $a , b , c \in GF(q)$​有

$$a \cdot ( b + c ) = a \cdot b + a \cdot c$$

$GF(2^8)$​域上的加法与乘法

加法

在伽罗华域中，加法是模2运算，也就是忽略进位的加法，等同于位运算中的异或。

乘法

本原多项式 (primitive polynomial)是一种特殊的不可约多项式。当一个域上的本原多项式确定了，这个域上的运算也就确定了。本原多项式一般通过查表得知，同一个域往往有多个本原多项式。

AES加解密算法中，使用的不可约多项式(irreducible polynomial)为$P(x)=x^8 + x^4 + x^3 + x + 1$​，下面将基于该多项式讲述$GF(2^8)$​域上的乘法实现。

$GF(2^M)$上的乘法运算是基于多项式运算的，比如 $5 = 00000101b = ( 2^2 + 1)$，对应的多项式为 $x^2+1$​

$$\begin{aligned} 3*7 &= (x+1)(x^2+x+1) \\ &= x^3 + x^2 + x + x^2 + x + 1 \\ &= x^3 + (x^2 + x^2) + (x+x) + 1 \\ &= x^3 + 1 \end{aligned}$$

因为加法为模2运算，所以相同项相加为0，所以减法可以当成加法来计算。

在相乘得到的多项式结果中，如果x的次数大于7，就需要对多项式在GF域上关于本原多项式 $P(x)$​​​ 求余数，即$\mod P(x)$​

$$\begin{aligned} 129 * 5 &= (x^7+1)(x^2+1) \\ &= x^9 + x^7 + x^2 + 1 \\ &= (x^9 + x^7 + x^2 + 1) + (x*P(x)) \\ &= (x^9 + x^7 + x^2 + 1) + (x^9 + x^5 + x^4 + x^2 + x) \\ &= x^7 + x^5 + x^4 + x + 1 \\ &=\text{10110011b} \\ &=\text{0xB3} \\ &= 179 \end{aligned}$$