抽象代数

参考教材:密码编码学与网络安全

AES加密的数学基础

第一遍读感觉教材上对数学基础(群环域,多项式运算)P72-P91给的莫名奇妙

然后参考了知乎回答对群环域的解释

此时第二遍读教材,发现其实教材在讲每一部分的开始都写了为什么要讲.

学习这部分一定要明确目的,在陷入定理的证明时或者公式应用时时刻想想是在干什么

引入多项式构造$GF(p^n)$这一想法真的太神奇了,将整数上的数论定理应用于多项式也真的太神奇了

另,教材P74页的图4.2是有错误的

抽象代数基础

图片来自代数结构入门：群、环、域、向量空间 - 知乎 (zhihu.com)

群

$<G,·>$表示一个定义了二元关系$·$的集合(注意这里$·$不一定是乘号,可以是所有二元关系的抽象表示)

如果G满足:

A1封闭性:$\forall a,b\in G\rightarrow a·b\in b$

A2结合律:$\forall a,b\in G,a·(b·c)=(a·b)·c$

A3单位元:$\exist e\in G,\forall a\in G,e·a=a·e=a$

A4逆元:$\forall a\in G,\exist a^{-1},a·a^{-1}=a^{-1}·a=e$

这里$^{-1}$不是一定是-1次幂,只是逆元的表示形式

集合G+A1+A2+A3+A4=群G

<Z,+>就是一个群

<N,+>就不是一个群,因为如果定义单位元是0,那么1的逆元就是-1,但是-1不在自然数范围内,满足A1A2A3但是不满足A4的代数系统被称为幺半群

变换群

设A是一非空集合,G是A到A的映射集合,如果G关于运算*构成一个群,则称$<G,✳>$是集合A上的一个变换群,简称变换群

置换群

设A是一非空有限集合,则A上的一个变换群就是A的一个置换群,简称置换群

交换群

A5交换律:$\forall a,b\in G,a·b=b·a$

群G+A5=交换群G

环

$<R,+,\times>$R是一个有两种二元运算的集合,这两种二元运算分别为加法$+$和乘法$\times$

已知$<R,+>$是交换群

如果R再满足

M1乘法封闭性:$\forall a,b\in R,a\times b\in R$

M2乘法结合律:$\forall a,b,c\in R,a\times (b\times c)=(a\times b)\times c$

M3乘法对加法的分配律:$\forall a,b,c\in R,\begin{cases}a\times (b+c)=a\times b+a\times c\(a+b)\times c=a\times c+b\times c\end{cases}$

注意这里没有写$a \times (b+c)=(b+c)\times a$

因为这样写实际上是满足乘法交换律,而满足分配律不一定满足交换律,比如矩阵乘法

矩阵的左右乘结果一般是不一样的,但是矩阵乘法对矩阵加法是有结合律的

则称R为环

交换环

如果环R再满足

M4乘法交换律:$\forall a,b,c\in R,(a\times b)\times c=a\times (b\times c)$

显然$R_n(Q)$是环但不是交换环

则称R为交换环

整环

如果交换环R再满足

M5乘法单位元:$\exist e,\forall a\in R,e\times a=a\times e=a$

当$R=S$为整数时,$e=1$

当$R=R_n(Q)$,n阶实数矩阵集合,$e=E(n)$n阶单位矩阵

M6无零因子,:$\forall a,b\in R,a\times b=0\rightarrow a=0\ or\ b=0$

则称R为整环

怎么理解”无0因子”?

显然$R_n(Q)$不满足M6,因为两个矩阵$A,B$乘积是个0矩阵并不能说明$A$或者$B$矩阵有至少一个是零矩阵

比如

$$
A=\begin{bmatrix}
0\ 0\ 0\
0\ 0\ 0\
0\ 0\ 1\
\end{bmatrix}\ \ \ \ \
B=\begin{bmatrix}
0\ 0\ 1\
0\ 0\ 0\
0\ 0\ 0\
\end{bmatrix}
$$
又如,

令$Z_6={0,1,2,3,4,5}$,

定义$Z_6$上的乘法$\otimes$为$a\otimes b=(a\times b\ )mod\ 6$

定义$Z_6$上的加法$\oplus$为$a\oplus b=(a+b)mod\ 6$

显然$Z_6$满足$A_1-A_5,M_1-M_5$

但是$<Z_6,+,\times>$不满足无零因子,比如

$2\otimes 3=(2\times 3)mod \ 6=6mod\ 6=0$

就是说,0这个元素一定也是在集合R中存在的,并且乘法运算结果为0一定和引入这个元素0有关

域

设$<R,+,\times>$为一个整环,如果R再满足

