加密技術(shù)(2)研公鑰密碼體系(自學)

1、2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論1附2 數(shù)據(jù)加密技術(shù)2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論2信源編碼器信道解碼器接收者秘密信道密 碼 分 析者密鑰源密鑰源2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論3u傳遞信息是否安全？傳遞信息是否安全？uA P B2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論4u使用鑰匙是否可保證安全？使用鑰匙是否可保證安全？uA Bu密鑰發(fā)布（密鑰發(fā)布（Distribution）或交換（）或交換（exchange）2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論5u76年Diffie和Hellman發(fā)表了“密碼學的新方向”，奠定了公鑰密碼學的基礎(chǔ)uDiffie

2、-Hellman密鑰交換協(xié)議算法u使用此方法確定對稱密鑰交換Ralph Merkle,and independently Marty 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.”2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論6u78

3、年，RSA算法u公鑰技術(shù)是二十世紀最偉大的思想之一 v改變了密鑰分發(fā)的方式v可以廣泛用于數(shù)字簽名和身份認證服務RSA(Ron Rivest,Adi Shamir,Len Adleman,1977)2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論7uAlice與ob確定兩個大素數(shù)n和g，這兩個整數(shù)不保密， Alice與ob 可以使用不安全信道確定這兩個數(shù)uAlice選擇另一個大隨機數(shù)x，并計算A如下： A=gx mod nuAlice將發(fā)給obuob選擇另一個大隨機數(shù)y，并計算B如下： B=gy mod nuob將發(fā)給Aliceu計算秘密密鑰K1如下： K1=Bx mod nu計算秘密密鑰K2如下：

4、 K2=Ay mod n2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論8uAlice與ob確定兩個大素數(shù)n和g，這兩個整數(shù)不保密， Alice與ob 可以使用不安全信道確定這兩個數(shù)設(shè)設(shè) n=11,g=7n=11,g=7uAlice選擇另一個大隨機數(shù)x，并計算A如下： A=gx mod n設(shè)設(shè) x=3,x=3,則則 A = 7A = 73 3 mod 11 = 343 mod 11 = 2mod 11 = 343 mod 11 = 2uAlice將發(fā)給ob AliceAlice將發(fā)給將發(fā)給obobuob選擇另一個大隨機數(shù)y，并計算B如下： B=gy mod n設(shè)設(shè) y=6,y=6,則則 B = 7

5、B = 76 6 mod 11 = 117649 mod 11 = 4mod 11 = 117649 mod 11 = 4uob將發(fā)給Aliceobob將將4 4發(fā)給發(fā)給AliceAlice2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論9u計算秘密密鑰K1如下： K1=Bx mod n有有 K1 = 4 K1 = 43 3 mod 11 = 64 mod 11 = 9mod 11 = 64 mod 11 = 9u計算秘密密鑰K2如下： K2=Ay mod n 有有 K2 = 2 K2 = 26 6 mod 11 = 64 mod 11 = 9 mod 11 = 64 mod 11 = 92006

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

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

8、=gx mod n =73 mod 11 =2TomA=gx mod n =78 mod 11 =9BobB=gy mod n =79 mod 11 =83B=gy mod n =76 mod 11 =42006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論13A=2A=2截獲A=A=B=8B=8A=4A=442006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論14AliceA=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

9、=Ay mod n =26 mod 11 =92006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論15uA、B不必同時訪問T以獲得密鑰對uB訪問T取得一個鎖和密鑰（K1）,將鎖和密鑰（K1）發(fā)給AuB告訴A可以使用這個鎖和密鑰（K1）封箱uB擁有不同組相關(guān)的密鑰（K2）， B從T取得（K2） ，是根據(jù)鎖和密鑰（K1）求出的，只有（K2）可用于開（K1）加的鎖u一個密鑰（K1）用于封箱，一個密鑰（K2）用于開鎖u這里引入T為可信任的第三方， T經(jīng)過認證，是高度可靠和高效的機構(gòu) B擁有密鑰對K1和K2，K1用于封箱，K2用于開鎖，B可以將鎖與鑰匙K1 發(fā)給任何人（如A），使其可以安全的向B發(fā)消息。B請求發(fā)

