第2章[第2部分]密碼學數學基礎(數論2)

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

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

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

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

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

6、[x]，滿足f(x)= f1(x)*f2(x)，其中deg(f1)>0和deg(f2)>0 ,也即f1(x),f2(x)不能是常數。,定義不可約多項式,解讀Zp[x],定義Zp[x]為變元x的所有多項式的集合（每一項的系數都小于p）。設整系數多項式f(x)=anxn+…+a1x+a0若f(x)∈Zp[x],則要求ai ∈ Zp(0<=i<=n),即0<=ai<p在實踐中，用得比較多的是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)是域當且僅當f(x)是不可約的 意思是：如果f(x)是不可約的，則所有屬于Zp[x]的多項式，在mod f(x)后的余式，構成一個域。反之也成立。 即這些余式對加法構成交換群，非零元素全體對乘法構成交換群。整數類似：　所有整數Z，Z/p是域當且僅當p是素數的 即mod

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

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)中任何一個都可用于構造一個具有八個元素的域。,構造域舉例,下面以選取f(x)= x3+x+1為例，來構造一個具有八個元素的域。 構造Z2[x]/ x3+x+1,八個域元素為0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 這

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

11、加(按位異或） ，相當于(000,001,010,011,100,101,110,111)之間相加(按位異或），結果肯定在(000,001,010,011,100,101,110,111)中。,域元素求和,要計算兩個域元素的乘積，可進行多項式相乘，并且模x3+x+1約化（即用x3+x+1去除，找出余式）。由于是用一個三次多項式去除，余式的次數至多是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個元素，那么在GF(2m)中至少存在一個元素g，使得GF(2m)中任意非零元素可以表示成g的某方次冪

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

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

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

17、（以這個8次不可約多項式為模）?！　≡赗ijndael密碼中，這個8次不可約多項式確定為p(x)= x8+x4+x3+x+1它的十六進制表示為‘11B’。例如，‘57’·‘83’=‘C1’可表示為以下的多項式乘法： (x6+x4+x2+x+1)·(x7+x+1)≡x7+x6+1(modp(x)),GF(28)上的乘法,以上定義的乘法滿足交換律，且有單位元‘01’。另外，對任何次數小于8的多項式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個字節(jié)值構成的集合，在以上定義的加法和乘法運算下，有有限域GF(28)的結構。,乘法逆元,GF(28)上還定義了一個運算，稱之為x乘法，

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

20、間結果相加實現。,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é)內左移一位即得（1010 1000） （最后一位補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)) //***相當（0001 1011）與（1010 1000）異或****// ≡ x7+x5+x4+x+1(modp(x))

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