M7乘法逆元:$\forall a≠0\in R,\exist a^{-1}\in R,a\times a^{-1}=1$则称$a^{-1}$为a的乘法逆元

注意乘法逆元也是$R$中的

定义乘法逆元的作用实际上是可以使用除法,除以一个数等于乘以该数的乘法逆元

比如对于$<Z_7,+,\times>$,由拓展欧几里得定理可知,由于模数为7是一个质数,因此0到6都存在$Z_7$上的mod 7意义下的乘法逆元

再比如全体整数就不是任何元素都有乘法逆元,只有1和-1有乘法逆元,任何绝对值大于1的整数其乘法逆元应该是分数,不属于整数.

则称R为域F

有限域GF(p)

符号意义:

$GF(p)=<Z_p,\oplus,\otimes >$

$GF:Galois Field$,伽罗华域

$p$:表示一个正素数

$\oplus:\forall a,b\in Z_p,a\oplus b=(a+b)\ mod\ p$即模p加法

$\otimes : \forall a,b\in Z_p,a\otimes b=(a\times b)\ mod\ p$即模屁乘法

为什么一定要求是一个素数?

当N为一个合数的时候$Z_N={1,2,3,…,N-2,N-1}$不满足$M_6$无零因子,不是整环,因此不是域

为什么不满足$M_6$?

由已知,N是合数,则至少存在$n\in Z_N,1<n<N,n|N$

如果$n^2=N$,则有$n\otimes n=n\times n\ mod\ N=0$

如果$n^2!=N$,则$\exist n’\in (1,N),nn’=N$那么$n\otimes n’=nn’\ mod\ N=N\ mod \ N=0$

故选取p为素数,就是为了保证$M_6$无零因子

同时,选取一个素数作为mod值,保证了$M_7$乘法逆元:

$\forall a\in Z_p,a\otimes x=1$,即$ax\equiv 1(mod\ p)$,显然当p为一个素数时有$gcd(a,p)=1$由2拓展欧几里得定理即可求出x的值

因此$Z_p$就是一个有限域,用$GF(p)$表示

$Z_p$上的数论定理

拓展欧几里得定理求乘法逆元

int exgcd(const int &a, const int &b, int &x, int &y) {//拓展欧几里得算法ax+by=1=gcd(a,b)
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int x2, y2;
	int d = exgcd(b, a % b, x2, y2);
	x = y2;
	y = x2 - a / b * y2;
	return d;
}

int inverse(const int &a, const int &mod) {//求a在模mod下的逆元
	int x, y;
	exgcd(a, mod, x, y);
	return ((x % mod) + mod) % mod;
}

快速幂


int quick_pow(const int &base, const int &index, const int &mod) {//bash^index(% mod)
	if (index == 0)
		return 1;
	else if (index == 1)
		return base % mod;
	else if (index % 2) {
		return quick_pow(base * base % mod, index >> 1, mod) % mod;
	} else {
		return base * quick_pow(base * base % mod, index >> 1, mod) % mod;
	}
}

多项式算术

为什么突然扯到”多项式算数”呢?

前面我们证明了对于整数集$Z_N={0,1,2,3,…,N-1}$,只有当$|Z_N|=N$为素数p时,$Z_p$才为一个域

如果想要得到一个元素个数为$2^n$的域,显然$Z_p$做不到.

为什么要得到一个元素个数为$2^n$的域?计算机使用二进制编码,AES加密算法就用到了$GF(2^8)$

一个3位二进制数可以表示8中状态,明文和密码就在这八种状态之中

模8乘法	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	4	3
5	5	2	7	4	1	6	3
6	6	4	2	4	3	4	2
7	7	6	5	3	3	2	1

在$Z_8$中的数字乘法,其结果中个数字的出现次数显然是不均匀的,比如1出现了4次,2就出现了8次

而一个理想的密码是不能暴露词频信息的,显然用$Z_8$上的变换进行加密不理想,于是想一种乘法和除法的构造方法, 使得有8个元素的域其乘法或者加法的结果的频率相等

而使用多项式运算就可以解决这个问题,因此引入了多项式运算

首先要研究的是==如何构造一个有8个元素($p^n$)的域==

==将数的性质拓展到多项式式上==

我们使用的一般是代数基本规则的普通多项式运算

然后拓展到系数在$GF(p)$中的多项式运算

然后再拓展到系数在$GF(p)$,模一个$n$次多项式$m(x)$的多项式运算

最终目标是理解并应用最后一种多项式

普通多项式运算

多项式次数:最高次项的次数

