有限域信安數(shù)學(xué)

有限域信安數(shù)學(xué)第1頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張域整環(huán)無(wú)零因子環(huán)含幺環(huán)可交換環(huán)環(huán)Abel群群半群AB表示滿足A則滿足B除環(huán)第2頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張定義7-1非空集合F，若F中定義了加和乘兩種運(yùn)算，且滿足：1)F關(guān)于加法構(gòu)成阿貝爾群，加法恒等元記為02)F中所有非零元素對(duì)乘法構(gòu)成阿貝爾群，乘法恒等元記為13)加法和乘法之間滿足分配律則F與這兩種運(yùn)算構(gòu)成域每一個(gè)非零元都是可逆元的有單位元的交換環(huán)如實(shí)數(shù)域\復(fù)數(shù)域\有理數(shù)域第3頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張當(dāng)域元素個(gè)數(shù)有限時(shí)，稱(chēng)為有限域或伽羅瓦galois域,記為GF并把元素的個(gè)數(shù)稱(chēng)為F的階，記為GF(n),否則稱(chēng)為無(wú)限域最常見(jiàn):GF(2)兩個(gè)元素個(gè)數(shù)相同的有限域一定同構(gòu)第4頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張如：1、全體整數(shù)2、全體偶數(shù)3、全體實(shí)數(shù)4、全體復(fù)數(shù)5、全體有理數(shù)設(shè)q為素?cái)?shù)，則整數(shù)全體關(guān)于模q的剩余類(lèi)在模q的運(yùn)算下(模q加和乘)構(gòu)成q階有限域GF(q)構(gòu)成環(huán)，不構(gòu)成域構(gòu)成域構(gòu)成域構(gòu)成域構(gòu)成環(huán)，不構(gòu)成域無(wú)限域6、第5頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張子域定義7-2記為F≤A第6頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張定義7-3設(shè)F是域，X是F一個(gè)子集，那么F中包含X所有子域的交，稱(chēng)為X所生成的子域。所有子域的交:最小子域素域素域也稱(chēng)為極小域任何域都包含一個(gè)素域第7頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張這兩個(gè)例子實(shí)際上已刻劃了所有的素域。第8頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張有限擴(kuò)張?jiān)O(shè)F是K的擴(kuò)域，視F是K上的向量空間，且維數(shù)為n，則稱(chēng)F是E上的有限擴(kuò)張，記為[F:K]=n。例：視C為R上向量空間，基{1，i}，維數(shù)為2,稱(chēng)C為R的二維擴(kuò)張。[F:K]=[F:E][E:K]無(wú)限擴(kuò)張[F:K]=∞第9頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.1域的擴(kuò)張擴(kuò)域的過(guò)程反過(guò)來(lái)，就得到素域的概念，即不會(huì)是任何域的擴(kuò)域的域定義7-3域F上子域K，可以并入F子集X擴(kuò)張，稱(chēng)為X在K上生成的子域，表示為K(X)擴(kuò)域過(guò)程中最小的一步，是得到所謂單擴(kuò)張，即并入一個(gè)元素而生成之?dāng)U域。

第10頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月例設(shè)F=R,K=Q,S={√2}，則K(S)=Q(√2)={a+b√2|a,b∈Q}復(fù)數(shù)域上的子域R，子集X={i},則R(X)=C第11頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)有限域的加法特性：特征有理數(shù)域、實(shí)數(shù)域和復(fù)數(shù)域中，任意多個(gè)1相加都不等于0而有限域中，因?yàn)樵貍€(gè)數(shù)有限，若干個(gè)1相加中不可能沒(méi)有相同的元素設(shè)i*1=j*1,1≤i<j,則(i-j)*1=0定義：設(shè)F為域，1為乘法單位元素，如果對(duì)任意正整數(shù)m，都有m*1≠0,則稱(chēng)F的特征是0，否則若適合條件的最小正整數(shù)p，則成F的特征為p，記為charF。第12頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)有限域F的特征=F的素域的階分析：charF=p,則p*1=0,F的素域K中必包含{0,1}，因此必包含n*1，因此<1>≤素域K的加群，所以p≤|F|,因?yàn)镕最小子域，|F|=pcharF=p,p一定素?cái)?shù)

第13頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)第14頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)有限域的加法特性：特征若F是一個(gè)域，則F的特征要么是0要么是素?cái)?shù)p若F是特征為p的有限域，則對(duì)任意a,b∈F都有（a+b)p=ap+bp第15頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)第16頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)第17頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.2有限域的基本性質(zhì)有限域的乘法特性：乘法群都是循環(huán)群有限域GF中的費(fèi)馬定理：或者說(shuō)都是方程的根或者說(shuō)有限域GF(q)乘法群的生成元（即階為q-1的元素）為GF(q)的本原元聯(lián)系：原根

乘法的階；加法的階被稱(chēng)為周期第18頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造域上的多項(xiàng)式如同環(huán)上的多項(xiàng)式，只是系數(shù)來(lái)源于域最重要的的是GF(p)和GF(pn),p素如f(x)=x6+x4+x+1,g(x)=x4+x+1為GF(2)上的多項(xiàng)式