10、送方（如A）用鎖與鑰匙K1 封住內(nèi)容，然后B 可以用密鑰K2開鎖這里密鑰K1是公開的，稱為公鑰（Public key）,另一個密鑰K是私有的的，稱為私鑰（Private key）2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論16u A、B(A-B) u A、B、C (A-B 、 A-C 、 B-C ) u A、B、C 、D (A-B 、 A-C 、 A-D 、 B-C 、 B-D 、 C-D ) u n nu N=1000 1000 u 1000個鎖，1000個公鑰，1000個私鑰2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論172006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論182006計算機網(wǎng)絡安

11、全概論計算機網(wǎng)絡安全概論19u涉及到各方：發(fā)送方、接收方、攻擊者u涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文u公鑰算法的條件：v產(chǎn)生一對密鑰是計算可行的v已知公鑰和明文，產(chǎn)生密文是計算可行的v接收方利用私鑰來解密密文是計算可行的v對于攻擊者，利用公鑰來推斷私鑰是計算不可行的v已知公鑰和密文，恢復明文是計算不可行的v(可選)加密和解密的順序可交換2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論20u公鑰和私鑰必須相關(guān)，而且從公鑰到私鑰不可推斷v必須要找到一個難題，從一個方向走是容易的，從另一個方向走是困難的v如何把這個難題跟加解密結(jié)合起來u數(shù)學上是用一個單向陷門函數(shù)描述,滿足下列條件的函數(shù)f:v給定定義域內(nèi)

12、的任意x，計算y=f(x)是容易的v給定y,計算x使y=f(x)是困難的，即要求出x=f-1(y)在計算上是不可行的v存在某個，當它已知時，對任何給定的y，若相應的x存在，則計算x使y=f(x)是容易的單向函數(shù)陷門性公鑰私鑰2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論21u與計算復雜性計算復雜性理論密切相關(guān)v基于大整數(shù)因式分解問題（RSA體制）v以大素數(shù)為模，計算離散對數(shù)問題(Elgamal體制,橢圓曲線密碼體制)u計算復雜性理論可以提供指導v但是需求不盡相同計算復雜性通常針對一個孤立的問題進行研究而公鑰密碼學往往需要考慮一些相關(guān)的問題比如，密碼分析還需要考慮已知明文、選擇明文等相關(guān)的情形v討

13、論的情形不同計算復雜性考慮最壞的情形而對于公鑰密碼學則是不夠的u一個np問題必然會導致一個保密性很好的密碼系統(tǒng)嗎？v不一定，還需要有好的構(gòu)造2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論22uEL Gamal算法v取P為質(zhì)數(shù)，隨機數(shù)gP,xP,計算y=gx mod P,(y,g,p)為公開密鑰，x為隱蔽密鑰。v選取隨機數(shù)k,使K與p-1互質(zhì)；v計算a=gk mod p ; b=ykM mod pv a和b構(gòu)成密文，它比明文M長一倍；v解密時計算M=b/ax mod p2006u大整數(shù)因數(shù)分解問題v兩個素數(shù)pq，計算積容易n=pXqv給定n,求兩個素因子pq,使n=pXq難v這是RSA算法未被破譯

14、的前提假設(shè)條件2006u離散對數(shù)問題v已知有限循環(huán)群G=gk|k=0,1,2,及其生成元g和階n=|G|.v給定整數(shù)a ,計算ga=h容易；v給定元素h,計算整數(shù)x,0=x=n,使得gx=h非常困難vDH、RSA算法的假設(shè)前提2006u橢圓曲線離散對數(shù)問題v已知有限域Fp上的橢圓曲線點群E(Fp)=(x,y) 屬于Fp X Fpy2=x3+ax+b,a,b屬于Fp UO點P=（x,y）的階為一個大素數(shù)則：給定a,計算點aP很容易給定Q,計算整數(shù)x,使xP=Q非常困難。這是橢圓加密算法的前提假設(shè)2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論26u1977年由Ron Rivest、Adi Shami