多项式的表示:
$$
f(x)=a_nx^n+a_{n-1}x^{n-1}+…+a_1x+a_0=\sum_{i=0}^na_ix^i,a_n≠0
$$
如果$\forall a_i\in S$则称$f(x)$是系数集$S$上的多项式,令$<A,+,\times >$表示S上的所有多项式以及加法和乘法二元关系

当$S=Z$表示整数集的时候,显然A是满足$A_1-A_5,M_1-M_6$,是个整环,

但是不满足乘法逆元,比如$x$的乘法逆元$x^{-1}$,是一个指数为负的多项式,显然不在$A$

设
$$
f(x)=\sum_{i=0}^na_ix^i\
g(x)=\sum_{i=0}^mb_ix^i\
a_nb_m≠0,n\ge m
$$
则普通多项式的加法运算
$$
f(x)+g(x)=\sum_{i=0}^m(a_i+b_i)x^i+\sum_{i=m+1}^na_i x^i
$$
普通多项式乘法
$$
f(x)g(x)=\sum_{i=0}^{n+m}c_ix^i\
c_i=a_0b_i+a_1b_{i-1}+…+a_ib_0
$$

系数在$Z_p$中的多项式运算

当系数集是全体整数的时候,由于系数不都有乘法逆元,因此无法进行多项式除法

当系数集是一个域的时候,系数都有了乘法逆元,可以对多项式引入除法(带余除法)

可以类比整数的除法,求余数用$%$,求商用$/$

那么在$Z_p$中的多项式,求余式用$%$,求商式用$/$

比如对于$Z_2$上的多项式$f(x)=x^4+1=(x+1)(x^3+x^2+x+1)$,则$f(x)/(x+1)=x^3+x^2+x+1$

设系数域为$<Z_p,\oplus,\otimes >$

设$Z_p$上的两个多项式
$$
f(x)=\sum_{i=0}^na_ix^i\
g(x)=\sum_{i=0}^mb_ix^i\
a_n,b_m≠0,n\ge m
$$

$Z_p$多项式的四则运算

则$Z_p$上的多项式加法(减法类似)为
$$
f(x)+g(x)=\sum_{i=0}^m(a_i\oplus b_i)x^i+\sum_{i=m+1}^na_i x^i\
=\sum_{i=0}^m(a_i+ b_i)mod\ p\ \times x^i+\sum_{i=m+1}^na_i x^i
$$

$Z_p$上的多项式乘法为
$$
f(x)g(x)=\sum_{i=0}^{n+m}c_ix^i\
c_i=(a_0b_i+a_1b_{i-1}+…+a_ib_0)mod\ p
$$
$Z_p$上的带余式除法
$$
f(x)=q(x)g(x)+r(x)
$$
意思是$f(x)\div g(x)=q(x)…r(x)$

以$Degree(f)$表示多项式f的阶,并且$Degree(f)=n,\
Degree(g)=m,\$则有$Degree(q)=n-m\
Degree(r)\le m-1$

$Z_p$多项式的欧几里得定理

定义$d(x)$是$a(x),b(x)$的最大公因式,即$d(x)$是能够整除$a(x),b(x)$的所有多项式中次数最高的
$$
gcd(a(x),b(x))=gcd[b(x),a(x)%b(x)]
$$

$Z_p$上多项式再mod n次素多项式

对于$Z_p$上次数高于n-1的多项式$f(x)$,需要mod一个$Z_p$上的n次素多项式$m(x)$,如此限制$f(x)$的次数在$[0,n-1]$

什么是”素多项式”?$Z_p$上的素多项式$m(x)$无法被$Z_p$上的任意多项式整除

当$m(x)$的次数为n,则$Z_p$上的多项式$mod\ m(x)$都会落在次数小于等于n-1的多项式集$F$中

显然$F$中的多项式都可以表示为
$$
\forall f(x)\in F,f(x)=a_0+a_1x+…+a_{n-1}x^{n-1},\forall a_i\in Z_p
$$
那么这样的多项式一共有$p^n$个(系数的乘法原理),即模$m(x)$构成的剩余类

现在类比$Z_p$,证明$F$是一个域

显然加减乘封闭且结合律分配律交换律均满足,$F$容易判定为交换环

由于1也是$F$中的多项式,因此存在乘法单位元1,

下面证明M6无零因子

由于k阶多项式的k次项系数不为零,假设有两个非零多项式,其最高次项分别为$a_ix^i,b_jx^j$

乘积多项式的最高次项为$a_ib_jx^{i+j}$如果指数$i+j\ge n$则对$m(x)$取模,如果系数$a_ib_j\ge p$则对$p$取模

显然p是一个素数,$a_ib_j=a_i\times b_j$是一个合数,合数对素数取模显然不为0

