1、第五章公鑰密碼體制,上課安排,公鑰密碼體制的概念、思想和工作方式 數(shù)論簡介 Diffie-Hellman密鑰交換算法 RSA 算法 EIgamal公鑰算法 ECC算法,背景,在擁有大量用戶的通信網(wǎng)絡(luò)，若想讓兩兩用戶都能進行保密通信，即要求 (1)任意一對用戶共享一個會話密鑰 (2)不同的用戶對共享的會話密鑰不相同 對于分配中心，N個用戶則需要分配CN2個會話密鑰，大量的數(shù)據(jù)存儲和分配是一件很麻煩的事，在計算機網(wǎng)絡(luò)環(huán)境下顯的尤為突出。另外傳統(tǒng)密碼不易實現(xiàn)數(shù)字簽名，也進一步限制了其發(fā)展。,公開密鑰算法的提出,公鑰密碼學(xué)是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見文

2、獻： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654,公開密鑰算法,公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制 雙鑰體制的公鑰可以公開，因此也稱公鑰算法 公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了30多年的發(fā)展，但仍具有強勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用,加密與解密由不同的密鑰完成 加密： 解密： 知道加

3、密算法，從加密密鑰得到解密密鑰在計算上是不可行的 兩個密鑰中任何一個都可以作為加密密鑰，而另一個用作解密密鑰（不是必須的）,公開密鑰算法的基本要求,用公鑰密碼實現(xiàn)保密,用戶擁有自己的密鑰對(KU , KR) 公鑰 KU公開，私鑰KR保密,用公鑰密碼實現(xiàn)鑒別,條件：兩個密鑰中任何一個都可以用作加密而另外一個用作解密 鑒別： 鑒別保密,公開密鑰算法,公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(shù)分解難題（IFP）的算法體制 基于離散對數(shù)難題（DLP）算法體制 基于橢圓曲線離散對數(shù)難題（ECDLP）的算法體制,數(shù)論簡介,模運算 費瑪定理和歐拉定理 中國剩余定理,模運算,設(shè)n是一正整數(shù),a是整數(shù)

4、,若 a=qn+r, 0rn, 則a mod n=r 若(a mod n)=(b mod n),稱為a,b模n同余，記為ab mod n 稱與a模n同余的數(shù)的全體為a的同余類，記為a，a稱為這個同余類的代表元素,模運算,同余的性質(zhì) 若n|(a-b)，則ab mod n (a mod n) (b mod n),則ab mod n ab mod n，則ba mod n ab mod n， bc mod n，則ac mod n 求余運算a mod n將a映射到集合0,1,n-1,求余運算稱為模運算,模運算,模運算的性質(zhì) (a mod n)+(b mod n) mod n=(a+b) mod n (a

5、 mod n)-(b mod n) mod n=(a-b) mod n (a mod n)(b mod n) mod n=(ab) mod n,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,模運算,若x+y=0 mod n, y為x的加法逆元。每一元素都有加法逆元 若對x，有xy=1 mod n，稱y為x的乘法逆元。在上例中，并非所有x都有乘法逆元 定義Zn=0,1,.,n-1為模n的同余類集合。,Zn上模運算的性質(zhì),交換律 （x+w) mod n=(w+x) mod n (xw) mod n=(wx) mod n 結(jié)合律 (x+w)+y mod n=x+(w+y) mod n (

6、xw) y mod n=x (wy) mod n 分配律 w (x+y) mod n=wx+wy mod n,單位元,單位元 (0+w) mod n=w mod n (1w) mod n=w mod n 加法逆元：對wZn,有zZn，滿足w+z=0 mod n, z為w的加法逆元，記為z=-w。 加法的可約律 (a+b)(a+c) mod n, 則bc mod n 對乘法不一定成立，因為乘法逆元不一定存在。,模運算,定理:設(shè)aZn,gcd(a,n)=1,則a在Zn有乘法逆元 證明思路： 用反證法證明a和Zn中任何兩個不同的數(shù)相乘結(jié)果都不相同 從而得出aZn=Zn,因此存在xZn,使ax=1 m

7、od n 設(shè)p為素數(shù)，Zp中每一個非零元素都與p互素，因此有乘法逆元，有乘法可約律 (ab)=(ac) mod n, b=c mod n,費瑪定理,若p是素數(shù)，a是正整數(shù)且gcd(a,p)=1，則ap-11 mod p 證明： gcd(a,p)=1,則aZp=Zp, a(Zp-0)=Zp-0 a mod p,2a mod p,(p-1)a mod p =1,p-1 (a mod p) (2a mod p) (p-1)a mod p=(p-1)! mod p (p-1)! ap-1=(p-1)! mod p (p-1)!與p互素，所以乘法可約律，ap-1=1 mod p,歐拉函數(shù)與歐拉定理,歐拉函數(shù) 設(shè)n為一正整數(shù)，小于n且與n互素的正整數(shù) 的個數(shù)稱為n的歐拉函數(shù)，記為 定理：若n是兩個素數(shù)p和q的乘積，則 歐拉定理：若a和n互素,則,歐幾里德算法,求兩個正整數(shù)的最大公因子 兩個正整數(shù)互素，可以求一個數(shù)關(guān)于另一個數(shù)的乘法逆元 性質(zhì): 對任意非負整數(shù)a和正整數(shù)b,有 gcd(a,b)=gcd(b,a mod b),中國剩余定理,如果已知某個數(shù)關(guān)于一些兩兩互素的數(shù)的同余類集，就可以重構(gòu)這個數(shù) 定理(中國剩余定理)：