第6章 公鑰密碼體制.ppt_第1頁(yè)
第6章 公鑰密碼體制.ppt_第2頁(yè)
第6章 公鑰密碼體制.ppt_第3頁(yè)
第6章 公鑰密碼體制.ppt_第4頁(yè)
第6章 公鑰密碼體制.ppt_第5頁(yè)
已閱讀5頁(yè),還剩27頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、1,第6章 公鑰密碼體制,2,背景,對(duì)稱密鑰編碼所面臨的難題 密鑰分配。 通信密鑰太多,管理和分發(fā)困難。 陌生人之間的通信 數(shù)字簽名和認(rèn)證。 密碼體制上的突破 Diffie & Hellman, “New Direction in Cryptography”, 1976。 首次公開提出了“公開密鑰密碼編碼學(xué)”的概念。 這是一個(gè)與對(duì)稱密碼編碼截然不同的方案。 提出公開密鑰的理論時(shí),其實(shí)現(xiàn)性并沒有又得到證明: 當(dāng)時(shí)還未發(fā)現(xiàn)滿足公開密鑰編碼理論的算法; 直到 1978 年,RSA 算法的提出。,3,基本特征,兩個(gè)密鑰: 使用一個(gè)密鑰進(jìn)行加密,用另一個(gè)相關(guān)的密鑰進(jìn)行解密 用加密密鑰生成的密文只有使用其

2、對(duì)應(yīng)的解密密鑰才能解密。 兩個(gè)密鑰的關(guān)系滿足: 兩個(gè)密鑰是不相同; 且在僅知道密碼算法和加密密鑰的情況下,要推斷解密密鑰在計(jì)算上是不可行的。,4,為了保障公鑰密碼體制的正確實(shí)現(xiàn),有以下要求 1.參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰(公開密鑰KUb 和私有密鑰KRb ) 2.在知道公開密鑰和待加密報(bào)文M的情況下,對(duì)于發(fā)送方A,很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文: 3.接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文,以便恢復(fù)原來(lái)的報(bào)文: 4.敵對(duì)方即使知道公開密鑰Kub,要確定私有密鑰KRb在計(jì)算上是不可行的。 5.敵對(duì)方即使知道公開密鑰Kub和密文C,要想恢復(fù)原來(lái)的報(bào)文M在計(jì)算上也是不可行的。 6.兩個(gè)密

3、鑰中的任何一個(gè)都可以用來(lái)加密,對(duì)應(yīng)的另一個(gè)密鑰用來(lái)解密(這一條不是所有公開密鑰密碼體制都適用):,(機(jī)密性實(shí)現(xiàn)) (數(shù)字簽名實(shí)現(xiàn)),5,優(yōu)點(diǎn),密鑰管理 加密密鑰是公開的; 解密密鑰需要妥善保存; 在當(dāng)今具有用戶量大、消息發(fā)送方與接收方具有明顯的信息不對(duì)稱特點(diǎn)的應(yīng)用環(huán)境中表現(xiàn)出了令人樂觀的前景。 數(shù)字簽名和認(rèn)證 只有解密密鑰能解密,只有正確的接收者才擁有解密密鑰。,6,公鑰密碼算法基礎(chǔ),單向函數(shù) 對(duì)于一個(gè)函數(shù) ,如果對(duì)于其定義域上的任意 x, 都容易計(jì)算,同時(shí) 對(duì)于其值域中幾乎所有的取值 y ,計(jì)算其逆函數(shù) 都是不可行的,則函數(shù) 被稱為單向函數(shù)。 可以提供單向函數(shù)的三大數(shù)學(xué)難題 大整數(shù)分解問(wèn)題(

4、簡(jiǎn)稱IFP); 離散對(duì)數(shù)問(wèn)題(簡(jiǎn)稱DLP); 橢圓曲線離散對(duì)數(shù)問(wèn)題(簡(jiǎn)稱ECDLP)。,7,公鑰密碼算法基礎(chǔ),單向陷門函數(shù) 對(duì)于一個(gè)單向函數(shù) ,如果其逆函數(shù) 在已知某些輔助信息的情況下容易求解得出,則稱該單向函數(shù) 為單向陷門函數(shù)。 構(gòu)造公鑰密碼系統(tǒng)的關(guān)鍵是如何在求解某個(gè)單向函數(shù)的逆函數(shù)中設(shè)置合理的“陷門”,8,單向陷門函數(shù)是滿足下列條件的函數(shù)f: 1.正向計(jì)算容易。即如果知道了密鑰KUb和消息x,容易計(jì)算 2.在不知道密鑰KRb的情況下,反向計(jì)算是不可行的。即如果只知道消息y而不知道密鑰KRb ,則計(jì)算 是不可行的。 3.在知道密鑰KRb的情況下,反向計(jì)算是容易的。即如果同時(shí)知道消息y和密鑰K

