現(xiàn)代密碼學(xué)理論與實踐-09_第1頁
已閱讀1頁,還剩33頁未讀, 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,1/32,現(xiàn)代密碼學(xué)理論與實踐第9章 公鑰密碼學(xué)與RSA,Fourth Edition by William StallingsSlides by 楊壽保syang@ustc.edu.cnhttp://staff.ustc.edu.cn/~syang2012年10月,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,2/34,本章要點,非對稱密碼是一種密碼體制,其加密算法和解密算法

2、使用不同的密鑰,一個是公鑰,一個是私鑰。非對稱密碼也稱為公鑰密碼。非對稱密碼用兩個密鑰中的一個以及加密算法將明文轉(zhuǎn)換為密文,用另一個密鑰以及解密算法從密文恢復(fù)出明文。非對稱密碼可以用來保密、認(rèn)證或者兩者兼而有之。應(yīng)用最廣泛的公鑰密碼體制是RSA,破解RSA的困難,是基于分解大合數(shù)素因子的困難。,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,3/34,9.1 公開密鑰密碼體制的基本原理,對稱密碼體制的問題加密能力與解密能力是捆綁

3、在一起的密鑰更換、傳遞和交換需要可靠信道,密鑰分發(fā)困難如有N用戶,則需要C=N(N-1)/2個密鑰,n=1000時,C(1000, 2)≈500000, 密鑰管理困難無法滿足不相識的人之間通信的保密要求不能實現(xiàn)數(shù)字簽名非對稱密碼體制的基本特點加密能力與解密能力是分開的密鑰分發(fā)簡單需要保存的密鑰量大大減少,N個用戶只需要N個密鑰可滿足不相識的人之間保密通信可以實現(xiàn)數(shù)字簽名,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09

4、,4/34,公開密鑰密碼體制,公鑰算法依賴于一個加密密鑰和一個與之相關(guān)的不同的解密密鑰,算法有如下特點:僅根據(jù)密碼算法和加密密鑰來確定解密密鑰在計算上是不可行的兩個密鑰的任何一個都可用來加密,另一個用來解密公鑰密碼體制的組成明文:算法的輸入,可讀信息或數(shù)據(jù)加密算法:對明文進(jìn)行各種轉(zhuǎn)換公鑰和私鑰:算法的輸入,分別用于加密和解密密文:算法的輸出,依賴于明文和密鑰解密算法:根據(jù)密文和密鑰,還原明文,2024/3/27,現(xiàn)代密碼

5、學(xué)理論與實踐-09,5/34,公鑰算法的主要步驟,每個用戶產(chǎn)生密鑰,用來加密和解密消息每個用戶將其中一個密鑰(公鑰)存于公開的寄存器或其他可訪問的文件中,另一密鑰私有,每個用戶可以擁有若干其他用戶的公鑰若Bob要發(fā)消息給Alice,則要用Alice的公鑰對消息加密Alice收到消息后,用其私鑰對消息解密,由于只有Alice知道其自身的私鑰,所以其他的接收者均不能解密消息需要認(rèn)證時示證方用自己的私鑰加密消息(簽名)驗證方用示證方

6、的公鑰解密消息(驗證),如果結(jié)果證實公鑰與示證方的私鑰相吻合,則可以確認(rèn)示證方確為合法的用戶(認(rèn)證)加密和認(rèn)證可以結(jié)合起來,同時實現(xiàn)保密性和認(rèn)證,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,6/34,公開密鑰加密過程,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,7/34,公開密鑰認(rèn)證過程,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,8/34,常規(guī)和公開密鑰加密的重要特征,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,9/

7、34,公開密鑰密碼系統(tǒng):保密性,C = KUb(M) M = KRb(C),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,10/34,公開密鑰密碼系統(tǒng):認(rèn)證,S = KRa(M) M = KUa(S),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,11/34,公開密鑰密碼系統(tǒng):保密和認(rèn)證,C = KRa(KUb(M

8、)) M = KRb(KUa(C)),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,12/34,公鑰密碼體制的應(yīng)用,加密/解密:發(fā)送方用接收方的公鑰對消息加密數(shù)字簽名:發(fā)送方用其私鑰對消息簽名,可以對整體消息簽名或?qū)ο⒌恼灻荑€交換:通信雙方交換會話密鑰,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,13/34,產(chǎn)生一對密鑰(公鑰ke和私鑰kd)在計算上是容易的不難計算C=E(ke, m)和m

