計算機網(wǎng)絡(luò)安全概論

1、計算機網(wǎng)絡(luò)安全概論1附2 數(shù)據(jù)加密技術(shù)計算機網(wǎng)絡(luò)安全概論2密碼系統(tǒng)的模型信源編碼器信道解碼器接收者秘密信道密碼分析者密鑰源密鑰源計算機網(wǎng)絡(luò)安全概論3對稱與非對稱密鑰加密 傳遞信息是否安全？A P B計算機網(wǎng)絡(luò)安全概論4對稱與非對稱密鑰加密 使用鑰匙是否可保證安全？A B密鑰發(fā)布（Distribution）或交換（exchange）計算機網(wǎng)絡(luò)安全概論5密鑰交換協(xié)議算法的歷史76年Diffie和Hellman發(fā)表了“密碼學(xué)的新方向”，奠定了公鑰密碼學(xué)的基礎(chǔ)Diffie-Hellman密鑰交換協(xié)議算法使用此方法確定對稱密鑰交換Ralph Merkle,and independently Marty

2、Hellman Whit Diffie,invented the notion of public-key cryptography.In November 1976,Diffie and Hellman published Directions in Cryptography, proclaiming “We are at the brink of a revolution in cryptography.”計算機網(wǎng)絡(luò)安全概論6密鑰交換協(xié)議算法的歷史78年，RSA算法公鑰技術(shù)是二十世紀最偉大的思想之一 改變了密鑰分發(fā)的方式可以廣泛用于數(shù)字簽名和身份認證服務(wù)RSA(Ron Rivest,Adi

3、 Shamir,Len Adleman,1977)計算機網(wǎng)絡(luò)安全概論7DH算法描述Alice與ob確定兩個大素數(shù)n和g，這兩個整數(shù)不保密， Alice與ob 可以使用不安全信道確定這兩個數(shù)Alice選擇另一個大隨機數(shù)x，并計算A如下： A=gx mod nAlice將發(fā)給obob選擇另一個大隨機數(shù)y，并計算B如下： B=gy mod nob將發(fā)給Alice計算秘密密鑰K1如下： K1=Bx mod n計算秘密密鑰K2如下： K2=Ay mod n計算機網(wǎng)絡(luò)安全概論8算法示例Alice與ob確定兩個大素數(shù)n和g，這兩個整數(shù)不保密， Alice與ob 可以使用不安全信道確定這兩個數(shù)設(shè) n=11,g

4、=7Alice選擇另一個大隨機數(shù)x，并計算A如下： A=gx mod n設(shè) x=3,則 A = 73 mod 11 = 343 mod 11 = 2Alice將發(fā)給ob Alice將發(fā)給obob選擇另一個大隨機數(shù)y，并計算B如下： B=gy mod n設(shè) y=6,則 B = 76 mod 11 = 117649 mod 11 = 4ob將發(fā)給Aliceob將4發(fā)給Alice計算機網(wǎng)絡(luò)安全概論9算法示例計算秘密密鑰K1如下： K1=Bx mod n有 K1 = 43 mod 11 = 64 mod 11 = 9計算秘密密鑰K2如下： K2=Ay mod n 有 K2 = 26 mod 11 =

5、64 mod 11 = 9計算機網(wǎng)絡(luò)安全概論10數(shù)學(xué)理論安全性在于有限域中的離散對數(shù)計算難度比同一個域中的指數(shù)計算難得多Alice在第步的計算：K1=Bx mod nB=gy mod nK1=（gy）x mod n=gyx mod nBob在第步的計算：K2=Ay mod nA=gx mod n K2=（gx）y mod n=gxy mod nK1=K2=K Alice與Bob交換n、g 、A 、B。根據(jù)這些值并不容易求出x（Alice知道）和 y（ Bob知道）,數(shù)學(xué)上對于足夠大的數(shù)，求x與y是相當復(fù)雜的a b(mod n) a0而0bn, b是a/n的余數(shù)，a為同余例：2311(mod 1

6、2)求模指數(shù)y=ax mod n求一個數(shù)的離散對數(shù)求x，使ax b(mod n) 計算機網(wǎng)絡(luò)安全概論11對稱密鑰的問題A、B(A-B) 1A、B、C (A-B 、 A-C 、 B-C ) 3A、B、C 、D (A-B 、 A-C 、 A-D 、 B-C 、 B-D 、 C-D ) 6n n*(n-1)/2N=1000 499500鑰匙的管理非常復(fù)雜（引入管鑰匙的T）計算機網(wǎng)絡(luò)安全概論12算法問題中間人攻擊Alicen=11,g=7Tomn=11,g=7Bobn=11,g=71Alicex=3Tomx=8,y=6Boby=92AliceA=gx mod n =73 mod 11 =2TomA=g

