第2章[第2部分]密碼學(xué)數(shù)學(xué)基礎(chǔ)(數(shù)論2)

1、第2章 密碼學(xué)數(shù)學(xué)基礎(chǔ),數(shù)論基礎(chǔ)篇（2）,（Number Theory）,成都信息工程學(xué)院網(wǎng)絡(luò)學(xué)院,群-概念,思考：構(gòu)成群的，單位元（恒等元）和逆元各是什么，不構(gòu)成群的，原因是什么？ *判定一個(gè)非空集合是不是群，就用群的定義去衡量,群的例子,有限群，階數(shù)，無限群，阿貝爾群,,,,,,,,,非空集合元素F，若在F中定義了加和乘兩種運(yùn)算，且滿足下述公理：（1）F關(guān)于加法構(gòu)成阿貝爾群。其加法恒等元記為0。（2）F中非零元素全體對乘法構(gòu)

2、成阿貝爾群。其乘法恒等元（單位元）記為1。（3）加法和乘法間有如下分配律：a(b+c)=ab+ac(b+c)a=ba+ca則稱F為一個(gè)域**若F中的元素為有限個(gè)，稱F為有限域(Finite Field)。,域的定義,例：　　　有理數(shù)全體，實(shí)數(shù)全體對加法、乘法都分別構(gòu)成域，分別稱為有理數(shù)域，實(shí)數(shù)域。且這兩個(gè)域中的元素有無限多個(gè)，所以稱它們?yōu)闊o限域。>>>有理數(shù)域中，對加法的恒等元是什么？某個(gè)元素的逆元是什么

3、？ （除零元素外）對乘法的恒等元是什么？某個(gè)元素的逆元是什么？>>>有實(shí)數(shù)域中，與在有理數(shù)域中類同。,域的例子,思考：模10的一個(gè)完全剩余系﹛ 0,1,2,…,9﹜對加法和乘法分別構(gòu)成群嗎？構(gòu)成域嗎？模11的一個(gè)完全剩余系﹛ 0,1,2,…,9,10﹜對加法和乘法分別構(gòu)成群嗎？構(gòu)成域嗎？,關(guān)于完全剩余系、域、群的思考,,例 域GF(2)中僅有兩個(gè)0和1，故稱為二元域域GF(5),有限域,如果域F只包含有限

4、個(gè)元素，則稱為有限域,定理1：每個(gè)有限域的階必為素?cái)?shù)的冪定理2：對任意素?cái)?shù)p與正整數(shù)n，令Zp＝{0,1,2,……,p-1},+為模p加,×為模p乘，則五元組(zp,+,×,0,1}構(gòu)成域，稱為p元域，存在p n階域，記為GF(pn),當(dāng)n＝1時(shí)，有限域GF(p)也稱為素?cái)?shù)域,思考,若p是素?cái)?shù)，GF(p)是如下定義的兩個(gè)二元運(yùn)算下是域a,b∈p, a+b mod p a×b mod pG

5、F(p)是域，則GF(pn)是GF(p)的擴(kuò)域，那么GF(pn)在何種運(yùn)算下能構(gòu)成域呢？,對于多項(xiàng)式f(x)，設(shè)它的次數(shù)為n，表示為deg(f)=n. 對于多項(xiàng)式f(x)、g(x)、h(x)，設(shè)deg(g)＝n，如果g(x)=q(x)f(x)+h(x)，其中deg(h)<n則可定義 g(x) ≡h(x) mod f(x),定義多項(xiàng)式同余,一個(gè)多項(xiàng)式f(x)稱為是不可約的，如果不存在多項(xiàng)式f1(x),f2(x)∈Zp

