公鑰密碼技術(shù)

1、第5講 公鑰密碼技術(shù)楊 明紫金學(xué)院計(jì)算機(jī)系網(wǎng)絡(luò)信息安全2022-4-9內(nèi)容n公鑰密碼的基本概念nRSA公鑰體制nDiffie-Hellman密鑰交換n公開密鑰的管理New Directions in Cryptography,by Whitfield Diffie and Martin. E. Hellman, IEEE Trans. Inform. Theory, vol. IT-22, pp. 644-654, Nov. 1976 Whitfield DiffieMartin Hellman密碼學(xué)中革命-公鑰密碼公鑰密碼的革命性意義n新理論n基本工具是數(shù)學(xué)函數(shù)而不是代換和置換n安全性是基于

2、數(shù)學(xué)難題n新技術(shù)n雙密鑰:kekdn非對(duì)稱加密:使用其中一個(gè)密鑰加密，使用另一個(gè)密鑰解密n可公開一個(gè)密鑰：僅知道密碼算法和公鑰要確定私鑰在計(jì)算上是不可行的公鑰密碼體制的原理n五元組（M，C，K，E，D）n雙密鑰KnKe Kd且由Ke 不能計(jì)算出 Kd ； nKe可公開, Kd保密K=(PK, SK)nPK為公鑰，SK為私鑰nSK嚴(yán)格保密，可作為個(gè)人的身份指紋n加密算法E和解密算法D可逆n方案1：c=E(m,PK), mD(c, SK)n方案2：c=E(m,SK), mD(c, PK)公開密鑰密碼的優(yōu)點(diǎn)n簡化密鑰管理n實(shí)現(xiàn)數(shù)字簽名n簽名需要有無法被他人獲悉的能代表自身的秘密信息n簽名驗(yàn)證時(shí)不會(huì)泄

3、漏上述秘密信息n密鑰交換n實(shí)現(xiàn)通過公開網(wǎng)絡(luò)環(huán)境下的密鑰協(xié)商簡化密鑰管理n對(duì)稱加密n密鑰分配困難n密鑰容易泄漏n通信雙方都知道密鑰n密鑰分配中心KDCn密鑰量大n密鑰生存期短簡化密鑰管理n非對(duì)稱加密n只需重點(diǎn)保護(hù)自己的私有密鑰n公有密鑰可通過相關(guān)機(jī)構(gòu)進(jìn)行下載，安全壓力小n密鑰存儲(chǔ)量小，使用方便n密鑰生存期長公鑰密碼的基本工作方式n保持機(jī)密性nc=E(m,PKB), mD(c, SKB)n保持真實(shí)性nc=E(m,SKA), mD(c, PKA)AliceBobSKBRSA公鑰體制n介紹n第一個(gè)公鑰密碼算法n1978年由Rivest, Shamir和Adleman提出nRSA密碼被譽(yù)為是一種風(fēng)格幽雅

4、的公開密鑰密碼n迄今理論上最為成熟完善的公鑰體制n應(yīng)用廣泛n安全性基于大整數(shù)分解RSA公鑰體制n構(gòu)造過程,( )(1)(1)( )gcd( ( ), )11mod( )p qnpqf npqf ndf n ddadaf n選擇兩個(gè)素?cái)?shù)尋找一個(gè)與互素的數(shù)計(jì)算 逆元( , , , , ), ,; , ,Kn p q a dn ap q d公開保密:mod,:mod,admncacnma加密過程加密密鑰解密過程解密密鑰RSA算法驗(yàn)證nE和D的可逆性nc=E(m,e)=me mod nnD(c,d)=cd mod n=(me)dmod n ned1 mod(n) D(c,d)=(me)dmod n=m

5、 t(n)+1 n數(shù)論Euler定理 D(c,d)=m t(n)+1 =mn加密和解密運(yùn)算的可交換性n D(E(m)=(me)d mod n =(md)e mod n=E(D(m)RSA算法示例n產(chǎn)生密鑰n選擇兩個(gè)素?cái)?shù): p=17 & q=11n計(jì)算 n = pq =1711=187 f(n)=(p1)(q-1)=1610=160n選擇加密密鑰 e : gcd(e,160)=1; choose e=7n確定對(duì)應(yīng)的解密密鑰n de=1 mod 160 ， d 160 d=23 由于 237=161= 10160+1n公鑰PK=e, n=7,187n私鑰SK=d,p,q=23,17,11R