15、r和Len Adleman發(fā)明，1978年公布u是一種塊加密算法。u應用最廣泛的公鑰密碼算法u只在美國申請專利，且已于2000年9月到期2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論27u素數(shù)只能被和本身整除的數(shù)（、）uRSA算法思想：v兩個大素數(shù)很容易相乘v而對得到的積求因子則很難vRSA中的私鑰和公鑰基于大素數(shù)（100位以上）v難度在于RSA選擇和生成私鑰和公鑰2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論28u產(chǎn)生密鑰對v選擇兩個大素數(shù)p,q, pqv計算n=pq,(n)=(p-1)(q-1)v選擇整數(shù)e（公鑰，即加密密鑰）,使gcd(e,(n)=1v選擇整數(shù)d（私鑰，即解密密鑰）,使d*e

16、 mod (n) =1 u公鑰: KU=e,n, 私鑰: KR=d,nu使用v加密: C = Me mod nv解密: M = Cd mod n明文明文密文密文2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論29u計算d=am, m=bkbk-1b0(二進制表示)d1for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod nreturn du原理：M = (bk2+bk-1)2+bk-2)2+bk-3)2+)2+b02006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論30u產(chǎn)生密鑰對v選擇兩個大素數(shù)p=7,q=17, pqv計算n=pq=7*17=1

