Lecture03密碼學(xué)的數(shù)學(xué)引論.ppt

1、第二章 古典密碼總結(jié),代替 單表代替 使用單詞作為密鑰的加密方法 仿射密碼 多表代替 Playfair密碼 Hill密碼 Vigenere密碼 換位,第三章密碼學(xué)數(shù)學(xué)引論,學(xué)習(xí)要點： 了解數(shù)論、群論、有限域理論的基本概念 了解模運算的基本方法 了解歐幾里德算法、費馬定理、歐拉定理、中國剩余定理 了解群的性質(zhì) 了解有限域中的計算方法,1、除數(shù)(因子)的概念：設(shè)z為由全體整數(shù)而構(gòu)成的集合，若 b0且 使得a=mb,此時稱b整除a.記為ba,還稱b為a的除數(shù)(因子). 注:若a=mb+r且01被稱為素數(shù)是指p的因子僅有1,-1,p,-p。 例：10以內(nèi)的素數(shù)：2，3，5，7,31數(shù)論,算術(shù)基本定理：

2、 任何一個不等于0的正整數(shù)a都可以寫成唯一的表達式aP11P22Ptt，這里P10 例： 91=7*13 11011=7*112*13 分解唯一 任一給定的正整數(shù)可通過簡單列出所有后面公式中非零指數(shù)分量來說明。 整數(shù)12可表示為 a2=2,a3=1 即12=22 * 31 整數(shù)18可表示為 a2=1, a3=2 即18=21 * 32 兩個數(shù)的乘法等同于對應(yīng)指數(shù)分量的加法： 例如：k=12*18=216 k2=2+1=3 k3=1+2=3 k=23*33=216,最大公約數(shù)： 若a,b,cz，如果ca，cb，稱c是a和b的公約數(shù)。正整數(shù)d稱為a和b的最大公約數(shù)，用gcd(a,b)表示，如果它滿

