第3章-基礎(chǔ)數(shù)論--信息理論《密碼學(xué)加密演算法》

1、返回總目錄,第3章基礎(chǔ)數(shù)論,教學(xué)目的,了解模運(yùn)算及輾轉(zhuǎn)相除法了解中國(guó)余式子定律了解Lagrange定理與費(fèi)馬小定理了解原根、二次剩余、Galois域等概念了解質(zhì)數(shù)理論和連分?jǐn)?shù)了解密碼安全偽隨機(jī)數(shù)字生成器,? 模運(yùn)算與輾轉(zhuǎn)相除法,本章內(nèi)容,? 中國(guó)余式子定律,? Lagrange定理與費(fèi)馬小定理,? 原根,? 二次剩余,? Galois域,? 連分?jǐn)?shù),? 質(zhì)數(shù)理論,? 密碼安全偽隨機(jī)數(shù)字生成器,模運(yùn)算與輾轉(zhuǎn)相除法,3.1

2、 模運(yùn)算與輾轉(zhuǎn)相除法,假設(shè)今天是星期五，請(qǐng)問(wèn)10000天后是星期幾？,,（即5+10000除以7的余數(shù)）,即：10000天后是星期二,同余,,,,,,,定義（同余，Congruence）：令 。令 為兩整數(shù)，稱(chēng)a同余b模n，記為 ，當(dāng)n整除b-a。而所有與a同余的整數(shù)所組成的集合，即稱(chēng)為a的同余類(lèi)。所有同余類(lèi)所形成的集合,同余類(lèi),同余類(lèi)滿(mǎn)足

3、的性質(zhì)：,（1）（反身性，Reflexivity）,,,（3）（遷移性，Transitivity）,若 則,例：,,令 則,,模運(yùn)算,加法：,（1）封閉性：若同余類(lèi) 則,,（2）交換律：若同余類(lèi) 則,,,（4）存在加法單位素：存在

4、 ，使得,,,,（5）存在加法反元素：對(duì)任一 存在 使得,減法：,乘法：,交換群,,定義（交換群） 考慮 ，其中G為集合，而*為運(yùn)算。令公理：,,,,,,,,,,,,（1）封閉性： 則；（2）交換律： 則；（3）結(jié)合律：

5、 則；（4）存在單位素： ， ，使得（5）存在反元素： ， ，使得,若公理1、3、4、5成立，稱(chēng)為群(Group)；若以上公理1～5都成立，稱(chēng)為交換群。,交換環(huán),,,,,,輾轉(zhuǎn)相除法,例：,求7812及6084的最大公因子,,被除數(shù)=商×除數(shù)+余數(shù)，gcd（被除數(shù)，除數(shù)）=gcd（除數(shù)，余數(shù)）輾轉(zhuǎn)相除法就是利用此性質(zhì)，反

6、復(fù)以（除數(shù)/余數(shù)）取代（被除數(shù)/除數(shù)）,其中：,,所以gcd (7812 , 6084) = 36,輾轉(zhuǎn)相除法,,,,定理3.1 整數(shù)線(xiàn)性方程有整數(shù)解,證明：,,,,若 則：,為一整數(shù)解,,若,,有整數(shù)解,因： 且,,,,所以,,借助廣義輾轉(zhuǎn)相除法，存在整數(shù) ，使得,對(duì)模乘法,,證明：,根據(jù)交換群封閉性,

7、,則,,,,,,,,,,,因 ，故存在乘法反元素 、 使得且 ，而故 為 的乘法反元素。,模運(yùn)算與輾轉(zhuǎn)相除法,3.2 中國(guó)余式子定理（Chinese Remainder Theorem）,定理：,,,,,,,,,令為

8、 兩兩互質(zhì)的正整數(shù)，令 則同余聯(lián)立方程組在集合 有惟一解，其解為其中 ，而,余式定理應(yīng)用,,,,其中， 為n的質(zhì)因數(shù)，,性質(zhì)1：,存在群同構(gòu)（Group Isomorphism）,,定義：,當(dāng)為正整數(shù)時(shí)，定義 Euler-Phi 函數(shù)為,,性質(zhì)2：,,Lagrange定理與費(fèi)

9、馬小定理,3.3 Lagrange定理與費(fèi)馬小定理,,,,,令 為群，若 為子集，且在相同的運(yùn)算*形成群則稱(chēng) （或H）為G的子群（Subgroup）。,子群(Subgroup),Lagrange定理,定理（Lagrange定理） 若G為有限群，H為G中之子群，則,,證明：,H為G的子群，為方便起見(jiàn)，假設(shè)為乘法群?？啥ǖ葍r(jià)關(guān)系如下： 若

10、 如此定義出的等價(jià)關(guān)系可將分割成若干個(gè)等價(jià)類(lèi)， 即,,,,,每個(gè)等價(jià)類(lèi)都有#H個(gè)元素（考慮 為1－1對(duì)應(yīng)）。因此#H整除 #G,費(fèi)馬小定理,定理（費(fèi)馬小定理）,令為p質(zhì)數(shù)、a為與p互質(zhì)的整數(shù)，則,,證明：,,,考慮乘法群 ， 為其子群，根據(jù)Lagrange定

11、理,,所以,,其中,,因此：,,原根,考慮2的次方（mod 11）：,3.4 原根,,,此時(shí)稱(chēng)2為乘法群 的原根（Primitive Root）,,,當(dāng) 時(shí)，則10必整除x；此時(shí)稱(chēng)10為2在（mod 11）（或在乘法群 ）的秩（Order）,秩,定義：,令G為乘法群，而g∈G為其中一元素，則元素g的秩（Order）定義為,,,,,,也可能

