1、第5章 公鑰密碼主要內(nèi)容v 公鑰密碼體制的產(chǎn)生公鑰密碼體制的產(chǎn)生 v 公鑰密碼體制的基本原理公鑰密碼體制的基本原理 v RSA公鑰密碼體制公鑰密碼體制v 其它公鑰密碼算法其它公鑰密碼算法 安全服務(wù)安全服務(wù)v保密性保密性v驗(yàn)證（鑒別）驗(yàn)證（鑒別）v完整性完整性v不可抵賴性（不可否認(rèn)性）不可抵賴性（不可否認(rèn)性）v訪問(wèn)控制訪問(wèn)控制v可用性可用性 傳統(tǒng)密碼體制在應(yīng)用中的缺陷 v密鑰管理的麻煩密鑰管理的麻煩 在擁有大量用戶的通信網(wǎng)絡(luò)，若想讓兩兩用戶都能在擁有大量用戶的通信網(wǎng)絡(luò)，若想讓兩兩用戶都能進(jìn)行保密通信，即要求進(jìn)行保密通信，即要求n(1)(1)任意一對(duì)用戶共享一個(gè)會(huì)話密鑰，需要通過(guò)任意一對(duì)用戶共享一

2、個(gè)會(huì)話密鑰，需要通過(guò)保密信道進(jìn)行密鑰交換。保密信道進(jìn)行密鑰交換。n(2)(2)不同的用戶對(duì)共享的會(huì)話密鑰不相同不同的用戶對(duì)共享的會(huì)話密鑰不相同 對(duì)于分配中心，對(duì)于分配中心，NN個(gè)用戶則需要分配個(gè)用戶則需要分配NN2 2/2/2個(gè)會(huì)話個(gè)會(huì)話密鑰，大量的數(shù)據(jù)存儲(chǔ)和分配是一件很麻煩的事，密鑰，大量的數(shù)據(jù)存儲(chǔ)和分配是一件很麻煩的事，在 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 環(huán) 境 下 顯 的 尤 為 突 出 。在 計(jì) 算 機(jī) 網(wǎng) 絡(luò) 環(huán) 境 下 顯 的 尤 為 突 出 。傳統(tǒng)密碼體制在應(yīng)用中的缺陷v密鑰難以傳輸密鑰難以傳輸v不能提供法律證據(jù)不能提供法律證據(jù)v缺乏自動(dòng)檢測(cè)密鑰泄密的能力缺乏自動(dòng)檢測(cè)密鑰泄密的能力公鑰密碼體

3、制(Public key system) (Public key system) v公鑰密碼學(xué)與其他密碼學(xué)完全不同：公鑰密碼學(xué)與其他密碼學(xué)完全不同：公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換使用兩個(gè)獨(dú)立的密鑰使用兩個(gè)獨(dú)立的密鑰v公鑰密碼學(xué)的提出是為了解決兩個(gè)問(wèn)題：公鑰密碼學(xué)的提出是為了解決兩個(gè)問(wèn)題：密鑰的分配密鑰的分配數(shù)字簽名數(shù)字簽名v19761976年年DiffieDiffie和和HellmanHellman首次公開(kāi)提出了公鑰密碼學(xué)首次公開(kāi)提出了公鑰密碼學(xué)的概念，被認(rèn)為是一個(gè)驚人的成就。的概念，被認(rèn)為是一個(gè)驚人的成就。公鑰密碼體制的原理公鑰體制公鑰體制(

4、Public key system) (Diffie(Public key system) (Diffie和和Hellman,1976)Hellman,1976) 每個(gè)用戶都有一對(duì)選定的密鑰每個(gè)用戶都有一對(duì)選定的密鑰( (公鑰公鑰k k1 1；私鑰；私鑰k k2 2) )，公開(kāi)的密鑰公開(kāi)的密鑰k k1 1可以像電話號(hào)碼一樣進(jìn)行注冊(cè)公布。可以像電話號(hào)碼一樣進(jìn)行注冊(cè)公布。主要特點(diǎn)：主要特點(diǎn)：v加密和解密能力分開(kāi)加密和解密能力分開(kāi)v多個(gè)用戶加密的消息只能由一個(gè)用戶解讀，（用于多個(gè)用戶加密的消息只能由一個(gè)用戶解讀，（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）v只能由一個(gè)用戶加密消息而使多個(gè)用

