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

第十頁，共三十五頁，2022年，8月28日例設F=R,K=Q,S={√2}，則K(S)=Q(√2)={a+b√2|a,b∈Q}復數(shù)域上的子域R，子集X={i},則R(X)=C第十一頁，共三十五頁，2022年，8月28日7.2有限域的基本性質有限域的加法特性：特征有理數(shù)域、實數(shù)域和復數(shù)域中，任意多個1相加都不等于0而有限域中，因為元素個數(shù)有限，若干個1相加中不可能沒有相同的元素設i*1=j*1,1≤i<j,則(i-j)*1=0定義：設F為域，1為乘法單位元素，如果對任意正整數(shù)m，都有m*1≠0,則稱F的特征是0，否則若適合條件的最小正整數(shù)p，則成F的特征為p，記為charF。第十二頁，共三十五頁，2022年，8月28日7.2有限域的基本性質有限域F的特征=F的素域的階分析：charF=p,則p*1=0,F的素域K中必包含{0,1}，因此必包含n*1，因此<1>≤素域K的加群，所以p≤|F|,因為F最小子域，|F|=pcharF=p,p一定素數(shù)

第十三頁，共三十五頁，2022年，8月28日7.2有限域的基本性質第十四頁，共三十五頁，2022年，8月28日7.2有限域的基本性質有限域的加法特性：特征若F是一個域，則F的特征要么是0要么是素數(shù)p若F是特征為p的有限域，則對任意a,b∈F都有（a+b)p=ap+bp第十五頁，共三十五頁，2022年，8月28日7.2有限域的基本性質第十六頁，共三十五頁，2022年，8月28日7.2有限域的基本性質第十七頁，共三十五頁，2022年，8月28日7.2有限域的基本性質有限域的乘法特性：乘法群都是循環(huán)群有限域GF中的費馬定理：或者說都是方程的根或者說有限域GF(q)乘法群的生成元（即階為q-1的元素）為GF(q)的本原元聯(lián)系：原根

乘法的階；加法的階被稱為周期第十八頁，共三十五頁，2022年，8月28日7.5有限域的構造域上的多項式如同環(huán)上的多項式，只是系數(shù)來源于域最重要的的是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)中的所有多項式，所得余數(shù)的次數(shù)一定小于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}第十九頁，共三十五頁，2022年，8月28日7.5有限域的構造第二十頁，共三十五頁，2022年，8月28日7.5有限域的構造這些剩余形成的多項式代數(shù)結構是域嗎？關鍵：逆元如f(x)=x3+1時，{x+1}有逆元嗎？若要構成域，則模必須為既約多項式若f(x)不是即約，則f(x)=g(x)h(x)，g(x)和h(x)的次數(shù)小于f(x)，則g(x)和h(x)是剩余類的一個代表元，所以屬于這個新的代數(shù)結構，但它們無逆元。第二十一頁，共三十五頁，2022年，8月28日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(xiàn)是GF(qn)的子域GF(qn)是F的擴域，或稱是由p(x)擴成的域選取p(x)的不同，取模運算效率不同，一般p(x)項數(shù)越少效率越高，所以一般p(x)為3項式或5項式，因為偶數(shù)項式都不是既約的。項數(shù)確定，除最高次數(shù)（已確定）其余次數(shù)從高向低盡量小第二十二頁，共三十五頁，2022年，8月28日7.5有限域的構造例：由GF(2)上的既約多項式p(x)=x4+x+1擴成GF(24)4位向量形式多項式形式生成元冪形式指數(shù)形式

000000-∞00011a000010xa110100x2a2

21000x3a330011x+1a440110x2+xa551100x3+x2a66第二十三頁，共三十五頁，2022年，8月28日7.5有限域的構造4位向量形式多項式形式生成元冪形式指數(shù)形式

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

100111x2+x+1

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

a14141001x3+1a15

15第二十四頁，共三十五頁，2022年，8月28日7.5有限域的構造第二十五頁，共三十五頁，2022年，8月28日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，則為本原多項式第二十六頁，共三十五頁，2022年，8月28日7.6有限域應用代表性應用：編碼理論開關理論糾錯碼AES：p(x)=x8+x4+x3+x+1第二十七頁，共三十五頁，2022年，8月28日7.6有限域應用AES1997年美國政府向世界公開征集，2000年稱為美國國家標準利用p(x)=x8+x4+x3+x+1擴成有限域GF(28)，8次不可約多項式一個字節(jié)就可視為一個多項式，成為GF(28)中的一個元素第二十八頁，共三十五頁，2022年，8月28日7.6有限域應用AESAES的主要環(huán)節(jié)字節(jié)代換：使用一個s盒S盒的構造：x行y列初始值xy，16進制下的，然后每個求出有限域中的逆，在進行矩陣變換行移位：一個簡單的置換列混淆：相互加、乘后形成新值輪密鑰加：按位xor多輪，每個階段均可逆第二十九頁，共三十五頁，2022年，8月28日7.6有限域應用循環(huán)冗余碼CRC檢錯碼與糾錯碼

CRC的工作過程可以簡單的概括為四步。添0：在需要發(fā)送的數(shù)據(jù)后面添加0，0的個數(shù)比生成多項式的位數(shù)少1個做除法：①除法時并非減法，而是異或②我們關心的是最后的余數(shù)R而不是商Q，因此有時直接將余數(shù)稱為CRC余數(shù)填充：將余數(shù)R填入待發(fā)數(shù)據(jù)中補充的0的位置，得到發(fā)送方的真正發(fā)送的數(shù)據(jù)S。接收方檢查：接收方將收到的數(shù)據(jù)S，執(zhí)行與發(fā)送方同樣的除法，如果得到的余數(shù)為0，則驗證通過，如果不為0則傳輸出錯。第三十頁，共三十五頁，2022年，8月28日7.6有限域應用第三十一頁，共三十五頁，2022年，8月28日7.6有限域應用CRC的數(shù)學原理

有限域中，將一般將位串看作系數(shù)為0或1的多項式，所以CRC也叫做多項式編碼如10011有6位，表示多項式為G(x)=x4+x+1，G(x)每項對應的系數(shù)分別為1、0、0、1、1在M后面添加r位0，就相當于xr·M(x)。有限域中，加法、減法是模2運算，因此，在上面第二步驟除法的減法運算為異或。第三十二頁，共三十五頁，2022年，8月28日7.6有限域應用CRC的數(shù)學原理

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