5、Rb ,則計(jì)算 是容易的。這里的KRb相當(dāng)于陷門,它和KUb是配對(duì)使用的。,9,公開密鑰密碼分析,密鑰窮舉攻擊 找到某種根據(jù)公開密鑰計(jì)算私有密鑰的方法 第三種攻擊方法是公開密鑰系統(tǒng)所特有的,它本質(zhì)上是一種可能報(bào)文攻擊。,10,公開密鑰密碼系統(tǒng)的應(yīng)用,機(jī)密性的實(shí)現(xiàn) 發(fā)送方用接收方的公開密鑰加密報(bào)文,接收方用自己對(duì)應(yīng)的私鑰來(lái)解密。 數(shù)字簽名,即防否認(rèn)性的實(shí)現(xiàn) 發(fā)送方用自己的私鑰“簽署”報(bào)文,接收方用發(fā)送方配對(duì)的公開密鑰來(lái)解密以實(shí)現(xiàn)鑒別。 密鑰交換 應(yīng)用于混合密碼系統(tǒng)。,11,RSA算法,分組密碼,安全性依賴于大數(shù)的因子分解。 是第一個(gè)較為完善的公鑰算法。 能夠同時(shí)用于加密和數(shù)字簽名,且易于理解和操

6、作。 RSA是被研究得最廣泛的公鑰算法,從提出到現(xiàn)在已近二十年,經(jīng)歷了各種攻擊的考驗(yàn),逐漸為人們接受,被普遍認(rèn)為是目前最優(yōu)秀的公鑰算法之一。 目前仍然無(wú)法從理論上證明它的保密性能究竟如何 ,因?yàn)槟壳叭藗儾]有從理論上證明破譯RSA的難度與大整數(shù)分解問(wèn)題的難度等價(jià)。,12,RSA算法,設(shè)分組長(zhǎng)度為l bit,每個(gè)分組 M 被看作是一個(gè) l bit 的二進(jìn)制值。 取某一個(gè)整數(shù) n ,使對(duì)所有 M,有 M n 一般, n 的取值滿足 2l n 2 l+1。 加密算法 C = Me mod n。 解密算法 M = Cd mod n = (Me)d mod n = Med mod n。 加密密鑰(公開密

7、鑰)為 KU = e,n。 解密密鑰(私有密鑰)為 KR = d,n。,返回,13,RSA算法,要求: e, d, n 使對(duì)所有 M n 都有: M = Med mod n 對(duì)所有 M n , Me 和 Cd 的計(jì)算相對(duì)簡(jiǎn)單。 給定 e, n ,要推斷 d 在計(jì)算上不可行。 問(wèn)題:怎樣找到滿足 M = Med mod n 的 e, d, n ? 需要利用數(shù)論作為其數(shù)學(xué)基礎(chǔ)。,14,數(shù)論術(shù)語(yǔ),最大公因子 :任意有限個(gè)整數(shù) 的公因子中的最大一個(gè)。必然存在并且惟一,記為 。 最小公倍數(shù) :任意有限個(gè)整數(shù) 的公倍數(shù)中的最小一個(gè) 。必然存在并且惟一,記為 。 同余式 :設(shè)n是一個(gè)正整數(shù), .如果 ,則稱

8、a和b模n同余,記作: ,稱整數(shù)n為同余模。 模運(yùn)算遵循交換律,結(jié)合律,分配律,15,指數(shù)模運(yùn)算可以看作是多次乘法。例:計(jì)算,法二:,法一:,RSA,16,例:通過(guò)同余式演算證明560-1 是56的倍數(shù) 解:注: ,于是有 對(duì)同余式的兩邊同時(shí)升到10次冪,即,17,模運(yùn)算的加法消去率:若 則, 模運(yùn)算的乘法消去率:若 若 則 加法逆元 :設(shè) ,如果存在 滿足 ,則稱x是a的模n加法逆元。 乘法逆元 :設(shè) ,如果存在 滿足 ,則稱x是a的模n乘法逆元,記為 a-1 (mod n)。,18,歐拉函數(shù),歐拉函數(shù)(Eulers totient function) 歐拉函數(shù)(n):表示小于 n 且與 n