,則，用g(x)去除f(x)商式為q(x)=x2+1,余式r(x)=x3+x2用域上n次多項(xiàng)式去除F(x)中的所有多項(xiàng)式，所得余數(shù)的次數(shù)一定小于n，如果域F含有q個(gè)元素，則余式共有qn個(gè)不同形式，這樣就可以將F(x)中所有元素劃為qn個(gè)剩余式如f(x)=x3+1為GF(2)上的多項(xiàng)式，用他去除GF(2)上所有多項(xiàng)式，得到余式可以將GF(2)上的多項(xiàng)式劃分為8個(gè)剩余類(lèi){0}，{1},{x},{x+1},{x2},{x2+1},{x2+x},{x2+x+1}第19頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造第20頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造這些剩余形成的多項(xiàng)式代數(shù)結(jié)構(gòu)是域嗎？關(guān)鍵：逆元如f(x)=x3+1時(shí)，{x+1}有逆元嗎？若要構(gòu)成域，則模必須為既約多項(xiàng)式若f(x)不是即約，則f(x)=g(x)h(x)，g(x)和h(x)的次數(shù)小于f(x)，則g(x)和h(x)是剩余類(lèi)的一個(gè)代表元，所以屬于這個(gè)新的代數(shù)結(jié)構(gòu)，但它們無(wú)逆元。第21頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造生成域：設(shè)p(x)為域F上一個(gè)n次既約多項(xiàng)式，記F[x]p(x)為模p(x)全體剩余式的集合，集合上的運(yùn)算為多項(xiàng)式按模加和按模乘,則F[x]p(x)構(gòu)成域，如果F包含q個(gè)元素，則F[x]p(x)是一個(gè)包含qn個(gè)元素的有限域GF(qn)，F(xiàn)是GF(qn)的子域GF(qn)是F的擴(kuò)域，或稱(chēng)是由p(x)擴(kuò)成的域選取p(x)的不同，取模運(yùn)算效率不同，一般p(x)項(xiàng)數(shù)越少效率越高，所以一般p(x)為3項(xiàng)式或5項(xiàng)式，因?yàn)榕紨?shù)項(xiàng)式都不是既約的。項(xiàng)數(shù)確定，除最高次數(shù)（已確定）其余次數(shù)從高向低盡量小第22頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造例：由GF(2)上的既約多項(xiàng)式p(x)=x4+x+1擴(kuò)成GF(24)4位向量形式多項(xiàng)式形式生成元冪形式指數(shù)形式

000000-∞00011a000010xa110100x2a2

21000x3a330011x+1a440110x2+xa551100x3+x2a66第23頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造4位向量形式多項(xiàng)式形式生成元冪形式指數(shù)形式

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

100111x2+x+1

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

a14141001x3+1a15

15第24頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造第25頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.5有限域的構(gòu)造多項(xiàng)式的周期設(shè)f(x)是GF(p)上的多項(xiàng)式，且f(0)≠0,使f(x)除得盡xt-1的最小t稱(chēng)為f(x)的周期，記為P(f)=tf(0)≠0必要，否則，f(x)必包含x的因式，f(x)必不能整除xt-1f(x)互素的全體余式加上元素0構(gòu)成有限域，記為[GF(p)f(x)]*注意，此時(shí)沒(méi)有要求f(x)既約t其實(shí)就是元素x在域[GF(p)f(x)]*中的階若既約多項(xiàng)式的周期等于pm-1，則為本原多項(xiàng)式第26頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用代表性應(yīng)用：編碼理論開(kāi)關(guān)理論糾錯(cuò)碼AES：p(x)=x8+x4+x3+x+1第27頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用AES1997年美國(guó)政府向世界公開(kāi)征集，2000年稱(chēng)為美國(guó)國(guó)家標(biāo)準(zhǔn)利用p(x)=x8+x4+x3+x+1擴(kuò)成有限域GF(28)，8次不可約多項(xiàng)式一個(gè)字節(jié)就可視為一個(gè)多項(xiàng)式，成為GF(28)中的一個(gè)元素第28頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用AESAES的主要環(huán)節(jié)字節(jié)代換：使用一個(gè)s盒S盒的構(gòu)造：x行y列初始值xy，16進(jìn)制下的，然后每個(gè)求出有限域中的逆，在進(jìn)行矩陣變換行移位：一個(gè)簡(jiǎn)單的置換列混淆：相互加、乘后形成新值輪密鑰加：按位xor多輪，每個(gè)階段均可逆第29頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用循環(huán)冗余碼CRC檢錯(cuò)碼與糾錯(cuò)碼

CRC的工作過(guò)程可以簡(jiǎn)單的概括為四步。添0：在需要發(fā)送的數(shù)據(jù)后面添加0，0的個(gè)數(shù)比生成多項(xiàng)式的位數(shù)少1個(gè)做除法：①除法時(shí)并非減法，而是異或②我們關(guān)心的是最后的余數(shù)R而不是商Q，因此有時(shí)直接將余數(shù)稱(chēng)為CRC余數(shù)填充：將余數(shù)R填入待發(fā)數(shù)據(jù)中補(bǔ)充的0的位置，得到發(fā)送方的真正發(fā)送的數(shù)據(jù)S。接收方檢查：接收方將收到的數(shù)據(jù)S，執(zhí)行與發(fā)送方同樣的除法，如果得到的余數(shù)為0，則驗(yàn)證通過(guò)，如果不為0則傳輸出錯(cuò)。第30頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用第31頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用CRC的數(shù)學(xué)原理

有限域中，將一般將位串看作系數(shù)為0或1的多項(xiàng)式，所以CRC也叫做多項(xiàng)式編碼如10011有6位，表示多項(xiàng)式為G(x)=x4+x+1，G(x)每項(xiàng)對(duì)應(yīng)的系數(shù)分別為1、0、0、1、1在M后面添加r位0，就相當(dāng)于xr·M(x)。有限域中，加法、減法是模2運(yùn)算，因此，在上面第二步驟除法的減法運(yùn)算為異或。第32頁(yè)，課件共35頁(yè)，創(chuàng)作于2023年2月7.6有限域應(yīng)用CRC的數(shù)學(xué)原理

若待發(fā)送數(shù)據(jù)為M(x)，生成元為G(x)，G(x)的最高次數(shù)為r，R(x)為余數(shù)，