17、19,(n)=(p-1)(q-1)=6*16=96,96的因子有2,2,2,2,2和，因此e不能有2和3的因子v選擇整數(shù)e=5（公鑰，即加密密鑰）,使gcd(e,(n)=1v選擇整數(shù)d=77（私鑰，即解密密鑰）,使d*e mod (n) =1 (5*77) mod 96 = 385 mod 96 =1u公鑰: KU=e,n=5,119, 私鑰: KR=d,n=77,119u使用v加密: C = Me mod nv解密: M = Cd mod n2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論31用用A=1、B=2等編碼原字符等編碼原字符求出明文求出明文e的冪（這里是的冪（這里是5）將結(jié)果除以將結(jié)果

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

19、u上述算法需要滿足以下條件:v能夠找到e,d,n,使得Med mod n = M, 對所有Mnv計算Me和Cd相對容易v從e和n得到d是在計算上不可行的公開公開2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論33u令n=pq, pq都是素數(shù),(n)=(p-1)(q-1)是n的Euler函數(shù)uEuler定理推論: 若n=pq, pq都是素數(shù), k是任意整數(shù),則 mk(p-1)(q-1)+1 m mod n, 對任意0mnmk(n)+1 m mod n, 對任意0mnu只要選擇e,d, 滿足ed=k(n)+1,即 ed mod (n) 1 ed 1 mod (n) d e-1 mod (n)u公鑰:

20、KU=e,n, 私鑰: KR=d,n即選擇e或d,使e與(n) 互質(zhì)2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論34u素數(shù)的產(chǎn)生取大數(shù)n（100位以上的整數(shù)）和整數(shù)an, 計算an-1modn 若結(jié)果不為1，則n必不為質(zhì)數(shù) 否則n不為質(zhì)數(shù)的概率大約10-13u大整數(shù)模運算v許多實際應用的RSA系統(tǒng)中，模數(shù)至少取512位，更多的建議使用1024位2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論35u產(chǎn)生兩個素數(shù)v由于n = pq是公開的，所以，為了防止攻擊者利用n獲得p和q，必須選擇足夠大的素數(shù)p和qv大素數(shù)產(chǎn)生算法u選擇e或者d，然后求出另一個2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論36u素數(shù)

21、生成過程: 隨機選擇一個奇數(shù)n 隨機選擇a, 使an 進行素性測試(例如用Miller-Rabin算法),若n沒有通過測試,拋棄n,轉(zhuǎn)到 如果通過了足夠次數(shù)的測試,認為n是素數(shù),否則轉(zhuǎn)到.u素數(shù)理論: 在N附近，每ln(N)個整數(shù)中有一個素數(shù)2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論37u基于數(shù)學的攻擊（30年研究）公鑰: KU=e,n, 私鑰: KR=d,n, n=pqv分解n=pq (n)=(p-1)(q-1) d=e-1 mod (n)v不求出p,q,直接求(n) d=e-1 mod (n)v不求出(n),直接計算dv500位10進制數(shù)需要1025年u結(jié)論v已知的方法至少跟因子分解一樣

22、難度v尚未發(fā)現(xiàn)多項式時間的因子分解算法v因子分解的算法已經(jīng)取得了長足進步u措施: 選擇足夠大的n(1024位以上),并且使得e,d之間相差不太大,也不太小2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論38 19851985年，年，N.KoblitzN.Koblitz及及V.S.MillerV.S.Miller分別提分別提出了橢圓曲線密碼體制（出了橢圓曲線密碼體制（ECCECC），只是為公鑰），只是為公鑰密碼需要的復雜數(shù)學運算提供了另一種方案。密碼需要的復雜數(shù)學運算提供了另一種方案。與其他公鑰密碼體制相比，橢圓曲線密碼體制與其他公鑰密碼體制相比，橢圓曲線密碼體制的優(yōu)點主要表現(xiàn)在以下的優(yōu)點主要表現(xiàn)在

23、以下4 4個方面：個方面：(1) (1) 密鑰尺度較??；密鑰尺度較??；(2) (2) 參數(shù)選擇比較靈活；參數(shù)選擇比較靈活；(3) (3) 具有由數(shù)學難題保證的安全性；具有由數(shù)學難題保證的安全性；(4) (4) 實現(xiàn)速度較快。實現(xiàn)速度較快。2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論39u橢園曲線曲線E是具有如下形式的函數(shù)圖：是具有如下形式的函數(shù)圖：vE：y2 = x3 + ax +b, 其中還包括一個無窮遠點其中還包括一個無窮遠點O。u橢園曲線（曲線（E）上兩點的和運算，就是連接兩點）上兩點的和運算，就是連接兩點做直線，并與做直線，并與橢園曲線相交于另外一點，該交點曲線相交于另外一點，該交點關(guān)

24、于關(guān)于x軸的對稱點就是和。則軸的對稱點就是和。則是一阿貝爾是一阿貝爾群。群。v POOPPv P1=（x1,y1), P2=(x2,y2)v if P1 P2 x3= m2 - x1 - x2, y3= m(x1-x3)-y1, m=(y2-y1)/（x2-x1)v If P1 = P2x3= m2 - x1 - x2, y3= m(x1-x3)-y1 mod p， m =(3 x12 + a)/(2y1) mod p2006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論40u信息m與點 的對應關(guān)系u假設(shè)有一正整數(shù)k滿足pMk.使得對任意的消息m, 0mM-1,1jk,滿足 使其有解，取其中的一個解為m

25、對應E上的點。反過來對于點Pm=(xm,ym),令 m=(xm-j)/k, 則得到點Pm與m的對應關(guān)系。 顯然k是存在的，具體取值，要視所選取的曲線而定。P(,)mmmxy23()()(mod)ymkja mkjbp,P(,)mmmmyxy則2006u算法v準備工作 選擇有限域Fq、橢圓曲線E、G（x,y),把明文編碼到曲線上的點（xm,ym).選擇私鑰n,計算公鑰P=nG對于A：私鑰為na,公鑰為Pa=naG; 對于B：私鑰為nb,公鑰為Pb=nbG; v加密：對于任何想發(fā)送消息給A的人 選擇一個隨機整數(shù)k,生成密文 Cm=k(x,y),(xm,ym)+kPav解密：A用私鑰恢復明文 計算n

26、a(k(x,y)），再計算 （xm,ym)+kPa-na(k(x,y)=（xm,ym)2006例：y2= x3 +11 x + 19 (mod 167) 及 點（2，7）uAlice選擇A=15， B選擇 B=22，則vAlice計算 A（2，7）=15（2，7）=（102，88）發(fā)給bobvBob計算B（2，7）=22（2，7）=（9，43）發(fā)給AlicevAlice 對 Bob發(fā)來的結(jié)果使用她的密碼A進行X運算A（9，43）= 15（9，43）=（131，140）vBob 對Alice發(fā)來的結(jié)果使用他的密碼B進行X運算B（102，88）=22（102，88）=（131，140）計算機網(wǎng)絡安