6、SA算法示例n加密與解密n公鑰PK=e, n=7,187n私鑰SK=d,p,q=23,17,11n明文m = 88n加密 c=me mod n= 887 mod 187 = 11 n解密 m =cd mod n= 1123 mod 187 = 88 RSA的安全性nRSA破解1mod( )( )(1)(1)()ddaf nf npqnpq計(jì)算e逆元大整數(shù)分解( , , , , ), ,; , ,Kn p q e dn ep q d公開保密nRSA的安全性依賴于大整數(shù)因子分解的難度n保密性良好RSA的安全性n安全性建議nRivest, Shamir和Adleman建議p和q為100位的十進(jìn)制數(shù)，

7、這樣n為200位的十進(jìn)制數(shù)。n估計(jì)200位的十進(jìn)制數(shù)的因式分解在億次機(jī)要進(jìn)行55萬年。n安全密鑰的產(chǎn)生np和q的長度接近np-1和q-1都包含大的素因子ngcd(p-1,q-1)很小混合密碼機(jī)制n比較nRSA涉及高次冪運(yùn)算，加密和解密速度較慢nDES加密和解密速度較RSA快近一個(gè)數(shù)量級(jí)nRSA宜于密鑰管理而DES難于密鑰管理n結(jié)合使用n使用RSA進(jìn)行密鑰的加密/解密n使用DES進(jìn)行數(shù)據(jù)的加密/解密對(duì)稱加密和非對(duì)稱加密的混合使用n加密過程n數(shù)據(jù)加密密鑰knc1=Edes(m,k) c2=RSA(k,pkb) c=(c1, c2)明文數(shù)據(jù)加密加密加密數(shù)據(jù) 數(shù)據(jù)加密密鑰接收者公鑰 加密的數(shù)據(jù)加密密鑰

8、對(duì)稱加密和非對(duì)稱加密的混合使用明文數(shù)據(jù)加密數(shù)據(jù) 數(shù)據(jù)加密密鑰接收者私鑰 數(shù)據(jù)加密密鑰 解密解密n解密過程n數(shù)據(jù)加密密鑰knc=(c1, c2)nk=RSA (c2, skb)nm=Ddes(c1, k)數(shù)字信封技術(shù)Diffie-Hellman密鑰交換n密鑰交換（密鑰協(xié)商）n通信雙方通過不安全信道協(xié)商密鑰n竊聽者無法獲得密鑰ABxaxbK=f(a,xb)K=f(b,xa)f(xa,xb)得不到KDiffie-Hellman密鑰交換AliceBob1. 選擇選擇x1,g and p.2. 計(jì)算計(jì)算y1 = gx1 mod p4. 選擇選擇 x2.5. 計(jì)算計(jì)算 y2 = gx2 mod p7. 計(jì)

9、算計(jì)算 z = y2x1 mod p = gx1x2 mod p7.計(jì)算計(jì)算 z = y1x2 mod p = gx1x2 mod pTime(y1,g,p)3(y2)6“相同的密鑰相同的密鑰”Diffie-Hellman密鑰交換n安全性n離散對(duì)數(shù)問題n問題n有限域上的離散對(duì)數(shù)問題是難解問題,modxg gpxABgxagxbK=g(xaxb)f(xa,xb)得不到KK=g(xaxb)DH密鑰交換算法示例nAlice和Bob協(xié)商后采用素?cái)?shù)p=353及其本原根a=3；nAlice選擇隨機(jī)數(shù)x=97，計(jì)算X=397 mod 353=40，并發(fā)送給Bob；nBob選擇隨機(jī)數(shù)y=233，計(jì)算Y=323

10、3 mod 353=248，并發(fā)送給Alice；nAlice計(jì)算k=Yx mod p=24897 mod 353=160；nBob計(jì)算k=Xy mod p=40233 mod 353=160。nk即為協(xié)商后的密鑰。公開密鑰的管理n公開密鑰的分配n公開宣布n公開可以得到的目錄n公開密鑰管理機(jī)構(gòu)n公開密鑰證書公開密鑰的管理n公開宣布n簡單方便，不受控制n易于偽造AKuaKuaKuaKuan公開可以得到的目錄n公開密鑰放在公開密鑰目錄n目錄由可信機(jī)構(gòu)負(fù)責(zé)n提高了安全性n仍有安全漏洞（篡改）AB公開密鑰目錄KuaKub公開密鑰的管理n公開密鑰管理機(jī)構(gòu)n使用公開密鑰密碼完成管理n用戶知道管理機(jī)構(gòu)的公鑰n存在瓶頸問題n公開密鑰證書n證書中包