9、=D(kd, C)知道ke, 計算kd不可行不知道kd,即使知道ke, E, D及C,計算m也不可行對明文m, E(ke, m)有定義,且D(kd, E(ke, m))=m對密文C, D(kd, C)有定義,且E(ke, D(kd, C))=C加密變換和解密變換可以互換順序, 即D(E(m))=E(D(m))1976年,Whitfield Diffie和Martin Hellman提出這樣的設(shè)想:每個用戶A有一加密密鑰ka,

10、不同于解密密鑰ka’,可將加密密鑰ka公開,ka’保密,要求ka的公開不影響ka’的安全。若B要向A秘密發(fā)送明文m,可查A的公開密鑰ka,加密得密文C=Eka(m) A收到C后用只有A才擁有的解密密鑰ka’對C進(jìn)行解密得m=Dka’(C). 實用方案的發(fā)展依賴于單向陷井函數(shù),對公開密鑰密碼編碼系統(tǒng)的要求,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,14/34,Whitfield Diffie and Martin He

11、llman,WHITFIELD DIFFIE,MARTIN HELLMAN,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,15/34,公鑰密碼的分析,公鑰密碼易受窮舉攻擊,解決方法是使用長密鑰;同時為了便于實現(xiàn)加密和解密,又希望密鑰足夠短,目前僅限于密鑰管理和簽名。找出一種從給定的公鑰計算出私鑰是第二種攻擊方法,尚未在數(shù)學(xué)上證明對一特定公鑰算法這種攻擊是不可行的,因此包括RSA在內(nèi)的任何算法都是值得懷疑的。窮舉消息攻擊是第三種攻擊

12、形式,攻擊者用公鑰對所有可能的消息加密,并與傳送的密文匹配,從而解密任何消息;抵抗的方法是在要發(fā)送的消息后附加隨機(jī)數(shù)。,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,16/34,9.2 RSA算法,概述1977年,Rivest、Shamir、Adleman提出的非對稱密碼體制,是基于大合數(shù)的素因子分解問題的困難性。1994年4月一個小組通過Internet合作,8個月時間成功分解129位的數(shù),大約428比特;1999年分解155位

13、合數(shù),最新的記錄是2005年5月分解200位十進(jìn)制數(shù)。RSA專利于2000年9月20日到期。,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,17/34,R-S-A Ron Rivest, Adi Shamir, Len Adleman,(Left to Right: Ron Rivest, Adi Shamir, Len Adleman),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,18/34,算法流程隨機(jī)選擇兩個秘密大素數(shù)p

14、和q;計算公開模數(shù)n=p*q;計算秘密的歐拉指數(shù)函數(shù)φ(n)=(p-1)(q-1);選擇一個與φ(n)互素的數(shù),作為e或d;用Euclid算法計算模φ(n)的乘法逆元素,即根據(jù) ed mod φ(n)=1, 求d或e;加密:C = Me mod n解密:M= Cd mod n = (Me mod n)d mod n = M這里,φ(n)為歐拉商數(shù), 即集合(1, 2, ..., n-1)中與n

15、互素的數(shù)的個數(shù)。,RSA密碼體制基本原理,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,19/34,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,20/34,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,21/34,一個例子,p=17,q=11,n=pq=17x11=187, φ(n)=(p-1)(q-1) =16x10=160選擇e=7, gcd(7,160)=1, 23x7=161,

16、所以d=23公鑰KU={7,187}, 私鑰KR={23,187}, M=88加密計算C=887 mod 187887 mod 187 =[(884mod187)x882mod187)x881mod187)]mod187881mod187=88882mod187=7744mod187=77884mod187=59969536mod187=132887mod187=(88x77x132)mod187=894432mod187

17、=11解密計算M=1123 mod 187 = 88,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,22/34,RSA密碼體制基本原理,RSA算法滿足公開密鑰加密的要求, 必須符合下列條件:有可能找到e, d, n的值, 使得對所有M<n有 Med mod n = M對于所有M<n的值, 要計算Me和Cd是相對容易的在給定e和n時, 計算d是不可行的幾個關(guān)系φ(n) = φ(pq)=φ(p)φ(q)=(p

18、-1)(q-1), p,q 是素數(shù)ed mod φ(n)=1, ed = kφ(n)+1, 即ed mod φ(n) =1, d=e-1 mod φ(n),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,23/34,定理:給定ed mod φ(n) =1, m∈[0, n-1], gcd(m, n)=1, 則:(me mod n )d mod n = med mod n = m

19、證明:∵ ed mod φ(n) = 1∴ ed = kφ(n)+1,對某些整數(shù)k∴ med mod n = mkφ(n)+1 mod n = m(mkφ(n) mod n) mod n∵mkφ(n) mod n = (mφ(n) mod n)k mod n = 1k mod n = 1∴med mod n = (m* 1) mod n = m,RSA密碼體制基本原理,2024/3/27,現(xiàn)代密碼

