有限域信安数学

有限域信安数学第1页，课件共35页，创作于2023年2月7.1域的扩张域整环无零因子环含幺环可交换环环Abel群群半群AB表示满足A则满足B除环第2页，课件共35页，创作于2023年2月7.1域的扩张定义7-1非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有单位元的交换环如实数域\复数域\有理数域第3页，课件共35页，创作于2023年2月7.1域的扩张当域元素个数有限时，称为有限域或伽罗瓦galois域,记为GF并把元素的个数称为F的阶，记为GF(n),否则称为无限域最常见:GF(2)两个元素个数相同的有限域一定同构第4页，课件共35页，创作于2023年2月7.1域的扩张如：1、全体整数2、全体偶数3、全体实数4、全体复数5、全体有理数设q为素数，则整数全体关于模q的剩余类在模q的运算下(模q加和乘)构成q阶有限域GF(q)构成环，不构成域构成域构成域构成域构成环，不构成域无限域6、第5页，课件共35页，创作于2023年2月7.1域的扩张子域定义7-2记为F≤A第6页，课件共35页，创作于2023年2月7.1域的扩张定义7-3设F是域，X是F一个子集，那么F中包含X所有子域的交，称为X所生成的子域。所有子域的交:最小子域素域素域也称为极小域任何域都包含一个素域第7页，课件共35页，创作于2023年2月7.1域的扩张这两个例子实际上已刻划了所有的素域。第8页，课件共35页，创作于2023年2月7.1域的扩张有限扩张设F是K的扩域，视F是K上的向量空间，且维数为n，则称F是E上的有限扩张，记为[F:K]=n。例：视C为R上向量空间，基{1，i}，维数为2,称C为R的二维扩张。[F:K]=[F:E][E:K]无限扩张[F:K]=∞第9页，课件共35页，创作于2023年2月7.1域的扩张扩域的过程反过来，就得到素域的概念，即不会是任何域的扩域的域定义7-3域F上子域K，可以并入F子集X扩张，称为X在K上生成的子域，表示为K(X)扩域过程中最小的一步，是得到所谓单扩张，即并入一个元素而生成之扩域。

第10页，课件共35页，创作于2023年2月例设F=R,K=Q,S={√2}，则K(S)=Q(√2)={a+b√2|a,b∈Q}复数域上的子域R，子集X={i},则R(X)=C第11页，课件共35页，创作于2023年2月7.2有限域的基本性质有限域的加法特性：特征有理数域、实数域和复数域中，任意多个1相加都不等于0而有限域中，因为元素个数有限，若干个1相加中不可能没有相同的元素设i*1=j*1,1≤i<j,则(i-j)*1=0定义：设F为域，1为乘法单位元素，如果对任意正整数m，都有m*1≠0,则称F的特征是0，否则若适合条件的最小正整数p，则成F的特征为p，记为charF。第12页，课件共35页，创作于2023年2月7.2有限域的基本性质有限域F的特征=F的素域的阶分析：charF=p,则p*1=0,F的素域K中必包含{0,1}，因此必包含n*1，因此<1>≤素域K的加群，所以p≤|F|,因为F最小子域，|F|=pcharF=p,p一定素数

第13页，课件共35页，创作于2023年2月7.2有限域的基本性质第14页，课件共35页，创作于2023年2月7.2有限域的基本性质有限域的加法特性：特征若F是一个域，则F的特征要么是0要么是素数p若F是特征为p的有限域，则对任意a,b∈F都有（a+b)p=ap+bp第15页，课件共35页，创作于2023年2月7.2有限域的基本性质第16页，课件共35页，创作于2023年2月7.2有限域的基本性质第17页，课件共35页，创作于2023年2月7.2有限域的基本性质有限域的乘法特性：乘法群都是循环群有限域GF中的费马定理：或者说都是方程的根或者说有限域GF(q)乘法群的生成元（即阶为q-1的元素）为GF(q)的本原元联系：原根

乘法的阶；加法的阶被称为周期第18页，课件共35页，创作于2023年2月7.5有限域的构造域上的多项式如同环上的多项式，只是系数来源于域最重要的的是GF(p)和GF(pn),p素如f(x)=x6+x4+x+1,g(x)=x4+x+1为GF(2)上的多项式