9、 互素的正整數(shù)的個(gè)數(shù); 歐拉函數(shù)的性質(zhì): 對(duì)任意素?cái)?shù) p,有 (p) = p 1; 對(duì)任意兩個(gè)素?cái)?shù) p、q,則對(duì) n = pq 有: (n) = (pq) = (p)(q) = (p1)(q1),19,歐拉定理,如a 和 n 是互素的整數(shù),則有: 等價(jià)形式:,20,歐拉定理推論,有兩個(gè)素?cái)?shù) p 和 q, 令 n = pq , 對(duì)任意整數(shù) k 和 m (0mn), 有下列等式成立: 其中:(n) = (p-1)(q-1)。,21,歐拉定理與RSA算法,RSA算法要求: M = Med mod n RSA算法描述: 選取足夠大的兩個(gè)素?cái)?shù) p 和 q, 令 n = pq , 則(n) = (p-1)

10、(q-1)。 選取適當(dāng)?shù)募用苊荑€ e 和解密密鑰 d ,使之滿足 。 公開 n 和 e ,保密 p, q 和 d。 加密運(yùn)算: 解密運(yùn)算:,返回,22,RSA算法實(shí)現(xiàn)步驟,生成兩個(gè)大素?cái)?shù) p 和 q ; 計(jì)算 , ; 選擇隨機(jī)數(shù) e(即加密密鑰), 使之滿足 ; 計(jì)算解密密鑰 ; 公布整數(shù) n 和加密密鑰 e。,23,證明 在條件 下成立。其中 是歐拉函數(shù),表示不超過(guò)n且與n互素的整數(shù)個(gè)數(shù)。 證明:,24,RSA 實(shí)現(xiàn)上的問(wèn)題,密鑰生成時(shí),如何找到足夠大的素?cái)?shù) p 和 q ? 對(duì)一個(gè)很大的整數(shù),如何判定它是否是素?cái)?shù)? 在 n、m、e、d 非常大的情況下,如何計(jì)算 me mod n ?,25,R

11、SA 實(shí)現(xiàn)上的相關(guān)算法,模加; 模乘; 擴(kuò)展的輾轉(zhuǎn)相除法(歐幾里德( Euclidean )算法 ); 求逆; 中國(guó)剩余定理; 求冪算法; 素性測(cè)試算法。,26,歐幾里德( Euclidean )算法,一個(gè)用于計(jì)算兩個(gè)整數(shù)的最大公因子的有效算法 ,算法依據(jù): 。 描述如下: (1)輸入 a 和 b ,其中, , , ; (2)如果 則依次完成: ,否則返回 a ; (3)輸出 。,27,中國(guó)剩余定理,求解如下形式的同余方程組 其中: , , , 。 令r個(gè)整數(shù) 兩兩互素, 是任意r個(gè)整數(shù),則r個(gè)同余方程組 (其中 )模 有惟一解,且該解的表達(dá)式為: 其中, , , 。,28,如何產(chǎn)生足夠大的隨

12、機(jī)素?cái)?shù),實(shí)際應(yīng)用所采用的方法是:首先,產(chǎn)生一個(gè)足夠大的隨機(jī)數(shù),然后,通過(guò)采用一個(gè)概率多項(xiàng)式時(shí)間算法來(lái)檢測(cè)該隨機(jī)數(shù)是否為素?cái)?shù)(即是否具有素性)。 常用的兩個(gè)素性測(cè)試算法: Solovay-Strassen 素性測(cè)試; Miller-Rabin素性測(cè)試。,29,Miller-Rabin素性測(cè)試算法,記 ,其中,m是奇數(shù)。 選擇一個(gè)隨機(jī)整數(shù)a, ,計(jì)算 。 如果 ,則回答“n是素?cái)?shù)”并退出;否則 for i=0 to k-1 do 如果 ,則回答“n是素?cái)?shù)”并退出; 否則 。 回答“n是合數(shù)”。,30,RSA安全性分析,影響RSA算法安全性的因素主要有 : 密碼分析者若能計(jì)算 ,p和q,即能分解n。實(shí)際上知道 就可以從公鑰e計(jì)算得出私鑰d。 在構(gòu)造n時(shí)應(yīng)選擇p和q,使得p-1 和q-1 有大的素因子。一般選擇p和 (p-1)/2均是素?cái)?shù)的p。 通過(guò)截獲來(lái)自不同用戶的密文,密碼分析者能夠有機(jī)會(huì)計(jì)算出密文,因此,不同用戶之間不要共享整數(shù)n。,31,RSA 的性能,同等強(qiáng)度的 DES 與 RSA 比較,硬件實(shí)現(xiàn):比 DES 慢 1000 倍。 軟件實(shí)現(xiàn):比 DES 慢 100 倍。 安全強(qiáng)度:,32,RSA的缺點(diǎn),RSA的缺點(diǎn)主要有:

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論