算法數(shù)論課件_第1頁
已閱讀1頁,還剩23頁未讀 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

1、第十章 在密碼學中的應用,,,,網(wǎng)絡安全體系的五類服務,引 言,,攻擊分類,威脅密碼系統(tǒng)安全的是攻擊者。攻擊者首先通過監(jiān)聽等手段截獲密文。然后試圖通過對密文的分析來得到明文。由于通常加密解密算法是對外公開的,攻擊者往往對密鑰更感興趣。一旦攻擊者獲得密鑰,他就可以在系統(tǒng)更新密鑰之前,利用該密鑰解密一系列的密文。,,,,RSA:最流行的公鑰密碼算法,加密和數(shù)字簽名;ECC:橢圓曲線密碼,采用ElGamal算法,公鑰密碼算法,

2、安全性高,密鑰量小,靈活性好;DSA:數(shù)字簽名算法,是數(shù)字簽名的一部分,公鑰密碼算法,數(shù)字簽名。MD5(SHA-1):數(shù)字摘要算法,數(shù)字簽名,保證消息的完整性。,引 言,,,,第一節(jié) 現(xiàn)代對稱密碼,現(xiàn)代密碼設(shè)計準則: Kerchhoff原則:系統(tǒng)的安全性不依賴于對密文或 加密算法的保密,而依賴于密鑰。 惟一需要保密的是密鑰;

3、 --決定了古典密碼學與現(xiàn)代密碼學。 一個好的密碼將融合混淆和擴散 混淆:混淆明文的不同部分; 擴散:對攻擊者隱藏一些語言的局部特征; 現(xiàn)代密碼將結(jié)合換位和代替: 代替密碼在混淆上是有效的; 換位密碼擴散性較好。,,,,第一節(jié) 現(xiàn)代對稱密碼,現(xiàn)代密碼算法的特點: 只要保證密鑰安全,就能保證加密信息的安全。對稱密碼算法:很好地融合了混淆和擴散;

4、 DES、AES、IEDA、RC6等非對稱密碼算法:基于數(shù)學難題; RSA、ECC、ElGamal等,,,,第四節(jié) 公鑰密碼算法,所有的傳統(tǒng)密碼以及DES、AES等現(xiàn)代密碼都是一種對稱算法,即解密密鑰等價于加密密鑰; 非對稱密碼算法中,加密密鑰和解密密鑰是不相同的,因而可以將加密密鑰公開,將解密密鑰保密。 公鑰密碼的思想1976年被提出; 典型的有

5、:RSA,ElGamal,Knapsnack,ECC等。,對稱密碼與公鑰密碼的特點: (1)對稱密碼算法速度快; (2)非對稱密碼密鑰管理簡單。 實際網(wǎng)絡應用中,采用非對稱密碼來交換對稱密碼算法的密鑰。,4.1 概述,,,,第四節(jié) 公鑰密碼算法,對稱密碼算法,公鑰密碼算法,加密,,,,,第四節(jié) 公鑰密碼算法,公鑰密碼算法,簽名,,混合加密通信,,,,第四節(jié) 公鑰密碼算法,4.2 陷門,每個

6、非對稱密碼算法大都依賴于數(shù)論中某些處理過程的不可逆性,稱為陷門。 RSA密碼:因子分解難題;,ECC:橢圓曲線上的離散對數(shù)難題,aP=Q;,易:a,P?Q,難:P,Q?a,,,,,,,第四節(jié) 公鑰密碼算法,4.3 RSA算法,由Rivest、Shamir和Adlemar開發(fā),既能加密又可簽名,易理解和實現(xiàn),因而最流行。,密鑰的生成: (1)選擇兩個大素數(shù)p和q,計算: n=pq以及?(n

7、)=(p-1)×(q-1); 例如:p=11,q=17; n=187, ?(n)=10×16=160 (2)選擇隨機數(shù)1<e<?(n),gcd(e,?(n))=1,計算: d=e-1 mod ?(n); 例如:e=7,則d=23,1.RSA算法過程,,,,第四節(jié) 公鑰密碼算法,(3)則公鑰為(e,n),私鑰(d,n

8、); 例如:公鑰為(7,187);私鑰為(23,187)加密m:c=me mod n解密c:m=cd mod n RSA比較慢,一般選e為3,17,65537等等。公鑰私鑰的關(guān)系: d=e-1 mod ?(n); 已知e和n,要得到d,需要知道?(n),由?(n)的計算公式?(n)=(p-1)×(q-1)可知需要知道n的因子分解。當n很大時,這是一個難題。,,,,第四節(jié) 公鑰密碼算法