5、戶可以解讀只能由一個(gè)用戶加密消息而使多個(gè)用戶可以解讀（可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字）。（可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字）。v無(wú)需事先分配密鑰。無(wú)需事先分配密鑰。v密鑰持有量大大減少密鑰持有量大大減少v提供了對(duì)稱密碼技術(shù)無(wú)法或很難提供的服務(wù)：提供了對(duì)稱密碼技術(shù)無(wú)法或很難提供的服務(wù)：如與哈希函數(shù)聯(lián)合運(yùn)用可生成數(shù)字簽名，可如與哈希函數(shù)聯(lián)合運(yùn)用可生成數(shù)字簽名，可證明的安全偽隨機(jī)數(shù)發(fā)生器的構(gòu)造，零知識(shí)證明的安全偽隨機(jī)數(shù)發(fā)生器的構(gòu)造，零知識(shí)證明等證明等 公鑰密碼體制有4個(gè)組成部分v明文：算法的輸入，它們是可讀信息或數(shù)據(jù)，用M表示；v密文：算法的輸出。依賴于明文和密鑰，對(duì)給定的消息，不同的密鑰產(chǎn)生

6、密文不同。用E表示；v公鑰和私鑰：算法的輸入。這對(duì)密鑰中一個(gè)可以公開(kāi)，一個(gè)保密。加密算法執(zhí)行的變換依賴于密鑰；v加密、解密算法 公鑰密碼體制下的秘密通信 保證機(jī)密性保證機(jī)密性 MEKbeE(M,Kbe)DKbdMKbe： Bob的公鑰Kbd ：Bob的私鑰保證真實(shí)性保證真實(shí)性 Kad： Alice的私鑰Kae ：Alice的公鑰MEKadE(M,Kad)DKaeM既保證機(jī)密性又保證真實(shí)性既保證機(jī)密性又保證真實(shí)性 Kad： Alice的私鑰Kae ：Alice的公鑰MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe： Bob的公鑰Kbd ：Bob的私鑰公鑰密碼

7、應(yīng)滿足的要求公鑰密碼應(yīng)滿足的要求v通訊雙方通訊雙方A A和和B B容易通過(guò)計(jì)算產(chǎn)生出一對(duì)密鑰（公容易通過(guò)計(jì)算產(chǎn)生出一對(duì)密鑰（公開(kāi)密鑰開(kāi)密鑰K1K1，私鑰密鑰，私鑰密鑰K2K2）。）。v在知道公開(kāi)密鑰在知道公開(kāi)密鑰K1K1和待加密報(bào)文和待加密報(bào)文MM的情況下，對(duì)的情況下，對(duì)于發(fā)送方于發(fā)送方A A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：vC = EC = Ek1k1（MM）v接收方接收方B B使用私有密鑰容易通過(guò)計(jì)算解密所得的密使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的報(bào)文：文以便恢復(fù)原來(lái)的報(bào)文：vM = DM = Dk2k2（C C）= D= Dk2k2EEk1

8、k1（MM） v除除A A和和B B以外的其他人即使知道公鑰以外的其他人即使知道公鑰k1k1，要確定私，要確定私鑰鑰K2K2在計(jì)算上也是不可行的。在計(jì)算上也是不可行的。v除除A A和和B B以外的其他人即使知道公鑰以外的其他人即使知道公鑰k1k1和密文和密文C C，要，要想恢復(fù)原來(lái)的明文想恢復(fù)原來(lái)的明文MM在計(jì)算上也是不可行的在計(jì)算上也是不可行的. . 單向陷門(mén)函數(shù)單向陷門(mén)函數(shù)v這些要求最終可以歸結(jié)到設(shè)計(jì)一個(gè)單向陷門(mén)函數(shù)。這些要求最終可以歸結(jié)到設(shè)計(jì)一個(gè)單向陷門(mén)函數(shù)。v單向函數(shù)：?jiǎn)蜗蚝瘮?shù)：一個(gè)單向函數(shù)是滿足下列條件的函數(shù)：它將一個(gè)一個(gè)單向函數(shù)是滿足下列條件的函數(shù)：它將一個(gè)定義域映射到值域，使得每