7、x mod n =78 mod 11 =9BobB=gy mod n =79 mod 11 =83B=gy mod n =76 mod 11 =4計算機網(wǎng)絡(luò)安全概論13中間人攻擊 A=2截獲A=B=8A=44計算機網(wǎng)絡(luò)安全概論14中間人攻擊 AliceA=2, B=4TomA=2, B=8BobA=9, B=85AliceK1=Bx mod n =43 mod 11 =9TomK1=Bx mod n =88 mod 11 =5BobK2=Ay mod n =99 mod 11 =56K2=Ay mod n =26 mod 11 =9計算機網(wǎng)絡(luò)安全概論15非對稱密鑰A、B不必同時訪問T以獲得密鑰

8、對B訪問T取得一個鎖和密鑰（K1）,將鎖和密鑰（K1）發(fā)給AB告訴A可以使用這個鎖和密鑰（K1）封箱B擁有不同組相關(guān)的密鑰（K2）， B從T取得（K2） ，是根據(jù)鎖和密鑰（K1）求出的，只有（K2）可用于開（K1）加的鎖一個密鑰（K1）用于封箱，一個密鑰（K2）用于開鎖這里引入T為可信任的第三方， T經(jīng)過認證，是高度可靠和高效的機構(gòu) B擁有密鑰對K1和K2，K1用于封箱，K2用于開鎖，B可以將鎖與鑰匙K1 發(fā)給任何人（如A），使其可以安全的向B發(fā)消息。B請求發(fā)送方（如A）用鎖與鑰匙K1 封住內(nèi)容，然后B 可以用密鑰K2開鎖這里密鑰K1是公開的，稱為公鑰（Public key）,另一個密鑰K是私

9、有的的，稱為私鑰（Private key）計算機網(wǎng)絡(luò)安全概論16非對稱密鑰A、B(A-B) A、B、C (A-B 、 A-C 、 B-C ) A、B、C 、D (A-B 、 A-C 、 A-D 、 B-C 、 B-D 、 C-D ) n nN=1000 1000 1000個鎖，1000個公鑰，1000個私鑰計算機網(wǎng)絡(luò)安全概論17公鑰算法應(yīng)用：保密計算機網(wǎng)絡(luò)安全概論18公鑰算法應(yīng)用：認證計算機網(wǎng)絡(luò)安全概論19基本思想和要求涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對密鑰是計算可行的已知公鑰和明文，產(chǎn)生密文是計算可行的接收方利用私鑰來解密密文是計算可

10、行的對于攻擊者，利用公鑰來推斷私鑰是計算不可行的已知公鑰和密文，恢復(fù)明文是計算不可行的(可選)加密和解密的順序可交換計算機網(wǎng)絡(luò)安全概論20如何設(shè)計一個公鑰算法公鑰和私鑰必須相關(guān)，而且從公鑰到私鑰不可推斷必須要找到一個難題，從一個方向走是容易的，從另一個方向走是困難的如何把這個難題跟加解密結(jié)合起來數(shù)學(xué)上是用一個單向陷門函數(shù)描述,滿足下列條件的函數(shù)f:給定定義域內(nèi)的任意x，計算y=f(x)是容易的給定y,計算x使y=f(x)是困難的，即要求出x=f-1(y)在計算上是不可行的存在某個，當它已知時，對任何給定的y，若相應(yīng)的x存在，則計算x使y=f(x)是容易的單向函數(shù)陷門性公鑰私鑰計算機網(wǎng)絡(luò)安全概論

11、21公鑰密碼學(xué)的研究情況與計算復(fù)雜性理論密切相關(guān)基于大整數(shù)因式分解問題（RSA體制）以大素數(shù)為模，計算離散對數(shù)問題(Elgamal體制,橢圓曲線密碼體制)計算復(fù)雜性理論可以提供指導(dǎo)但是需求不盡相同計算復(fù)雜性通常針對一個孤立的問題進行研究而公鑰密碼學(xué)往往需要考慮一些相關(guān)的問題比如，密碼分析還需要考慮已知明文、選擇明文等相關(guān)的情形討論的情形不同計算復(fù)雜性考慮最壞的情形而對于公鑰密碼學(xué)則是不夠的一個np問題必然會導(dǎo)致一個保密性很好的密碼系統(tǒng)嗎？不一定，還需要有好的構(gòu)造計算機網(wǎng)絡(luò)安全概論22EL Gamal算法取P為質(zhì)數(shù)，隨機數(shù)gP,xP,計算y=gx mod P,(y,g,p)為公開密鑰，x為隱蔽密