9、,Bob的公鑰為(7,187),私鑰為(23,187); Alice要將保險柜密碼88發(fā)送Bob。,,,密碼分析,,公共網(wǎng)絡,Alice,Bob,88,887 mod 187=11,11,1123 mod 187=88,Eve,2.舉例,,,,第四節(jié) 公鑰密碼算法,(1)歐拉定理:如果gcd(x,n)=1,則有: x?(n)=1 mod n (2)明文x與模數(shù)n要互素,不互素的概

10、率為:,(3)e,d必須與?(n)互素; (4)具有形式為n=pq的整數(shù)稱為Blum整數(shù)。 其中p和q都是模4同余3的素數(shù)。,3.可解性分析,,,,第四節(jié) 公鑰密碼算法,依賴于將整數(shù)n分解為素因子的難度。EDI攻擊標準使用的RSA算法中規(guī)定n的長度為512至1024比特位之間,且為128的倍數(shù)。國際數(shù)字簽名標準ISO/IEC 9796中規(guī)定n的長度位512比特位。,從安全性考慮,p與q必為足夠大的素數(shù),使n的分解無

11、法在多項式時間內(nèi)完成。要求n至少要有1024或者2048比特(十進制的308位或616位)。,4.安全性分析,,,,第四節(jié) 公鑰密碼算法,1985年發(fā)表,既可用于數(shù)字簽名又用于加密。其安全性依賴于離散對數(shù)難題。 離散對數(shù)問題DLP:給定素數(shù)p,ZnX的一個原根b和一個元素c。求解x,使得bx=c mod p。 1.描述 選取素數(shù)p>10150,一個模p的原根g以及隨機整數(shù)x(1<x<p

12、),計算y=gx mod p,則 公鑰為(y,g,p),私鑰為x,4.4 ElGamal算法,2.ElGamal加密消息m 選擇隨機數(shù)k,得到密文對(a,b)為: (a=gk mod p, b=m·yk mod p) 解密消息:b·a-x mod p=m·yk·(gk)-x mod p=m,,,,第四節(jié) 公鑰密碼算法,(1)Bob選擇隨機數(shù)k=

13、4,計算得到的密文: a=gk mod p=24 mod 11=5 b=m·yk mod p=3·54 mod 11=5 (2)Alice對收到的密文(5,5)解密: b·a-x mod p=5·5-4 mod 11=3,選p=11,g=2,私鑰x=4,則公鑰y=gx mod p=5Bob要將消息m=3傳送給Alice。,3.舉

14、例,,,,第四節(jié) 公鑰密碼算法,第一個公鑰算法,由Ralph Merkle和Martin Hellman開發(fā),只能用于加密。 1.描述 b=a1x1+a2x2+…+anxn 明文分組長度為n,消息為x1~xn,密文為b。 舉例1:明文:1 1 1 0 0 1 背包:1 5 6 11 14 20

15、 密文:b=1+5+6+20=32 解密:32=1x1+5x2+6x3+11x4+14x5 +20x6 奧妙在于背包問題有兩種: 普通背包:難解;超遞增背包:易解。,4.5 Knapsnack算法,,26次測試,,,,第四節(jié) 公鑰密碼算法,超遞增背包: a1+a2+…+ai<ai+1 于是存在一個較簡單的方法解決Knapsnack問題。 如果b<an

16、,則an不可能出現(xiàn)在大小為b的背包中; 如果b≥an,則an必須出現(xiàn)在大小為b的背包中。 舉例: 70=2x1+3x2+6x3+13x4+27x5+52x6 問題:授權(quán)者能解密,非授權(quán)者亦可。 解決:將超增長背包轉(zhuǎn)換為普通背包。,,,,第四節(jié) 公鑰密碼算法,2.Knapsnack算法過程 (1)密鑰的生成: 選擇一個超遞增(a1,…,an)、整數(shù)m(m&g

17、t;a1+…+an, gcd(ai,m)=1)以及t(gcd(t,m)=1); 計算: ci=t×ai mod m 則:背包序列(c1,c2,…,cn)為公鑰; 私鑰為(a1,…,an)和t。 (2)加密: 加密n位的消息x=(x1,…,xn),得到密文: b=c1x1+c2x2+…+cnxn (3)解密:

18、 t-1×b= t-1×(c1x1+c2x2+…+cnxn) =a1x1+a2x2+…+anxn,,,,第四節(jié) 公鑰密碼算法,3.舉例: 選m=105,t=31,則 {2,3,6,13,27,52} {62,93,81,88,102,37} 加密消息110101得到密文b=280 解密消息: 計算 280×31-1%105

溫馨提示

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

評論

0/150

提交評論