9、個(gè)函數(shù)值有一個(gè)唯一定義域映射到值域，使得每個(gè)函數(shù)值有一個(gè)唯一的原像，同時(shí)還要滿足下列條件：函數(shù)值計(jì)算很的原像，同時(shí)還要滿足下列條件：函數(shù)值計(jì)算很容易，而逆計(jì)算是不可行的。容易，而逆計(jì)算是不可行的。v單向陷門(mén)函數(shù)：?jiǎn)蜗蛳蓍T(mén)函數(shù)：所謂單向陷門(mén)函數(shù)是這樣的函數(shù)，即除非知道某所謂單向陷門(mén)函數(shù)是這樣的函數(shù)，即除非知道某種附加的信息，否則這樣的函數(shù)在一個(gè)方向上容種附加的信息，否則這樣的函數(shù)在一個(gè)方向上容易計(jì)算，而在另外的方向上要計(jì)算是不可行的。易計(jì)算，而在另外的方向上要計(jì)算是不可行的。有了附加的信息，函數(shù)的逆就可以在多項(xiàng)式時(shí)間有了附加的信息，函數(shù)的逆就可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出來(lái)。內(nèi)計(jì)算出來(lái)。v一個(gè)實(shí)用的公

10、開(kāi)密鑰密碼系統(tǒng)的建立和發(fā)展依賴于一個(gè)實(shí)用的公開(kāi)密鑰密碼系統(tǒng)的建立和發(fā)展依賴于找到一個(gè)單向陷門(mén)函數(shù)。找到一個(gè)單向陷門(mén)函數(shù)。 對(duì)公鑰密碼體制的攻擊v攻擊公開(kāi)密鑰密碼系統(tǒng)的方法有如下幾種：攻擊公開(kāi)密鑰密碼系統(tǒng)的方法有如下幾種：窮舉法窮舉法 對(duì)此防范措施應(yīng)為：使用長(zhǎng)的密鑰。但對(duì)此防范措施應(yīng)為：使用長(zhǎng)的密鑰。但是由于公鑰算法依賴于單向陷門(mén)函數(shù)，計(jì)算函數(shù)是由于公鑰算法依賴于單向陷門(mén)函數(shù)，計(jì)算函數(shù)的復(fù)雜性與密鑰的長(zhǎng)度的關(guān)系可能會(huì)增長(zhǎng)得更快。的復(fù)雜性與密鑰的長(zhǎng)度的關(guān)系可能會(huì)增長(zhǎng)得更快。因而密鑰大小必須足夠大，以保證安全性，但是因而密鑰大小必須足夠大，以保證安全性，但是又要足夠小以便加密解密使用。又要足夠小以便

11、加密解密使用。根據(jù)公鑰計(jì)算私鑰根據(jù)公鑰計(jì)算私鑰 在數(shù)學(xué)上證明，對(duì)任何公鑰在數(shù)學(xué)上證明，對(duì)任何公鑰算法，這種分析可能成功。因而對(duì)任何公鑰算法，算法，這種分析可能成功。因而對(duì)任何公鑰算法，對(duì)這種攻擊方法都需要測(cè)試對(duì)這種攻擊方法都需要測(cè)試 。常用加密算法常用加密算法 :RSA:RSA算法算法RSA AlgorithmRSA Algorithm概況概況vMIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.AdlemanRivest等1978, 1979發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MITMIT體制體制，后來(lái)被廣泛稱之為RSARSA體制體制。v它既可用于加密、又可用于數(shù)字簽名。vRSA