3、足 d是a和b的公約數(shù)。 對a和b的任何一個公約數(shù)c有cd。 將兩個正整數(shù)分別表示為素數(shù)的乘積，確定它們的最大公因子。 例： 300=22*31*52 18=21*32 gcd(300,18)=21*31*50=6 注：1*. 等價的定義形式是： gcd（a,b）maxk ka且kb 2*若gcd（a,b）=1，稱a與b是互素的。,二、模算術(shù),帶余除法：az,0，可找出兩個唯一確定的整數(shù)q和r,使a=qm+r, 0=r m,q和r這兩個數(shù)分別稱為以m去除a所得到的商數(shù)和余數(shù)。 (若r=0則ma） 例：a=11; m=7; 11=1*7+4; r=4 a=-11; m=7; -11=(-2)*7

4、+3; r=3 11 mod 7=4; -11 mod 7=3; 整數(shù)同余： 定義（同余）如果a mod m =b mod m，則稱整數(shù)a模正整數(shù)m同余于整數(shù)b，并寫ab（mod m）,m稱為模數(shù)。,注： 1*.如果ma-b，則ab（mod m） 證明：a-b=km,a=km+b 2*.相對于某個固定模數(shù)m的同余關(guān)系，是整數(shù)間的一種等價關(guān)系。具有等價關(guān)系的三點基本性質(zhì)： 自反性：對任意整數(shù)a有aa（mod m） 對稱性：如果ab(mod m)則ba（mod m） 傳遞性：如果ab (mod m）bc（mod m）則ac(mod m),3*.對于某個固定模m的同余式可以象普通的等式那樣相加相減和

5、相乘： (1)a(mod m)b(mod m)mod m=(ab)(mod m) (2)a(mod m)*b(mod m)mod m=a*b(mod m) 例如：11 mod 8=3 15 mod 8=7 (11+15)mod 8=(11 mod 8)+(15 mod 8)mod 8 =(3+7)mod 8=10 mod 8=2 例如：117 mod 13=? 112 mod 13=121 mod 13=4 114 mod 13=42 mod 13=3 117 mod 13=(112*114*11) mod 13 =(4*3*11)mod 13=2,例如：通過同余式演算證明5601是56的倍數(shù)

6、， 解： 53=12513(mod56) 于是有561691(mod56) 對同余式的兩邊同時升到10次冪， 即有56560-1。 證明：2231是47的倍數(shù)？,同理, 注意到26=64-30(mod47),于是 223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)(-30)*(32) (mod47) 1(mod47) 于是有 47223-1 定理：(消去律)對于abac（mod m）來說，若gcd(a,m)1則bc(mod m),例如1：附加條件不滿足的情況 63=182mod8 67=422mod8 但37mod8 例如2：附加條件滿足的情

7、況 53157mod8 511=557mod8 311mod8,歐幾里德算法,Euclid定理：對任意非負整數(shù)a和b： gcd(a,b)=gcd(b,a mod b) 例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6 gcd(11,10)=gcd(10,1)=gcd(1,0)=1,例: gcd (1970, 1066) 1970=1*1066+904 gcd(1066,904) 1066=1*904+162 gcd(904,162) 904=5*162+94 gcd(162,94) 162=1*94+68 gcd(94,68) 94=1*68+26 gcd(68,26) 6

8、8=2*26+16 gcd(26,16) 26=1*16+10 gcd(16,10) 16=1*10+6 gcd(10,6) 10=1*6+4 gcd(6,4) 6=1*4+2 gcd(4,2) 4=2*2+0 gcd(2,0),歐幾里德算法：假定ab0, Euclid(a,b) X=a; Y=b; 如果Y=0,返回X R=X mod Y X=Y Y=R,擴展的歐幾里德算法,如果gcd(d,f)=1，那么d有一個模f的乘法逆元，記作d-1, d* d-1mod f=1.,擴展的歐幾里德算法,Extended Euclid(f, d) （設(shè) f d） 1. (X1,X2,X3)(1,0,f);(

9、Y1,Y2,Y3)(0,1,d); 2. if Y3=0 then return X3=gcd(f, d)；無逆元; 3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f; 4. Q=X3/Y3 ； 5. (T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3); 6. (X1,X2,X3)(Y1,Y2,Y3); 7. (Y1,Y2,Y3)(T1,T2,T3); 8. goto 2。,求： gcd(4655,12075) 550-1mod 1723,費馬(Format)定理,Format定理：如果p是素數(shù)并且a是不能被p整除的正整數(shù),那么，a

10、p-11(mod p) Format定理的另一種形式： 對gcd（a，p）1 有apa(modp),例如：,a=7,p=19,求ap-1 mod p,解：72=4911mod19 74121mod197mod19 7849mod1911mod19 716121mod197mod19,ap-1=718=71672711mod191mod19,例如：,P=5, a=3, 35mod 5=3,歐拉（Euler）定理,小于n的且與n互素的正整數(shù)的個數(shù)，記作 例如： 小于24且與24互素的正整數(shù)有：1，5，7，11，13，17，19，23 為此,例子：,比7小而與7 互素的正整數(shù)為：1、2、3、4、5、

11、6。故 這12個數(shù)是： 1,2,4,5,8,10,11,13,16,17,19,20 9=32 1 2 4 5 7 8 ,歐拉定理,對于任何互素的整數(shù)a和n有：,中國剩余定理,例子：（孫子算經(jīng)）今有物不知其數(shù)。三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問物幾何？,答曰：二十三。 232*70+3*21+2*15(mod 105) （口訣：三人同行七十稀，五樹梅花廿一枝， 七子團圓月正半，除百零五便得知。） 問，70，21，15如何得到的？ 原問題為： 求解同余方程組,注意：解題口訣提示我們先解下面三個特殊的同余方程組 (1) (2) (3) 的特殊解 =?=?=? 以方程（1）為對象，相當于解一個這樣的同余方程 35y1(mod 3)， 解出y=2（mod 3）于是x35*2 70(mod105),類似地得到（2）、（3）方程的模105的解21、15。于是有：,中國剩余定理：設(shè)自然數(shù)m1,m2,mr兩兩互素，并記M=m1m2mr，b1.br表示r個整數(shù)，則同余方程組 （A） 在模M同余的意義下有唯一解。,例如： x1 mod 2 x2 mod 3 x3 mod 5 解： M=235=30 M1=15, M2=10,