算法數(shù)論課件

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

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

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

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

5、：RSA,ElGamal,Knapsnack,ECC等。,對(duì)稱密碼與公鑰密碼的特點(diǎn)： (1)對(duì)稱密碼算法速度快； (2)非對(duì)稱密碼密鑰管理簡(jiǎn)單。 實(shí)際網(wǎng)絡(luò)應(yīng)用中，采用非對(duì)稱密碼來交換對(duì)稱密碼算法的密鑰。,4.1 概述,,,,第四節(jié) 公鑰密碼算法,對(duì)稱密碼算法,公鑰密碼算法,加密,,,,,第四節(jié) 公鑰密碼算法,公鑰密碼算法,簽名,,混合加密通信,,,,第四節(jié) 公鑰密碼算法,4.2 陷門,每個(gè)

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

7、)=(p-1)×(q-1)； 例如：p=11,q=17; n=187, ?(n)=10×16=160 (2)選擇隨機(jī)數(shù)1<e<?(n),gcd(e,?(n))=1，計(jì)算： 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)的計(jì)算公式?(n)=(p-1)×(q-1)可知需要知道n的因子分解。當(dāng)n很大時(shí)，這是一個(gè)難題。,,,,第四節(jié) 公鑰密碼算法

9、,Bob的公鑰為(7,187)，私鑰為(23,187)； Alice要將保險(xiǎn)柜密碼88發(fā)送Bob。,,,密碼分析,,公共網(wǎng)絡(luò),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的素?cái)?shù)。,3.可解性分析,,,,第四節(jié) 公鑰密碼算法,依賴于將整數(shù)n分解為素因子的難度。EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，且為128的倍數(shù)。國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長度位512比特位。,從安全性考慮，p與q必為足夠大的素?cái)?shù)，使n的分解無

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

12、)，計(jì)算y=gx mod p，則 公鑰為(y,g,p)，私鑰為x,4.4 ElGamal算法,2.ElGamal加密消息m 選擇隨機(jī)數(shù)k，得到密文對(duì)(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選擇隨機(jī)數(shù)k=

13、4，計(jì)算得到的密文： a=gk mod p=24 mod 11=5 b=m·yk mod p=3·54 mod 11=5 (2)Alice對(duì)收到的密文(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é) 公鑰密碼算法,第一個(gè)公鑰算法，由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次測(cè)試,,,,第四節(jié) 公鑰密碼算法,超遞增背包： a1+a2+…+ai<ai+1 于是存在一個(gè)較簡(jiǎn)單的方法解決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)密鑰的生成： 選擇一個(gè)超遞增(a1,…,an)、整數(shù)m(m&g

17、t;a1+…+an, gcd(ai,m)=1)以及t(gcd(t,m)=1)； 計(jì)算： 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 解密消息： 計(jì)算 280×31-1%105