12、算法的安全性基于數(shù)論中大整數(shù)分解的困難性。v迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。算法原理vRSA算法使用了乘方運(yùn)算。v要求： 明文M經(jīng)過(guò)加密得到密文C： C=Me mod n 密文C經(jīng)過(guò)解密得到明文M： Cd mod n=(Me mod n)d mod n= Med mod n=M即：必須存在e，d，n，使Med mod n=M成立如何確定e,d,nv確定n：獨(dú)立地選取兩大素?cái)?shù)獨(dú)立地選取兩大素?cái)?shù)p p和和q q( (各各100100200200位十進(jìn)制位十進(jìn)制數(shù)字?jǐn)?shù)字) )計(jì)算計(jì)算 n n=p pq q，其歐拉函數(shù)值，其歐拉函數(shù)值 ( (n n)=()=(p p1

13、)(1)(q q1) 1)v確定e：隨機(jī)選一整數(shù)隨機(jī)選一整數(shù)e e，11 e e ( (n n) )，gcd(gcd( ( (n n), ), e e)=1)=1v確定d：根據(jù)根據(jù)ed=1ed=1 mod mod ( (n n) )在模在模 ( (n n) )下，計(jì)算下，計(jì)算d d這樣確定的e,d,n是否能使Med mod n=M成立呢？v因?yàn)橐驗(yàn)閑d=1ed=1 mod mod ( (n n) ) 即即ed=ked=k ( (n n)+1)+1 所以：所以：MMeded=M=Mk k ( (n n)+1)+1v如果如果MM和和n n互素互素，即，即gcd(M,n)=1 gcd(M,n)=1

14、那么，那么，根據(jù)歐拉定理根據(jù)歐拉定理( (如果如果gcd(a,n)=1gcd(a,n)=1，則，則 a(n) 1 mod n) )：有：有：MM ( (n n) ) 11 mod n mod n所以：所以：MMed ed M Mk k ( (n n)+1 )+1 MMMM ( (n n) ) k kmod nmod n M M11k kmod nmod n M M mod n mod nv如果如果MM和和n n不互素不互素，即，即gcd(M,n)1gcd(M,n)1，即，即MM和和n n有大于有大于1 1的公約數(shù)。的公約數(shù)。因?yàn)橐驗(yàn)閚=pqn=pq，而，而p p、q q都是素?cái)?shù)，不可再分解，都

15、是素?cái)?shù)，不可再分解，所以所以MM一定包含了一定包含了p p或或q q為因子。為因子。又因?yàn)橛忠驗(yàn)镸nMn，所以，所以MM不可能既是不可能既是p p的倍數(shù)又是的倍數(shù)又是q q的倍數(shù)。的倍數(shù)。v不妨設(shè)不妨設(shè)MM是是p p的倍數(shù)，的倍數(shù)，M=cpM=cp。 由于由于MM不是不是q q的倍數(shù)，所以的倍數(shù)，所以gcd(M,q)=1gcd(M,q)=1，則，則MM ( (q q) ) 11 mod q mod q ，所以：，所以：MM ( (q q) ) ( (p p) ) 11 mod q mod q 即即MM ( (n n) ) 11 mod q mod q ，即，即MM ( (n n) ) =1+k

16、q=1+kqvMM ( (n n) ) =1+kq=1+kq兩邊同乘以兩邊同乘以M=cpM=cp，則：，則：MM ( (n n)+1)+1=M+kqcp=M+kcn=M+kqcp=M+kcn把把kckc看作一個(gè)常數(shù)，則：看作一個(gè)常數(shù)，則：MM ( (n n)+1)+1=M+tn=M+tn即：即：MM ( (n n)+1 )+1 MM mod n mod n，即，即MM ( (n n) ) 11 mod n mod n因?yàn)橐驗(yàn)閑d=1 mod ed=1 mod ( (n n) )，所以：所以： MMed ed M Mk k ( (n n)+1 )+1 MMMM ( (n n) ) k kmod

17、nmod n M M11k kmod nmod n M M mod n mod n綜上綜上, ,這樣的這樣的e e，d d，n n可以實(shí)現(xiàn)加密可以實(shí)現(xiàn)加密C=Me mod n和解密和解密M=Cd mod n密鑰v以以n n，e e為公鑰。秘密鑰為為公鑰。秘密鑰為d d。( (p p, , q q不再需要，不再需要，可以銷毀?？梢凿N毀。) )RSA算法在計(jì)算上的可行性v加密和解密無(wú)論是加密還是解密都需要計(jì)算某個(gè)整數(shù)的模n整數(shù)次冪，即C=Me mod n、M=Cd mod n。但不需要先求出整數(shù)的冪再對(duì)n取模，而可利用模運(yùn)算的性質(zhì)： (a mod n) * (b mod n)= (a*b) mod

