1、6.3 非對(duì)稱(chēng)密碼體制（公鑰密碼體制）對(duì)稱(chēng)密碼體制中密鑰管理的困惑網(wǎng)絡(luò)中有n個(gè)用戶(hù)，兩兩之間要進(jìn)行保密通信，在對(duì)稱(chēng)密碼體制下，需要多少把密鑰？答: 需要Cn2把密鑰如何解決？每個(gè)用戶(hù)擁有一個(gè)郵筒。發(fā)送方向接收方郵筒的投遞口投遞信息，只有接收方自己用鑰匙才能打開(kāi)郵筒獲得信息。公鑰體制中，郵筒投遞口相當(dāng)于公鑰，郵筒鑰匙相當(dāng)于私鑰。發(fā)送方和接收方無(wú)需共享密鑰，就可進(jìn)行保密通信。Diffie-Hellman密鑰協(xié)商1976， W.Diffie和M.Hellman， New Directions in Cryptography提出公鑰密碼系統(tǒng)的構(gòu)想為對(duì)稱(chēng)密碼系統(tǒng)實(shí)現(xiàn)了一個(gè) 密鑰交換協(xié)議密鑰協(xié)商：在公共網(wǎng)

2、絡(luò)上為發(fā)送方和接收方協(xié)商一個(gè)密鑰Diffie, Hellman, Merkle加密器Ek解密器Dk私密通道明文密文明文kk離散對(duì)數(shù)困難性問(wèn)題已知整數(shù)g和p(大整數(shù))，求出一個(gè)整數(shù)x滿(mǎn)足y=gx(mod p)是困難的。xy = 2x(mod 11)Diffie-Hellman密鑰交換協(xié)議發(fā)送方A和接收方B如何秘密地協(xié)商一個(gè)共同的密鑰K？（1）A選一個(gè)大素?cái)?shù)p和有限域Zp的本原元g（2）A發(fā)送三個(gè)數(shù)（gx mod p，g，p）給接收方B， x只有A知道（3）B收到之后，發(fā)送（gy mod p）給接收方A， y只有B知道（4）AB雙方都接收到對(duì)方發(fā)的數(shù)后， A計(jì)算（ gy mod p ）x = gx

3、y mod p B計(jì)算（ gx mod p ）y = gxy mod p 密鑰 K = gxy mod pAB(gx mod p, g, p)(gy mod p)K = gxy mod pxy公鑰密碼系統(tǒng)1976， W.Diffie和M.Hellman， 提出公鑰密碼系統(tǒng)的概念和原理1977，麻省理工學(xué)院的Ron Rivest，Adi Shamir和Len Adleman，RSA算法AB加密解密密文B的公鑰B的私鑰明文明文Diffie, Hellman, Merkle大整數(shù)分解困難問(wèn)題將兩個(gè)素?cái)?shù)相乘得到結(jié)果十分容易，但要將一個(gè)大整數(shù)分解成兩個(gè)素?cái)?shù)的乘積卻非常困難p * q = n （容易）n

4、= p * q （困難） 1977年，科學(xué)美國(guó)人雜志懸賞100美元征求一個(gè)129位整數(shù)的素?cái)?shù)因子分解。直到1994年，由Lenstra領(lǐng)導(dǎo)的一隊(duì)數(shù)學(xué)家在互聯(lián)網(wǎng)上用600臺(tái)計(jì)算機(jī)協(xié)同工作了8個(gè)月才完成這個(gè)數(shù)的分解RSA算法發(fā)送方A向接收方B發(fā)送消息B密鑰生成 （1）B隨機(jī)選擇兩個(gè)大素?cái)?shù)p和q （2）B計(jì)算n=p*q和 (n) = (p-1)*(q-1) （3）隨機(jī)選一個(gè)小于(n)且與(n)互素的整數(shù)e, （4）計(jì)算出e關(guān)于模(n)的乘法逆元d （5）B得到公鑰(e,n)，私鑰(d,n)加密解密過(guò)程（明文以分組為單位加密） A 加密：C = Me mod n B 解密：M = Cd mod n (

5、M：明文，C：密文)(1)任選兩個(gè)素?cái)?shù)p=7,q=17(2)n =p*q = 7 * 17 = 119, (n) = (p-1)(q-1) = 6 * 16 = 96(3)取小于(n)=96，且與96互素的整數(shù)e=5(4)計(jì)算出e=5關(guān)于mod 96的乘法逆元 d, 即e*d = 1 mod 96。d = 77(5)得到B的公鑰(e,n) = (5,119)，私鑰(d,n) = (77,119)加密明文m=19C=195 mod 119 =66 解密密文 C = 66M = 6677 mod 119 = 19橢圓曲線(xiàn)密碼體制（ECC）1985年，Koblitz和Miller，Elliptic

