抽象代数

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

AES加密的数学基础

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

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

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

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

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

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

抽象代数基础

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

代数结构入门：群、环、域、向量空间

群

群

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

如果G满足:

A1封闭性:$\mathrm{\forall }a,b\in G\to a·b\in b$

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

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

A4逆元:$\mathrm{\forall }a\in G,\text{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交换律:$\mathrm{\forall }a,b\in G,a·b=b·a$

群G+A5=交换群G

l

环

环

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

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

如果R再满足

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

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

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

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

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

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

则称R为环

交换环

如果环R再满足

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

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

则称R为交换环

整环

如果交换环R再满足

M5乘法单位元:$\text{exist}e,\mathrm{\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无零因子,:$\mathrm{\forall }a,b\in R,a\times b=0\to a=0orb=0$

则称R为整环

怎么理解"无0因子"?

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

比如

$$A=\left[\begin{array}{c}000\\ 000\\ 001\end{array}\right]B=\left[\begin{array}{c}001\\ 000\\ 000\end{array}\right]$$ 又如,

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

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

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

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

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

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

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

域

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

M7乘法逆元:$\mathrm{\forall }a\ne 0\in R,\text{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:GaloisField$,伽罗华域

$p$:表示一个正素数

$\oplus :\mathrm{\forall }a,b\in Z_p,a\oplus b=(a+b)modp$即模p加法

$\otimes :\mathrm{\forall }a,b\in Z_p,a\otimes b=(a\times b)modp$即模屁乘法

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

当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 nmodN=0$

如果$n^2!=N$,则$\text{exist}{n}^{\prime }\in (1,N),n{n}^{\prime }=N$那么$n\otimes n^{\prime }=n{n}^{\prime }modN=NmodN=0$

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

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

$\mathrm{\forall }a\in Z_p,a\otimes x=1$,即$ax\equiv 1(modp)$,显然当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乘法	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6	7
2	0	2	4	6	0	2	4	6
3	0	3	6	1	4	7	2	5
4	0	4	0	4	0	4	4	3
5	0	5	2	7	4	1	6	3
6	0	6	4	2	4	3	4	2
7	0	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_n{x}^n+a_{n-1}{x}^{n-1}+...+a_{1}x+a_0=\sum _{i=0}^n{a}_i{x}^i,a_n\ne 0$$ 如果$\mathrm{\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$

设 $$\begin{gathered} f(x)=\sum _{i=0}^n{a}_i{x}^i \\ g(x)=\sum _{i=0}^m{b}_i{x}^i \\ {a}_n{b}_m\ne 0,n\ge m \end{gathered}$$ 则普通多项式的加法运算 $$f(x)+g(x)=\sum _{i=0}^m(a_i+b_i)x^i+\sum _{i=m+1}^n{a}_i{x}^i$$ 普通多项式乘法 $$\begin{gathered} f(x)g(x)=\sum _{i=0}^{n+m}{c}_i{x}^i \\ {c}_i=a_0{b}_i+a_1{b}_{i-1}+...+a_i{b}_0 \end{gathered}$$

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

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

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

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

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

比如对于$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$上的两个多项式 $$\begin{gathered} f(x)=\sum _{i=0}^n{a}_i{x}^i \\ g(x)=\sum _{i=0}^m{b}_i{x}^i \\ {a}_n,b_m\ne 0,n\ge m \end{gathered}$$

$Z_p$多项式的四则运算

则$Z_p$上的多项式加法(减法类似)为 $$\begin{gathered} f(x)+g(x)=\sum _{i=0}^m(a_i\oplus b_i)x^i+\sum _{i=m+1}^n{a}_i{x}^i \\ =\sum _{i=0}^m(a_i+b_i)modp\times x^i+\sum _{i=m+1}^n{a}_i{x}^i \end{gathered}$$

$Z_p$上的多项式乘法为 $$\begin{gathered} f(x)g(x)=\sum _{i=0}^{n+m}{c}_i{x}^i \\ {c}_i=(a_0{b}_i+a_1{b}_{i-1}+...+a_i{b}_0)modp \end{gathered}$$ $Z_p$上的带余式除法 $$f(x)=q(x)g(x)+r(x)$$ 意思是$f(x)÷g(x)=q(x)...r(x)$

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

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

定义$d(x)$是$a(x),b(x)$的最大公因式,即$d(x)$是能够整除$a(x),b(x)$的所有多项式中次数最高的 $$gcd(a(x),b(x))=gcd[b(x),a(x)\mathrm{\%}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$上的多项式$modm(x)$都会落在次数小于等于n-1的多项式集$F$中

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

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

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

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

下面证明M6无零因子

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

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

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

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

到此F被证明是整环

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

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

$f(x)g(x)\equiv 1(modm(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)$上的乘法逆元

$$\begin{gathered} f(x)g(x)\equiv 1(modm(x)) \\ g(x)f(x)+k(x)m(x)=1 \\ gcd(f(x),m(x))=1 \end{gathered}$$

显然可以将整数上的拓展欧几里得推广到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)\mathrm{mod}m(x)$

拆分成项

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

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

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

求$f(x)\times x\mathrm{mod}m(x)$

假设$f(x)=a_7{x}^7+a_6{x}^6+...+a_{1}x+a_0$表示$GF(2^8)$上的任意多项式

则$x\times f(x)=a_7{x}^8+a_6{x}^7+...+a_{0}x$

如果用二进制表示,那么 在还没有取模时,我们可以发现$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_6{x}^7+a_5{x}^6+...+a_{0}x$,

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

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

求$x^8\mathrm{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(\mathrm{系}\mathrm{数}mod2)$$ 此时用$x^8+2x^7+2x^6+...+2x+2$去$\mathrm{mod}m(x)$终于可以大干一场了,还得是门当户对地干,次数相同的项单挑

$x^8\equiv x^8+2x^7+2x^6+...+2x+2(\mathrm{系}\mathrm{数}mod2)$作为被除数,$m(x)$作为除数,余数即为所求结果

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

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

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

这是巧合吗?

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

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

在战争之前我们把"累赘的尾部$a_6{x}^7+a_5{x}^6+...+a_{0}x$"留下不参战,原因是他们参战也会被敌人$m(x)$直接劝返

现在我们知道了精锐的头部$x^8$和累赘的尾部$a_6{x}^7+a_5{x}^6+...+a_{0}x$各自参战的结果了,此时可以总结一支部队$x\times f(x)=x^8+a_6{x}^7+a_5{x}^6+...+a_{0}x$参战的结果了: $$x\times f(x)\mathrm{mod}m(x)=[m(x)-x^8]+a_6{x}^7+a_5{x}^6+...+a_{0}x$$ 比如当$f(x)=x^7+x^4+x^2+x+1,m(x)=x^8+x^4+x^3+x+1$时 $$\begin{array}{rl}& x\times f(x)\mathrm{mod}m(x)\\ & =(x^8+x^5+x^3+x^2+x)\mathrm{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{array}$$ 到此我们知道$x\times f(x)\mathrm{mod}m(x)$如何计算了,

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

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

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

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

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

总结

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

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

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

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

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