12、鑰。選取隨機數(shù)k,使K與p-1互質(zhì)；計算a=gk mod p ; b=ykM mod p a和b構(gòu)成密文，它比明文M長一倍；解密時計算M=b/ax mod p三大數(shù)學(xué)難題大整數(shù)因數(shù)分解問題兩個素數(shù)pq，計算積容易n=pXq給定n,求兩個素因子pq,使n=pXq難這是RSA算法未被破譯的前提假設(shè)條件三大數(shù)學(xué)難題離散對數(shù)問題已知有限循環(huán)群G=gk|k=0,1,2,及其生成元g和階n=|G|.給定整數(shù)a ,計算ga=h容易；給定元素h,計算整數(shù)x,0=x=n,使得gx=h非常困難DH、RSA算法的假設(shè)前提三大數(shù)學(xué)難題橢圓曲線離散對數(shù)問題已知有限域Fp上的橢圓曲線點群E(Fp)=(x,y) 屬于Fp

13、X Fpy2=x3+ax+b,a,b屬于Fp UO點P=（x,y）的階為一個大素數(shù)則：給定a,計算點aP很容易給定Q,計算整數(shù)x,使xP=Q非常困難。這是橢圓加密算法的前提假設(shè)計算機網(wǎng)絡(luò)安全概論26RSA算法1977年由Ron Rivest、Adi Shamir和Len Adleman發(fā)明，1978年公布是一種塊加密算法。應(yīng)用最廣泛的公鑰密碼算法只在美國申請專利，且已于2000年9月到期計算機網(wǎng)絡(luò)安全概論27RSA簡介素數(shù)只能被和本身整除的數(shù)（、）RSA算法思想：兩個大素數(shù)很容易相乘而對得到的積求因子則很難RSA中的私鑰和公鑰基于大素數(shù)（100位以上）難度在于RSA選擇和生成私鑰和公鑰計算機網(wǎng)