因此任何两个非零多项式乘积一定非零,M6无零因子得证

到此F被证明是整环

无零因子就是$GF(2^3)$是域但是$Z_8$不是域的本质原因

下面证明任意F中的非0多项式都在F中有乘法逆元

$f(x)g(x)\equiv 1(mod\ m(x))$

$g(x)f(x)+k(x)m(x)=1$

又$m(x)$为素因式,有欧几里得定理知上式有解

因此M7乘法逆元得证

因此$F$是域

$F$和$Z_p$的不同

我们在证明$Z_p$是域的时候发现,对于整数集$Z_N={0,1,2,3,…,N-1}$,只有当$|Z_N|=N$为素数p时,$Z_p$才为一个域

而现在$|F|=p^n$显然当$n>1$时是一个合数,但是$F$仍然是一个域

将$F$记作$GF(p^n)$表示伽罗华域

$F=GF(p^n)$上的乘法逆元

$$
f(x)g(x)\equiv 1(mod \ m(x))\
g(x)f(x)+k(x)m(x)=1\
gcd(f(x),m(x))=1
$$

显然可以将整数上的拓展欧几里得推广到F上

$GF(2^n)$上构造结果分布均匀的二元运算

$GF(2^n)$上的多项式各项的系数要么是0,要么是1,可以用二进制数表示

比如$x^3+x^2+1$就可以表示为1101

加法

由于系数要么是0要么是1,即系数要自动对2取模

那么多项式的加法就是二进制数按位异或

比如$(x^3+x^2+x)+(x^4+x+1)=x^4+x^3+x^2+2x+1=x^4+x^3+x^2+1$

$01110\oplus 10011=11101$

乘法

教材上一本正经地写了一堆用字母表示的多项式,看上去头大.

从一个例子入手可能比较容易理解:

考虑AES加密算法使用到的$GF(2^8)$,取$m(x)=x^8+x^4+x^3+x+1$为模.

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

$g(x)=x^7+x+1$

求$f(x)\otimes g(x)=f(x)\times g(x)\mod m(x)$

拆分成项

容易想到的是把$g(x)$按幂次拆分成项然后用f(x)与g(x)的各项相乘之后相加,而相加在”加法”中我们已经认识到可以通过两个多项式异或这种简洁的方式实现,因此我们现在把精力放在$f(x)$如何和一个$x^k$项相乘上
$$
f(x)\times g(x)\mod m(x)\
=f(x)\times(1+x+x^7)\mod m(x)\
=f(x)\times 1\mod m(x)+f(x)\times x\mod m(x)+f(x)\times x^7\mod m(x)
$$
问题转化为如何求$f(x)\times x^k\mod m(x)$

求$f(x)\times x^k\mod m(x)$

由于
$$
f(x)\times x^k\mod m(x)\
={[(f(x)\times x\mod m(x))\times x\mod m(x)]\times …\times x\mod m(x)}\times x\mod m(x)
$$
因此问题又可以转换为怎么跨出求$f(x)$到$f(x)\times x\mod m(x)$这第一步

求$f(x)\times x\mod m(x)$

假设$f(x)=a_7x^7+a_6x^6+…+a_1x+a_0$表示$GF(2^8)$上的任意多项式

则$x\times f(x)=a_7x^8+a_6x^7+…+a_0x$

如果用二进制表示,那么
$$
f(x)=&a_7&a_6&a_5&a_4&a_3&a_2&a_1&a_0\
x\times f(x)=a_7&a_6&a_5&a_4&a_3&a_2&a_1&a_0&0
$$
在还没有取模时,我们可以发现$f(x)$到$x\times f(x)$只需要将$f(x)$的二进制表示左移一位,下面考虑如何取模

如果$a_7=0$则$x\times f(x)$顶多是一个7次多项式,如果有$a_6=0$则顶多是一个6次多项式,一个七次多项式$x\times f(x)$去mod一个8次多项式$m(x)$实乃以卵击石,直接被8次多项式劝返

如果$a_7=1$则$x\times f(x)$与$m(x)$都是8次多项式,算是旗鼓相当,可以一战

此时$x\times f(x)$可以分成精锐的头部$x^8$与累赘的尾部$a_6x^7+a_5x^6+…+a_0x$,

这个尾部对$m(x)$取模还是被劝返,只留下精锐的头部$x^8$独自抗衡$m(x)$

那么问题转化为$x^8$对$m(x)=x^8+x^4+x^3+x+1$取模,考虑如何取模?

求$x^8 \mod m(x)$

$x^8$形单影只,只能单挑$m(x)$的$x^8$项,无暇处理$m(x)$的一伙子小弟,

