第6章 公鑰密碼體制(RSA算法)

《第6章 公鑰密碼體制(RSA算法)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、密碼學(xué)基礎(chǔ)趙海燕zhaohaiyan@ccniit.com第6章　公鑰密碼體制(RSA算法)§6－1概　述問(wèn)題的提出：密鑰管理困難傳統(tǒng)密鑰管理兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)密鑰空間急劇增大。如:n=100時(shí)C(100,2)=4,995n=5000時(shí)C(5000,2)=12,497,500陌生人間的保密通信問(wèn)題數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求公鑰密碼體制公鑰密碼又稱為雙鑰密碼、非對(duì)稱密碼公鑰密碼體制提出的標(biāo)志性文獻(xiàn)：1976年，Diffie和Hellman，《密碼學(xué)的新方向》W.DiffieandM.E.Hellman

2、,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公鑰密碼算法基于數(shù)學(xué)函數(shù)而不是代替和換位操作。支持?jǐn)?shù)字簽名：用兩個(gè)密鑰中的任何一個(gè)加密的內(nèi)容，都可以用對(duì)應(yīng)的另一個(gè)密鑰解密。對(duì)公鑰密碼體制的要求（1）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開(kāi)密鑰KUb和私有密鑰KRb）。（2）在知道公開(kāi)密鑰和待加密報(bào)文M的情況下，對(duì)于發(fā)送方A，很容易通過(guò)公開(kāi)密鑰計(jì)算產(chǎn)生對(duì)應(yīng)的密文：C＝EKUb（M）（3）接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的報(bào)文：

3、M＝DKRb（C）＝DKRb（EKUb（M））（4）敵對(duì)方即使知道公開(kāi)密鑰KUb，要確定私有密鑰KRb在計(jì)算上是不可行的。（5）敵對(duì)方即使知道公開(kāi)密鑰KUb和密文C，要想恢復(fù)原來(lái)的報(bào)文M在計(jì)算上也是不可行的。（6）加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來(lái)使用（適用于部分公鑰密碼體制）:M＝DKRb(EKUb(M))（機(jī)密性）M=EKUb(DKRb(M))（數(shù)字簽名）對(duì)公鑰密碼體制的要求陷門設(shè)計(jì)公鑰密碼算法的關(guān)鍵——單向陷門函數(shù)滿足下列條件的函數(shù)f叫做單向陷門函數(shù)：(1)給定x，計(jì)算y=f(x)是容易的(2)給定y,計(jì)算x使y=f(x)是不可行的(3)存在δ，已知δ時(shí),對(duì)給定的任何y，若

4、相應(yīng)的x存在，則計(jì)算x使y=f(x)是容易的設(shè)計(jì)公鑰密碼算法的關(guān)鍵——單向陷門函數(shù)單向函數(shù)陷門性陷門信息（1）當(dāng)用陷門函數(shù)f作為加密函數(shù)時(shí)，可將f公開(kāi)，這相當(dāng)于公開(kāi)加密密鑰。此時(shí)加密密鑰便稱為公開(kāi)密鑰，記為Pk。（2）f函數(shù)的設(shè)計(jì)者將δ保密，用作解密密鑰，此時(shí)δ稱為秘密密鑰，記為Sk。（3）由于加密函數(shù)是公開(kāi)的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有Sk，他自然可以解出x=f-1(y)。（4）竊聽(tīng)者由于沒(méi)有Sk，則他由截獲的密文y=f(x)推測(cè)x是不可行的。設(shè)計(jì)公鑰密碼算法的關(guān)鍵——單向陷門函數(shù)公開(kāi)密鑰密碼系統(tǒng)的分析方法

5、蠻力攻擊(對(duì)密鑰)防范措施：采用長(zhǎng)密鑰公開(kāi)密鑰算法本身可能被攻破找到從公鑰計(jì)算私鑰的方法可能報(bào)文攻擊(對(duì)報(bào)文本身的強(qiáng)行攻擊)搜索報(bào)文本身的所有可能，跟密文匹配同等加密強(qiáng)度下DES和RSA密鑰長(zhǎng)度的比較公鑰密碼系統(tǒng)的應(yīng)用加密/解密數(shù)字簽名（第9章）密鑰交換（第7章）并不是所有的公開(kāi)密鑰密碼體制都支持加密解密、數(shù)字簽名和密鑰交換。如RSA、ECC三種都支持；DSA只用于數(shù)字簽名；DH只用于密鑰交換?；旌厦艽a系統(tǒng)——加密用對(duì)稱密碼加密明文，發(fā)揮速度優(yōu)勢(shì)用非對(duì)稱密碼加密密鑰，發(fā)揮密鑰分發(fā)管理優(yōu)勢(shì)混合密碼系統(tǒng)——解密用非對(duì)稱密碼解密密鑰用對(duì)稱密碼解密密文§6－2RSA由Rivest，Shamir和

6、Adleman在1978年提出，是目前唯一被廣泛接受并實(shí)現(xiàn)的通用公開(kāi)密鑰密碼算法。其數(shù)學(xué)基礎(chǔ)是Euler定理，并建立在大整數(shù)因子分解困難問(wèn)題之上。陷門RSA密碼體制描述明文空間P＝密文空間C=Zn密鑰的生成選擇互異素?cái)?shù)p、q，計(jì)算n=p×q，?(n)=(p-1)(q-1)選擇滿足條件gcd(?(n),e)=1，0

7、dn)Bob為接收（實(shí)現(xiàn)）者：Bob選擇p=7和q＝17則n=119,?(n)=6×16＝96＝25×3選擇一個(gè)正整數(shù)e(0