14、絡(luò)安全概論28RSA密鑰生成與使用產(chǎn)生密鑰對選擇兩個大素數(shù)p,q, pq計算n=pq,(n)=(p-1)(q-1)選擇整數(shù)e（公鑰，即加密密鑰）,使gcd(e,(n)=1選擇整數(shù)d（私鑰，即解密密鑰）,使d*e mod (n) =1 公鑰: KU=e,n, 私鑰: KR=d,n使用加密: C = Me mod n解密: M = Cd mod n明文密文計算機網(wǎng)絡(luò)安全概論29計算乘冪（反復(fù)平方乘）計算d=am, m=bkbk-1b0(二進制表示)d1for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod nreturn d原理：M = (b

15、k2+bk-1)2+bk-2)2+bk-3)2+)2+b0計算機網(wǎng)絡(luò)安全概論30RSA密鑰生成與使用（例子）產(chǎn)生密鑰對選擇兩個大素數(shù)p=7,q=17, pq計算n=pq=7*17=119,(n)=(p-1)(q-1)=6*16=96,96的因子有2,2,2,2,2和，因此e不能有2和3的因子選擇整數(shù)e=5（公鑰，即加密密鑰）,使gcd(e,(n)=1選擇整數(shù)d=77（私鑰，即解密密鑰）,使d*e mod (n) =1 (5*77) mod 96 = 385 mod 96 =1公鑰: KU=e,n=5,119, 私鑰: KR=d,n=77,119使用加密: C = Me mod n解密: M =

16、 Cd mod n計算機網(wǎng)絡(luò)安全概論31RSA密鑰生成與使用（例子）用A=1、B=2等編碼原字符求出明文e的冪（這里是5）將結(jié)果除以119，得到余數(shù)，即為密文求出密文d的冪（這里是77）將結(jié)果除以119，得到余數(shù)，即為明文用A=1、B=2等譯碼原字符使用公鑰的加密算法使用私鑰的解密算法FF=66565 Mod 119=4141774177 Mod 119=66=F41F計算機網(wǎng)絡(luò)安全概論32RSA算法要求塊大小為k, 2k n 2k+1明文信息M n 加密: C = Me mod n解密: M = Cd mod n = Med mod n公鑰: KU=e,n, 私鑰: KR=d,n上述算法需要

17、滿足以下條件:能夠找到e,d,n,使得Med mod n = M, 對所有Mn計算Me和Cd相對容易從e和n得到d是在計算上不可行的公開計算機網(wǎng)絡(luò)安全概論33RSA密鑰生成原理令n=pq, pq都是素數(shù),(n)=(p-1)(q-1)是n的Euler函數(shù)Euler定理推論: 若n=pq, pq都是素數(shù), k是任意整數(shù),則 mk(p-1)(q-1)+1 m mod n, 對任意0mnmk(n)+1 m mod n, 對任意0mn只要選擇e,d, 滿足ed=k(n)+1,即 ed mod (n) 1 ed 1 mod (n) d e-1 mod (n)公鑰: KU=e,n, 私鑰: KR=d,n即選

18、擇e或d,使e與(n) 互質(zhì)計算機網(wǎng)絡(luò)安全概論34RSA的實現(xiàn)素數(shù)的產(chǎn)生取大數(shù)n（100位以上的整數(shù)）和整數(shù)an, 計算an-1modn 若結(jié)果不為1，則n必不為質(zhì)數(shù) 否則n不為質(zhì)數(shù)的概率大約10-13大整數(shù)模運算許多實際應(yīng)用的RSA系統(tǒng)中，模數(shù)至少取512位，更多的建議使用1024位計算機網(wǎng)絡(luò)安全概論35RSA密鑰產(chǎn)生產(chǎn)生兩個素數(shù)由于n = pq是公開的，所以，為了防止攻擊者利用n獲得p和q，必須選擇足夠大的素數(shù)p和q大素數(shù)產(chǎn)生算法選擇e或者d，然后求出另一個計算機網(wǎng)絡(luò)安全概論36大素數(shù)產(chǎn)生素數(shù)生成過程: 隨機選擇一個奇數(shù)n 隨機選擇a, 使an 進行素性測試(例如用Miller-Rabin

19、算法),若n沒有通過測試,拋棄n,轉(zhuǎn)到 如果通過了足夠次數(shù)的測試,認為n是素數(shù),否則轉(zhuǎn)到.素數(shù)理論: 在N附近，每ln(N)個整數(shù)中有一個素數(shù)計算機網(wǎng)絡(luò)安全概論37RSA安全性基于數(shù)學(xué)的攻擊（30年研究）公鑰: KU=e,n, 私鑰: KR=d,n, n=pq分解n=pq (n)=(p-1)(q-1) d=e-1 mod (n)不求出p,q,直接求(n) d=e-1 mod (n)不求出(n),直接計算d500位10進制數(shù)需要1025年結(jié)論已知的方法至少跟因子分解一樣難度尚未發(fā)現(xiàn)多項式時間的因子分解算法因子分解的算法已經(jīng)取得了長足進步措施: 選擇足夠大的n(1024位以上),并且使得e,d之間

20、相差不太大,也不太小計算機網(wǎng)絡(luò)安全概論38橢圓曲線密碼體制 1985年，N.Koblitz及V.S.Miller分別提出了橢圓曲線密碼體制（ECC），只是為公鑰密碼需要的復(fù)雜數(shù)學(xué)運算提供了另一種方案。與其他公鑰密碼體制相比，橢圓曲線密碼體制的優(yōu)點主要表現(xiàn)在以下4個方面：(1) 密鑰尺度較?。?2) 參數(shù)選擇比較靈活；(3) 具有由數(shù)學(xué)難題保證的安全性；(4) 實現(xiàn)速度較快。計算機網(wǎng)絡(luò)安全概論39橢園曲線密碼橢園曲線E是具有如下形式的函數(shù)圖：E：y2 = x3 + ax +b, 其中還包括一個無窮遠點O。橢園曲線（E）上兩點的和運算，就是連接兩點做直線，并與橢園曲線相交于另外一點，該交點關(guān)于x軸

21、的對稱點就是和。則是一阿貝爾群。POOPPP1=（x1,y1), P2=(x2,y2) if P1 P2 x3= m2 - x1 - x2, y3= m(x1-x3)-y1, m=(y2-y1)/（x2-x1)If P1 = P2x3= m2 - x1 - x2, y3= m(x1-x3)-y1 mod p， m =(3 x12 + a)/(2y1) mod p計算機網(wǎng)絡(luò)安全概論40橢園曲線密碼信息m與點 的對應(yīng)關(guān)系假設(shè)有一正整數(shù)k滿足pMk.使得對任意的消息m, 0mM-1,1jk,滿足 使其有解，取其中的一個解為m對應(yīng)E上的點。反過來對于點Pm=(xm,ym),令 m=(xm-j)/k,