6、[x]，滿足f(x)= f1(x)*f2(x)，其中deg(f1)>0和deg(f2)>0 ,也即f1(x),f2(x)不能是常數(shù)。,定義不可約多項(xiàng)式,解讀Zp[x],定義Zp[x]為變元x的所有多項(xiàng)式的集合（每一項(xiàng)的系數(shù)都小于p）。設(shè)整系數(shù)多項(xiàng)式f(x)=anxn+…+a1x+a0若f(x)∈Zp[x],則要求ai ∈ Zp(0<=i<=n),即0<=ai<p在實(shí)踐中，用得比較多的是Z2[

7、x]例：　 f(x)=x5+x2+x g(x)=3x5+x+1則f(x)∈Z２[x]，而g(x)不屬于Z２[x]。,Zp[x]/f(x)是域當(dāng)且僅當(dāng)f(x)是不可約的 意思是：如果f(x)是不可約的，則所有屬于Zp[x]的多項(xiàng)式，在mod f(x)后的余式，構(gòu)成一個(gè)域。反之也成立。 即這些余式對加法構(gòu)成交換群，非零元素全體對乘法構(gòu)成交換群。整數(shù)類似：　所有整數(shù)Z，Z/p是域當(dāng)且僅當(dāng)p是素?cái)?shù)的 即mod

8、p的余數(shù)對加法構(gòu)成交換群，非零元素全體對乘法構(gòu)成交換群。,一個(gè)重要的結(jié)論,例： 構(gòu)造一個(gè)具有八個(gè)元素的域。這可以通過在Z2[x]中找一個(gè)次數(shù)為3的不可約多項(xiàng)式做到。因?yàn)槿魏纬?shù)項(xiàng)為0的多項(xiàng)式都可以被x整除，因而是可約的，故只需考慮常數(shù)項(xiàng)為1的多項(xiàng)式。有這樣四個(gè)：,構(gòu)造域舉例,f1(x)=x3+1f2(x)=x3+x+1f3(x)= x3+x2+1f4(x)= x3+ x2+x+1(記住，所有的系數(shù)要模2約化),因?yàn)椋篺

9、1(x)=x3+1=(x+1)(x2+x+1)f4(x)= x3+ x2+x+1=(x+1)(x2+1)而f2(x), f3(x)是不可約化的。f2(x), f3(x)中任何一個(gè)都可用于構(gòu)造一個(gè)具有八個(gè)元素的域。,構(gòu)造域舉例,下面以選取f(x)= x3+x+1為例，來構(gòu)造一個(gè)具有八個(gè)元素的域。 構(gòu)造Z2[x]/ x3+x+1,八個(gè)域元素為0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 這

10、八個(gè)域元素的系數(shù)為:(000,001,010,011,100,101,110,111),構(gòu)造域舉例,要計(jì)算兩個(gè)域元素的和，可進(jìn)行多項(xiàng)式相加（這里是在Z2[x] 中的加法，相當(dāng)于是按位異或）例： (x2+1)＋(x2+x+1)=2x2+x+2 ≡ x mod（ x3+x+1 ）相當(dāng)于（101）⊕ (111)=(010) 顯然，八個(gè)域元素0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 之間的相