27、全概論計算機網(wǎng)絡安全概論422006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論43 CerticomCerticom公司對公司對ECCECC和和RSARSA進行對比后發(fā)現(xiàn)，進行對比后發(fā)現(xiàn)，在實現(xiàn)相同安全性的情況下，在實現(xiàn)相同安全性的情況下，ECCECC所需要的密所需要的密鑰量要比鑰量要比RSARSA少的多少的多ECC的密鑰長度RSA的密鑰長度Mips年16010241012320512010366002100010781200120000101682006計算機網(wǎng)絡安全概論計算機網(wǎng)絡安全概論44ECCECC特別適用于以下情況：特別適用于以下情況：(1) (1) 無線無線ModemModem的實現(xiàn)。為

28、分組交換數(shù)據(jù)網(wǎng)提供加密。在移動通信器的實現(xiàn)。為分組交換數(shù)據(jù)網(wǎng)提供加密。在移動通信器件上運行件上運行4MHz4MHz的的68330CPU68330CPU，則可實現(xiàn)快速的，則可實現(xiàn)快速的Diffie-Hellman Diffie-Hellman 密鑰交密鑰交換，并極小化密鑰交換所占用的寬帶，并將計算時間從換，并極小化密鑰交換所占用的寬帶，并將計算時間從6060秒降到秒降到2 2秒秒以內(nèi)。以內(nèi)。(2) Web(2) Web服務器實現(xiàn)服務器實現(xiàn)在在web web 服務器上集中進行密碼計算就會形成瓶頸，服務器上集中進行密碼計算就會形成瓶頸，WebWeb服務器上的寬服務器上的寬帶有限使寬帶費用增高，而采用

29、帶有限使寬帶費用增高，而采用ECCECC后就可節(jié)省時間和寬帶，且通過后就可節(jié)省時間和寬帶，且通過算法的協(xié)商也比較容易處理兼容性方面的問題。算法的協(xié)商也比較容易處理兼容性方面的問題。(3) (3) 集成電路卡的實現(xiàn)集成電路卡的實現(xiàn)ECCECC無需協(xié)處理器就可以在標準卡上實現(xiàn)快速、安全的數(shù)字簽名，而無需協(xié)處理器就可以在標準卡上實現(xiàn)快速、安全的數(shù)字簽名，而RSARSA體制難以做到。而且體制難以做到。而且ECCECC可使程序代碼、密鑰、證書的存儲空間極可使程序代碼、密鑰、證書的存儲空間極小化，數(shù)據(jù)幀最短，便于實現(xiàn)，從而大大降低了小化，數(shù)據(jù)幀最短，便于實現(xiàn)，從而大大降低了ICIC卡的成本?？ǖ某杀?。20

30、06特征對稱密鑰加密非對稱密鑰加密加密/解密使用的密鑰相同不相同加密/解密的速度快慢得到的密文長度等于或小于明文長度大于明文長度密鑰協(xié)定與密鑰交換大問題沒問題所需密鑰數(shù)量和消息交換參與者個數(shù)的關(guān)系大約為參與者個數(shù)的平方,伸縮性不好等于參與者個數(shù),伸縮性好用法主要用于加密/解密(保密性),不能用于數(shù)字簽名(完整性和不可抵賴檢查)可以用于加密/解密(保密性)和數(shù)字簽名(完整性和不可抵賴檢查)網(wǎng)絡與信息安全網(wǎng)絡與信息安全452006加密對稱密鑰用戶A 明文明文 密文密文用戶B的公鑰數(shù)字信封解密用戶B 明文明文hash摘要摘要簽名簽名簽名簽名A證書證書B證書證書用戶A的私鑰用戶B的私鑰對稱密鑰 密文密文解密 明文明文簽名簽名A證書證書簽