18、 n對(duì)于Me mod n，可先求出M1 mod n，M2 mod n，M4 mod n，再求Me mod nRSA算法在計(jì)算上的可行性v產(chǎn)生密鑰由于n是公開(kāi)的，為了避免攻擊者用窮舉法求出p和q（根據(jù)n=pq），應(yīng)該從足夠大的集合中選取p和q，即p和q必須是大素?cái)?shù)。目前還沒(méi)有有效的方法可以產(chǎn)生任意大素?cái)?shù)，通常使用的方法是：隨機(jī)挑選一個(gè)期望大小的奇數(shù)，然后測(cè)試它是否是素?cái)?shù)，若不是，則挑選下一個(gè)隨機(jī)數(shù)直至檢測(cè)到素?cái)?shù)為止。RSA算法在計(jì)算上的可行性v確定d和e有了p和q，可計(jì)算出 ( (n n)=()=(p p1)(1)(q q1) 1)根據(jù)根據(jù)gcd(gcd( ( (n n),e)=1),e)=1來(lái)

19、選擇來(lái)選擇e e，這一步計(jì)算量也不，這一步計(jì)算量也不大，因?yàn)閮蓚€(gè)隨機(jī)數(shù)互素的概率約為大，因?yàn)閮蓚€(gè)隨機(jī)數(shù)互素的概率約為0.60.6有了有了e e，再計(jì)算，再計(jì)算d=ed=e-1 -1 mod mod ( (n n) )，這里用的是擴(kuò)展，這里用的是擴(kuò)展的的EuclidEuclid算法。算法。選p=7，q=17。求n=pq=119，(n)=(p-1)(q-1)=96。取e=5，滿足1e(n)，且gcd(n),e)=1。確定滿足de=1 mod 96且小于96的d，因?yàn)?75=385=496+1，所以d為77。因此公開(kāi)鑰為5，119，秘密鑰為77，119。設(shè)明文m=19，則由加密過(guò)程得密文為C=195

20、 mod 1192476099 mod 119=66解密為6677mod 119=19RSA的安全性vRSA的安全性是基于分解大整數(shù)的困難性假定v如果分解n=pq，則立即獲得(n)=(p1)(q1)，從而能夠確定e的模(n)乘法逆dvn的長(zhǎng)度應(yīng)該介于1024bit到2048bit之間v由n直接求(n)等價(jià)于分解nRSA-129的故事的故事 v鶚鳥(niǎo)（ossifrage），又名髭兀鷹（lammergeier），是阿爾卑斯山上一種稀有的肉食禿鷹。它的翅膀展開(kāi)將近十米寬。鳥(niǎo)名的字面含義是“碎骨”。顧名思義，其習(xí)性令人毛骨悚然。vMirtin Gardner在1977年“Scientific Ameri

21、can”的專欄文章中介紹了RSA碼。為了顯示這一技術(shù)的威力，RSA公司的研究人員用一個(gè)129位的數(shù)N和一個(gè)4位數(shù)e 對(duì)這個(gè)關(guān)于禿鷹的消息作了編碼。Gardner刊登了那個(gè)密文，同時(shí)給出了N和e。RSA公司還懸賞100美元，獎(jiǎng)給第一個(gè)破譯這密碼的人。v96869 61375 46220 61477 14092 22543 55882 90575 99911 24574 31987 46951 20930 81629 82251 45708 35693 14766 22883 98962 80133 91990 55182 99451 57815 154 v一批松散組成的因子分解迷，大約有六百多人，分布在二十幾個(gè)國(guó)家。他們最后于1994年4月為RSA-129找到了64位數(shù)和65位數(shù)兩個(gè)素?cái)?shù)因子。v11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541 = 34905 29510 84765 09491 47849 61990 38981 33417 76463 84933 87843 99082 0577 *