,则，用g(x)去除f(x)商式为q(x)=x2+1,余式r(x)=x3+x2用域上n次多项式去除F(x)中的所有多项式，所得余数的次数一定小于n，如果域F含有q个元素，则余式共有qn个不同形式，这样就可以将F(x)中所有元素划为qn个剩余式如f(x)=x3+1为GF(2)上的多项式，用他去除GF(2)上所有多项式，得到余式可以将GF(2)上的多项式划分为8个剩余类{0}，{1},{x},{x+1},{x2},{x2+1},{x2+x},{x2+x+1}第19页，课件共35页，创作于2023年2月7.5有限域的构造第20页，课件共35页，创作于2023年2月7.5有限域的构造这些剩余形成的多项式代数结构是域吗？关键：逆元如f(x)=x3+1时，{x+1}有逆元吗？若要构成域，则模必须为既约多项式若f(x)不是即约，则f(x)=g(x)h(x)，g(x)和h(x)的次数小于f(x)，则g(x)和h(x)是剩余类的一个代表元，所以属于这个新的代数结构，但它们无逆元。第21页，课件共35页，创作于2023年2月7.5有限域的构造生成域：设p(x)为域F上一个n次既约多项式，记F[x]p(x)为模p(x)全体剩余式的集合，集合上的运算为多项式按模加和按模乘,则F[x]p(x)构成域，如果F包含q个元素，则F[x]p(x)是一个包含qn个元素的有限域GF(qn)，F是GF(qn)的子域GF(qn)是F的扩域，或称是由p(x)扩成的域选取p(x)的不同，取模运算效率不同，一般p(x)项数越少效率越高，所以一般p(x)为3项式或5项式，因为偶数项式都不是既约的。项数确定，除最高次数（已确定）其余次数从高向低尽量小第22页，课件共35页，创作于2023年2月7.5有限域的构造例：由GF(2)上的既约多项式p(x)=x4+x+1扩成GF(24)4位向量形式多项式形式生成元幂形式指数形式

000000-∞00011a000010xa110100x2a2

21000x3a330011x+1a440110x2+xa551100x3+x2a66第23页，课件共35页，创作于2023年2月7.5有限域的构造4位向量形式多项式形式生成元幂形式指数形式

1011x3+x+1a770101x2+1a881010x3+xa990100x2a10

100111x2+x+1

a11111110x3+x2+xa12121111x3+x2+x+1a13131101x3+x2+1

a14141001x3+1a15

15第24页，课件共35页，创作于2023年2月7.5有限域的构造第25页，课件共35页，创作于2023年2月7.5有限域的构造多项式的周期设f(x)是GF(p)上的多项式，且f(0)≠0,使f(x)除得尽xt-1的最小t称为f(x)的周期，记为P(f)=tf(0)≠0必要，否则，f(x)必包含x的因式，f(x)必不能整除xt-1f(x)互素的全体余式加上元素0构成有限域，记为[GF(p)f(x)]*注意，此时没有要求f(x)既约t其实就是元素x在域[GF(p)f(x)]*中的阶若既约多项式的周期等于pm-1，则为本原多项式第26页，课件共35页，创作于2023年2月7.6有限域应用代表性应用：编码理论开关理论纠错码AES：p(x)=x8+x4+x3+x+1第27页，课件共35页，创作于2023年2月7.6有限域应用AES1997年美国政府向世界公开征集，2000年称为美国国家标准利用p(x)=x8+x4+x3+x+1扩成有限域GF(28)，8次不可约多项式一个字节就可视为一个多项式，成为GF(28)中的一个元素第28页，课件共35页，创作于2023年2月7.6有限域应用AESAES的主要环节字节代换：使用一个s盒S盒的构造：x行y列初始值xy，16进制下的，然后每个求出有限域中的逆，在进行矩阵变换行移位：一个简单的置换列混淆：相互加、乘后形成新值轮密钥加：按位xor多轮，每个阶段均可逆第29页，课件共35页，创作于2023年2月7.6有限域应用循环冗余码CRC检错码与纠错码

CRC的工作过程可以简单的概括为四步。添0：在需要发送的数据后面添加0，0的个数比生成多项式的位数少1个做除法：①除法时并非减法，而是异或②我们关心的是最后的余数R而不是商Q，因此有时直接将余数称为CRC余数填充：将余数R填入待发数据中补充的0的位置，得到发送方的真正发送的数据S。接收方检查：接收方将收到的数据S，执行与发送方同样的除法，如果得到的余数为0，则验证通过，如果不为0则传输出错。第30页，课件共35页，创作于2023年2月7.6有限域应用第31页，课件共35页，创作于2023年2月7.6有限域应用CRC的数学原理

有限域中，将一般将位串看作系数为0或1的多项式，所以CRC也叫做多项式编码如10011有6位，表示多项式为G(x)=x4+x+1，G(x)每项对应的系数分别为1、0、0、1、1在M后面添加r位0，就相当于xr·M(x)。有限域中，加法、减法是模2运算，因此，在上面第二步骤除法的减法运算为异或。第32页，课件共35页，创作于2023年2月7.6有限域应用CRC的数学原理

若待发送数据为M(x)，生成元为G(x)，G(x)的最高次数为r，R(x)为余数，