于是$x^8$利用其系数都在$GF(2)$上,无中生有搬来了一伙子小弟:
$$
x^8\equiv x^8+2x^7+2x^6+…+2x+2(系数mod 2)
$$
此时用$x^8+2x^7+2x^6+…+2x+2$去$\mod m(x)$终于可以大干一场了,还得是门当户对地干,次数相同的项单挑

$x^8\equiv x^8+2x^7+2x^6+…+2x+2(系数mod 2)$作为被除数,$m(x)$作为除数,余数即为所求结果

战争一开始,商1之后被除数减去除数得到$2x^7+2x^6+2x^5+x^4+x^3+2x^2+x+1\equiv x^4+x^3+x+1(系数mod2)$

立刻发现刚才”精锐的头部”那个$x^8$在和$m(x)$的8次项的决斗中阵亡了,剩下的小弟都是7次方以下的项,无力与$m(x)$抗衡,直接作为余数

即刚才的”战争”可以写为:
$$
x^8\equiv x^4+x^3+x+1 \mod m(x)&系数mod2\
其中m(x)=x^8+x^4+x^3+x+1
$$
突然发现$x^8\mod m(x)=m(x)-x^8=x^4+x^3+x+1$

这是巧合吗?

这是系数mod2的必然结果,并且可以从8次推广到n次:

$m(x)$为n次多项式
$$
x^n\mod m(x)=m(x)-x^n(系数mod2)
$$
$x^8$独自面对$m(x)$,最终壮烈牺牲但是换回$x^4+x^3+x+1$颇有”将军百战死,壮士十年归”的感觉

在战争之前我们把”累赘的尾部$a_6x^7+a_5x^6+…+a_0x$”留下不参战,原因是他们参战也会被敌人$m(x)$直接劝返

现在我们知道了精锐的头部$x^8$和累赘的尾部$a_6x^7+a_5x^6+…+a_0x$各自参战的结果了,此时可以总结一支部队$x\times f(x)=x^8+a_6x^7+a_5x^6+…+a_0x$参战的结果了:
$$
x\times f(x)\mod m(x)=[m(x)-x^8]+a_6x^7+a_5x^6+…+a_0x
$$
比如当$f(x)=x^7+x^4+x^2+x+1,m(x)=x^8+x^4+x^3+x+1$时
$$
\begin{aligned}
&x\times f(x)\mod m(x)\
&=(x^8+x^5+x^3+x^2+x)\mod (x^8+x^4+x^3+x+1)\
&=[x^4+x^3+x+1]+[x^5+x^3+x^2+x]\
&=011011\oplus 101110\
&=110101
\end{aligned}
$$
到此我们知道$x\times f(x)\mod m(x)$如何计算了,

那么$x^2\times f(x)\mod m(x)=x\times (x\times f(x)\mod m(x))\mod m(x)$

以此类推可以得到$x^k\times f(x)\mod m(x)$如何计算了

回到求$f(x)\times g(x)\mod m(x)$

不管你$g(x)$长什么样,我先预处理出$f(x)\times x\mod x,f(x)\times x^2\mod m(x),f(x)\times x^k\mod m(x)$等等情况

如果你$g(x)=1+x+x^2$长得很虚,那么
$$
f(x)\times g(x)\mod m(x)\
=f(x)\times (1+x+x^2)\mod m(x)\
=(f(x)+x\times f(x)+x^2\times f(x))\mod m(x)\
=f(x)+x\times f(x)\mod m(x)+x^2\times f(x)\mod m(x)
$$
直接利用预处理得出的结果,然后计算加法直接用二进制异或

总结

到此我们构造出了$GF(2^n)$,即有$2^n$个元素的伽罗华域

怎么构造出的?由系数在$GF(2)$上的多项式模一个$2^n$次的素多项式拓展出的

多项式和这$2^n$个数怎么产生联系?每一个多项式都对应一个二进制数

这$2^n$个数的加减乘除运算怎么定义的?还是通过多项式的运算得到的

下一步可以向AES加密算法进军了

模8乘法	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	4	3
5	5	2	7	4	1	6	3
6	6	4	2	4	3	4	2
7	7	6	5	3	3	2	1

模8乘法	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	4	3
5	5	2	7	4	1	6	3
6	6	4	2	4	3	4	2
7	7	6	5	3	3	2	1

模8乘法	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	1	2	3	4	5	6	7
2	2	4	6	0	2	4	6
3	3	6	1	4	7	2	5
4	4	0	4	0	4	4	3
5	5	2	7	4	1	6	3
6	6	4	2	4	3	4	2
7	7	6	5	3	3	2	1