20、學(xué)理論與實踐-09,24/34,RSA密碼體制基本原理,RSA方案概述素數(shù) p, q, 私有,選擇n=pq,公開,計算出 e, gcd(φ(n), e) = 1; 1 < e < φ(n), 公開,選擇d=e-1 mod φ(n), 私有,計算出RSA實現(xiàn)方面的考慮加密與解密模運算特性之一 [(a mod n) x (b mod n)] mod n = (a x b) mod n指數(shù)運算的

21、效率問題,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,25/34,計算ab mod n的算法和快速取模指數(shù)算法,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,26/34,確定兩個素數(shù)p和q,選擇e或d并計算另外一個檢驗素數(shù)隨機(jī)選擇一個奇整數(shù)n,如使用偽隨機(jī)數(shù)產(chǎn)生器隨機(jī)選一個整數(shù)a < n完成隨機(jī)素數(shù)性檢驗,如果n沒有通過檢驗,則另選n如果n通過了足夠多次的檢驗,則接受n,否則另選例:p = 5, q = 7, n

22、 = 35, φ(n)=24選d = 11,則e = inv(11, 24) = 11,M = 2C = me mod n = 211 mod 35 = 18M = Cd mod n = 1811 mod 35 = 2,密鑰的產(chǎn)生和檢驗素數(shù),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,27/34,RSA的安全性,RSA的安全性有三種可能的對RSA的攻擊方法強(qiáng)行攻擊:嘗試所有可能的密鑰數(shù)學(xué)攻擊:對兩個素數(shù)乘積的因

23、子分解(FAC問題)計時攻擊:依賴于解密算法的運行時間選擇密文攻擊:利用了RSA算法的性質(zhì)RSA的安全性問題依賴于大合數(shù)的素因子分解,即factorization problem (FAC),F(xiàn)AC的計算復(fù)雜性為T=exp((ln(n)ln(ln(n)))1/2),同DLP問題。,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,28/34,,p和q應(yīng)滿足下列約束條件:P和q的長度應(yīng)僅相差幾位,p和q都應(yīng)約在1075到10100之

24、間(p-1)和(q-1)都應(yīng)有一個大的素因子GCD(p-1, q-1)應(yīng)該較小 另外,已經(jīng)證明,若e<n且d<n1/4,則d很容易確定,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,29/34,,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,30/34,針對RSA的計時攻擊,計時攻擊類似通過觀察他人轉(zhuǎn)動保險柜撥號盤的時間長短來猜測密碼可能的解決辦法不變的冪運行時間,可能會降低性能在求冪運算中加

25、入隨機(jī)延時隱蔽:在執(zhí)行冪運算之前先將密文乘上一個隨機(jī)數(shù)RSA數(shù)據(jù)安全算法,用私鑰實現(xiàn)操作M=Cd mod n的過程如下產(chǎn)生0-n-1之間的秘密隨機(jī)數(shù)r計算C’=C(re) mod n, e是公開的指數(shù)計算M’=(C’)d mod n計算M=M’r -1 mod n, 其中r -1是r模n的乘法逆元,根據(jù) redmod n=r,可以證明結(jié)論是正確的,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,31/3

26、4,幾種不同復(fù)雜性的算法的代價,2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,32/34,選擇密文攻擊和最佳非對稱加密填充,基本的RSA算法容易受選擇密文攻擊(CCA)進(jìn)行CCA攻擊時,攻擊者選擇一些密文,并獲得相應(yīng)的明文,這些明文是利用目標(biāo)對象的私鑰解密獲得的因此,攻擊者可以選擇一個明文,運用目標(biāo)對象的公鑰加密,然后再用目標(biāo)對象的私鑰解密而取回明文。關(guān)鍵在于攻擊者可以利用RSA的性質(zhì),選擇數(shù)據(jù)塊使得當(dāng)用目標(biāo)對象的私鑰處理時,產(chǎn)生

27、密碼分析所需要的信息。利用CCA攻擊RSA的一個簡單例子利用了RSA如下的性質(zhì):E(PU, M1) x E(PU, M2)=E(PU, [M1 x M2]),2024/3/27,現(xiàn)代密碼學(xué)理論與實踐-09,33/34,CCA攻擊RSA,利用CCA攻擊,可以如下方式解密C=Me mod n計算 X=(C x 2e) mod n將X作為選擇明文提交,并收到Y(jié)=Xd mod n注意:X = (C mod n) x (2e mod

溫馨提示

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

評論

0/150

提交評論