12、不存在x ∈ N使得 ，此時(shí)定義 。若G為有限群，則 為G的子群，有 ，根據(jù)Lagrange定理，子群的元素個(gè)數(shù)必整除母群G的元素個(gè)數(shù)，故,,原根定理,定理：,令g為質(zhì)數(shù)p上的原根，則,（1）若x為整數(shù)，則（2）若i、j為整

13、數(shù)，則,,,證明：,,,,,,,,,,,,子群與循環(huán)群,,令G為任一乘法群， 為任一元素，則 為G中的子群（封閉性與反元素的存在性自然成立）。此子群稱(chēng)為由元素g所生成的子群。,定義：子群,定義：循環(huán)群（Cyclic Group）,,,若存在 使得 ，則稱(chēng)G為循環(huán)群（Cyclic Grou

14、p），而g為原根或生成元（Generator）。,二次剩余,3.5 二次剩余 Quadratic Residue,定義：,同余式,,a與n為互質(zhì)整數(shù),若有整數(shù)解，稱(chēng)a為（mod n）的二次剩余（Quadratic Residue）若無(wú)解則稱(chēng)a為（mod n）的非二次剩余（Quadratic Nonresidue）。,二次剩余的性質(zhì),性質(zhì),令p為奇質(zhì)數(shù)，可定義函數(shù),,Legendre符號(hào),,定義：,令p為質(zhì)數(shù)，定義Legendre

15、符號(hào)如下：,定理 （ Euler判別）,令p為質(zhì)數(shù)，a與p互質(zhì)。則：,,Legendre符號(hào),性質(zhì),令p為奇質(zhì)數(shù)，a、b為與p互質(zhì)的整數(shù)，則,,,（2）,,（3）,,（4）,（5）,,,定理Quadratic Reciprocity,令p、q為奇質(zhì)數(shù)，則,,Jacobi 符號(hào),定義：,令a為整數(shù)，n>0為奇整數(shù)，其質(zhì)因數(shù)分解為,,定義Jacobi符號(hào)：,,性質(zhì)：,當(dāng)n>0為奇整數(shù)，Jacobi符號(hào)才可能有意義,,,,,,（5

16、）,（3）,（4）,（2）,（6）,注：a、b為整數(shù)，m、n為奇整數(shù),Galois域,3.6 Galois域,定義,域（Field）：令K為一集合，并含有兩個(gè)運(yùn)算“ ”及“*”，則（K， ，*）為域,公理：,（K， ，*）為交換群，即,（1）（ -封閉性） （2）（ -單位素） （3）（ -反元素） （4）（ -結(jié)合律） （5）（ -交換性）,,,,,,,,,,,,,,x=,,,x,x,y,Galois域,

17、公理：,,,,,,,,,,,,,,,,,,,,,（1）（*-封閉性） （2）（*-單位素） （3）（*-反元素） （4）（*-結(jié)合律） （5）（*-交換性）,公理：,*對(duì)有 分配律,,,,,,質(zhì)數(shù)理論,3.7 質(zhì)數(shù)理論,定義,,,令p為不為1的正整數(shù)，p為質(zhì)數(shù)（Prime） 若某正整數(shù)d整除p（記為 ），則d=1或d=p。,Eratosthenes篩法,質(zhì)數(shù)定理,質(zhì)數(shù)定理,,,Riemann猜想,,H

18、ardy-Littlewood猜想,,,,,連分?jǐn)?shù),3.8 連分?jǐn)?shù),定義,任何以下形式的數(shù)均稱(chēng)為連分?jǐn)?shù),,其中，q1、q2、……為整數(shù),連分?jǐn)?shù),性質(zhì),令 為一實(shí)數(shù)，其連分?jǐn)?shù)表達(dá)式為,其中，,,而其各項(xiàng)連分?jǐn)?shù)的收斂值為：,,當(dāng)中 滿(mǎn)足遞推關(guān)系及初始條件,,,,,,連分?jǐn)?shù),定理：,,,令 （且 ）為實(shí)數(shù)x的某項(xiàng)連分?jǐn)?shù)的收斂值,,,,密碼安全偽隨機(jī)數(shù)生

19、成器,3.9 密碼安全偽隨機(jī)數(shù)生成器,BlumBlumShub(){do{p=RandomPrime();}while (p%4!=3);do{q=RandomPrime();}while (p%4!=3);//p,q為隨機(jī)質(zhì)數(shù)且 = 3 mod 4n=p*q;do{s=RandomInteger(1,n);}while(gcd(s,n)!=1);//gcd(s,n)

20、=1且s為隨機(jī)數(shù)種子x[0]=s;for(i=1;i<=k;i++){x[i]=x[i-1]*x[i-1]%n;b[i]=x[i]&1;//取最末位};return(b[1],b[2],...,b[k]);},算法,Blum-Blum-Shub偽隨機(jī)數(shù)字生成器,密碼安全偽隨機(jī)數(shù)生成器,算法,RSA偽隨機(jī)數(shù)字生成器,RSA_PseudomBitGen(){p=RandomPrime

21、();q=RandomPrime();n=p*q;phi=(p-1)*(q-1);do{e=RandomInteger(2,phi-1);}while(gcd(e,phi)!=1);//gcd(e,phi)=1x[0]=RandomInteger(1,n-1);//x[0]為隨機(jī)數(shù)種子for(i=1;i<=k;i++){x[i]=PowerMod(x[i-1],e,n);