6、Curve Cryptography (ECC)基于橢圓曲線(xiàn)離散對(duì)數(shù)的困難問(wèn)題比大整數(shù)分解問(wèn)題、離散對(duì)數(shù)困難問(wèn)題要難解得多以高效著稱(chēng)，密鑰短，安全性高橢圓曲線(xiàn)方程E: y2 = x3 + ax +bxy有限域上的橢圓曲線(xiàn)有限域Z23 = 0,1,2,22, x Z23, y2 = x3 + x +10 mod 23xyx = 1時(shí)， 1 + 1 + 10 mod 23 = 12, y2 mod 23 = 12, 所以，y = 9 (23 * 3 + 12 = 81), y = 14 (23 * 8 + 12 =196)橢圓曲線(xiàn)群y2 = x3 + x +10 mod 23方程中的所有點(diǎn)構(gòu)成了一

7、個(gè)集合，在這個(gè)集合上定義了一個(gè)加法，構(gòu)成橢圓曲線(xiàn)群xyPQ-RR加法：P+Q = RxyP-R加法（2倍點(diǎn)）：P+P = 2PR橢圓曲線(xiàn)離散對(duì)數(shù)困難問(wèn)題若已知橢圓曲線(xiàn)上兩點(diǎn)P和Q滿(mǎn)足Q = kP，要求出整數(shù)k是非常困難的。由2P可以推廣到k倍點(diǎn)即k個(gè)P點(diǎn)相加kP = P + P + + Pk個(gè)橢圓曲線(xiàn)加密算法發(fā)送方A向接收方B傳遞信息m，使用橢圓曲線(xiàn)Ep和基點(diǎn)G（G為橢圓曲線(xiàn)上一點(diǎn)）（1）B設(shè)定自己的私鑰d和公鑰Q=dG(d為整數(shù))（2）A隨機(jī)選擇一個(gè)整數(shù)k， 計(jì)算(x1,y1) = kG， 計(jì)算(x2,y2) = kQ A對(duì)m進(jìn)行加密，c = m * x2 mod p A將密文c和(x1,y

8、1)傳遞給B（3）B計(jì)算(x2,y2) = d(x1,y1) B對(duì)c進(jìn)行解密 m = c * x2-1 mod pRSA vs 橢圓曲線(xiàn)RSA 密鑰長(zhǎng)度ECC密鑰長(zhǎng)度長(zhǎng)度比值5121065:17681326:110241607:1204821010:12100060035:1RSA與ECC在同等安全強(qiáng)度下的密鑰長(zhǎng)度PPT模板下載：/moban/ 行業(yè)PPT模板：/hangye/ 節(jié)日PPT模板：/jieri/ PPT素材下載：/sucai/PPT背景圖片：/beijing/ PPT圖表下載：/tubiao/ 優(yōu)秀PPT下載：/xiazai/ PPT教程： /powerpoint/ Word教程： /word/ Excel教程：/excel/ 資料下載：/ziliao/ PPT課件下載：/kejian/ 范文下載：/fanwen/ 試卷下載：/shiti/ 教案下載：/jiaoan/ 單向陷門(mén)函數(shù)單向陷門(mén)函數(shù)y = f(x,