22、則得到點Pm與m的對應(yīng)關(guān)系。 顯然k是存在的，具體取值，要視所選取的曲線而定。橢園曲線密碼算法準備工作 選擇有限域Fq、橢圓曲線E、G（x,y),把明文編碼到曲線上的點（xm,ym).選擇私鑰n,計算公鑰P=nG對于A：私鑰為na,公鑰為Pa=naG; 對于B：私鑰為nb,公鑰為Pb=nbG; 加密：對于任何想發(fā)送消息給A的人 選擇一個隨機整數(shù)k,生成密文 Cm=k(x,y),(xm,ym)+kPa解密：A用私鑰恢復(fù)明文 計算na(k(x,y)），再計算 （xm,ym)+kPa-na(k(x,y)=（xm,ym)DH交換算法例：y2= x3 +11 x + 19 (mod 167) 及 點（2

23、，7）Alice選擇A=15， B選擇 B=22，則Alice計算 A（2，7）=15（2，7）=（102，88）發(fā)給bobBob計算B（2，7）=22（2，7）=（9，43）發(fā)給AliceAlice 對 Bob發(fā)來的結(jié)果使用她的密碼A進行X運算A（9，43）= 15（9，43）=（131，140）Bob 對Alice發(fā)來的結(jié)果使用他的密碼B進行X運算B（102，88）=22（102，88）=（131，140）計算機網(wǎng)絡(luò)安全概論42計算機網(wǎng)絡(luò)安全概論43橢圓密碼體制（ECC）的實現(xiàn) Certicom公司對ECC和RSA進行對比后發(fā)現(xiàn)，在實現(xiàn)相同安全性的情況下，ECC所需要的密鑰量要比RSA少的

24、多ECC的密鑰長度RSA的密鑰長度Mips年1601024101232051201036600210001078120012000010168計算機網(wǎng)絡(luò)安全概論44橢圓密碼體制（ECC）的實現(xiàn) ECC特別適用于以下情況：(1) 無線Modem的實現(xiàn)。為分組交換數(shù)據(jù)網(wǎng)提供加密。在移動通信器件上運行4MHz的68330CPU，則可實現(xiàn)快速的Diffie-Hellman 密鑰交換，并極小化密鑰交換所占用的寬帶，并將計算時間從60秒降到2秒以內(nèi)。(2) Web服務(wù)器實現(xiàn)在web 服務(wù)器上集中進行密碼計算就會形成瓶頸，Web服務(wù)器上的寬帶有限使寬帶費用增高，而采用ECC后就可節(jié)省時間和寬帶，且通過算法的

25、協(xié)商也比較容易處理兼容性方面的問題。(3) 集成電路卡的實現(xiàn)ECC無需協(xié)處理器就可以在標準卡上實現(xiàn)快速、安全的數(shù)字簽名，而RSA體制難以做到。而且ECC可使程序代碼、密鑰、證書的存儲空間極小化，數(shù)據(jù)幀最短，便于實現(xiàn)，從而大大降低了IC卡的成本。對稱與非對稱密鑰加密比較 特征對稱密鑰加密非對稱密鑰加密加密/解密使用的密鑰相同不相同加密/解密的速度快慢得到的密文長度等于或小于明文長度大于明文長度密鑰協(xié)定與密鑰交換大問題沒問題所需密鑰數(shù)量和消息交換參與者個數(shù)的關(guān)系大約為參與者個數(shù)的平方,伸縮性不好等于參與者個數(shù),伸縮性好用法主要用于加密/解密(保密性),不能用于數(shù)字簽名(完整性和不可抵賴檢查)可以用于加密/解密(保密性)和數(shù)字簽名(完整性和不可抵賴檢查)網(wǎng)絡(luò)與信息安全45完整的數(shù)據(jù)加密及身份認證流程加密對稱密鑰用戶A 明文 密文用戶B的公鑰數(shù)字信封解密用戶B 明文hash摘要簽名簽名A證書B證書用戶A的私鑰用戶B的私鑰對稱密鑰 密文解密 明文簽名A證書簽名用戶A的公鑰摘要密鑰托管系統(tǒng)從保護國家安全、防止犯罪需要，希望國家權(quán)威機構(gòu)能夠?qū)用艿臄?shù)據(jù)進行破譯。密鑰托管系統(tǒng)（Key Escrow S