11、加(按位異或） ，相當(dāng)于(000,001,010,011,100,101,110,111)之間相加(按位異或），結(jié)果肯定在(000,001,010,011,100,101,110,111)中。,域元素求和,要計(jì)算兩個(gè)域元素的乘積，可進(jìn)行多項(xiàng)式相乘，并且模x3+x+1約化（即用x3+x+1去除，找出余式）。由于是用一個(gè)三次多項(xiàng)式去除，余式的次數(shù)至多是2，因此是該域中的元素。如（x2+1）(x2+x+1) ≡ x4+x3+x2+x2+x+

12、1　　　　　　　　 ≡ x4+x3+x+1　　　　　　　　 ≡ (x+1)( x3+x+1)+x2+x　　　　　　　　　≡ x2+x mod（ x3+x+1 ）因此，在Z2[x]中， （x2+1）(x2+x+1) ≡ x2+x mod（ x3+x+1 ）,域元素求積,Example: GF(23),Polynomial Congruence,使用生成元,,,,Example: GF(23),(Power R

13、epresentation) g1 = gg2 = g2 Using g3 = g + 1 g3 = g + 1g4 = g2 + gg5 = g2 + g + 1g6 = g2 + 1 g7 = 1,Polynomial Congruence,,若GF(2m)中包含2m個(gè)元素，那么在GF(2m)中至少存在一個(gè)元素g，使得GF(2m)中任意非零元素可以表示成g的某方次冪

14、的形式，這樣的元素g稱為GF(2m)的生成元（或本原元），即：,實(shí)例構(gòu)造GF(24),選擇GF(2)上的多項(xiàng)式f(x)最高次數(shù)為4的不可約多相式如：f(x)=x4+x+1或f(x)=x4+x3+1多項(xiàng)式的剩余類：r(x)=a3x3+a2x2+a1x+a0因此有Z2[x]:0,1,x,1+x,……,,,,,,,GF(28),（AES）:系數(shù)模2，即只可0或1余式的次數(shù)至多是7次，共28=256個(gè)多項(xiàng)式p(x) = x8 + x

15、4 + x3 + x + 1,將b7b6b5b4b3b2b1b0構(gòu)成的字節(jié)b看成系數(shù)在{0,1}中的多項(xiàng)式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如： 十六進(jìn)制數(shù)‘57’對應(yīng)的二進(jìn)制為01010111，看成一個(gè)字節(jié)，對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1。,字節(jié)在GF(28)上的表示,在多項(xiàng)式表示中，GF(28)上兩個(gè)元素的和仍然是一個(gè)次數(shù)不超過7的多項(xiàng)式，其系數(shù)等于兩個(gè)元素對應(yīng)系數(shù)的模2加（

16、按位異或）。例如： ‘57’+‘83’=‘D4’，用多項(xiàng)式表示為(x6+x4+x2+x+1)+(x7+x+1)≡x7+x6+x4+x2(modp(x))用二進(jìn)制表示為01010111⊕10000011=11010100由于每個(gè)元素的加法逆元等于自己，所以減法和加法相同。,GF(28)上兩個(gè)元素的和,要計(jì)算GF(28)上的乘法，必須先確定一個(gè)GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個(gè)元素的乘積就是這兩個(gè)多項(xiàng)式的模乘

17、（以這個(gè)8次不可約多項(xiàng)式為模）?！　≡赗ijndael密碼中，這個(gè)8次不可約多項(xiàng)式確定為p(x)= x8+x4+x3+x+1它的十六進(jìn)制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項(xiàng)式乘法： (x6+x4+x2+x+1)·(x7+x+1)≡x7+x6+1(modp(x)),GF(28)上的乘法,以上定義的乘法滿足交換律，且有單位元‘01’。另外，對任何次數(shù)小于8的多項(xiàng)式b(x)，可用

18、推廣的歐幾里得算法得b(x)a(x)+p(x)c(x)=1 即a(x)·b(x)=1 mod p(x)，因此a(x)是b(x)的乘法逆元。 再者，乘法還滿足分配律：a(x)·(b(x)+c(x))= a(x)·b(x)+a(x)·c(x)所以，256個(gè)字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。,乘法逆元,GF(28)上還定義了一個(gè)運(yùn)算，稱之為x乘法，

19、其定義為x·b(x)≡b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(mod p(x))　　 如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去p(x)，即求乘積結(jié)果與p(x)的異或。由此得出x（十六進(jìn)制數(shù)‘02’）乘b(x)可以先對b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），　　 若b7=1，則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，而任意常數(shù)乘法可以通過對中

20、間結(jié)果相加實(shí)現(xiàn)。,GF(28)上x乘法,b7＝0舉例02 ·54=(0000 0010) ·(0101 0100)=(x)·(x6+x4+x2) =x7+ x5+x3 =x7+ x5+x3 ≡ x7+ x5+x3 (modp(x)) =（1010 1000）由上面的規(guī)則：把(0101 0100) 在字節(jié)內(nèi)左移一位即得（1010 1000） （最后一位補(bǔ)0）,b7＝0舉例,02

21、83;D4=(0000 0010) ·(1101 0100) =(x) ·(x7+x6+x4+x2) =x8+x7+ x5+x3 ≡(x4+x3+x+1)+x7+x5+x3(modp(x)) //***相當(dāng)（0001 1011）與（1010 1000）異或****// ≡ x7+x5+x4+x+1(modp(x))

22、 =(1011 0011)　由上面的規(guī)則：先把(1101 0100) 在字節(jié)內(nèi)左移一位即得（10101000）（最后一位補(bǔ)0），因?yàn)閎7＝1，故（1010 1000）再與（0001 1011）異或得（1011 0011）,b7＝1舉例,例如，‘57’·‘13’可按如下方式實(shí)現(xiàn)： ‘57’·‘02’ =‘AE’；‘57’·‘04’= ‘AE’ ·‘02’ =‘47’；‘57’