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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、公理：,,,,,,,,,,,,,,,,,,,,,（1）（*-封閉性） （2）（*-單位素） （3）（*-反元素） （4）（*-結合律） （5）（*-交換性）,公理：,*對有 分配律,,,,,,質(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猜想,,,,,連分數(shù),3.8 連分數(shù),定義,任何以下形式的數(shù)均稱為連分數(shù),,其中，q1、q2、……為整數(shù),連分數(shù),性質(zhì),令 為一實數(shù)，其連分數(shù)表達式為,其中，,,而其各項連分數(shù)的收斂值為：,,當中 滿足遞推關系及初始條件,,,,,,連分數(shù),定理：,,,令 （且 ）為實數(shù)x的某項連分數(shù)的收斂值,,,,密碼安全偽隨機數(shù)生

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

20、=1且s為隨機數(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偽隨機數(shù)字生成器,密碼安全偽隨機數(shù)生成器,算法,RSA偽隨機數(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]為隨機數(shù)種子for(i=1;i<=k;i++){x[i]=PowerMod(x[i-1],e,n);