信息安全系統(tǒng)工程公鑰密碼體制

1、一、概述,1、公鑰密碼體制概況2、公鑰密碼體制的發(fā)展動因3、公鑰密碼體制的特點和要求4、公鑰密碼體制的使用5、對公鑰密碼體制的攻擊類型,1、公鑰密碼體制概況,公鑰密碼體制的出現(xiàn)也許是人類3000年的密碼技術發(fā)展史上最重要的進步公鑰體制使用兩個密鑰—私鑰(private key)和公鑰(public key)在公鑰體制下，加解密雙方是非對稱的在單鑰體制下，加解密雙方是對稱的。公鑰體制主要是基于數(shù)學函數(shù)和數(shù)論問題，而不是單鑰

2、算法采用的置換和替代,公鑰體制與單鑰體制,公鑰體制與單鑰體制互相補充，但都不能替代對方公鑰體制并不比單鑰體制安全（安全性與密鑰長度有關）；公鑰體制不能替代單鑰體制（公鑰體制的計算速度比單鑰體制慢很多）；使用公鑰體制進行密鑰分配，仍然需要相當復雜的協(xié)議。,2、公鑰密碼體制的發(fā)展動因,公鑰密碼體制的出現(xiàn)主要是為了解決常規(guī)加密所面臨的兩個突出問題1、密鑰分配：在沒有一個安全的、可值得信賴的KDC（Key Distribution Ce

3、nter）的情況下，如何進行安全的密鑰分配；2、數(shù)字簽名：如何驗證一個報文是由其聲稱的發(fā)送者發(fā)送的，并且是完整的。Whitfield Diffie & Martin Hellman在1976年首次公開地提出了公開密鑰密碼編碼學的概念，這種新方法的出現(xiàn)，可以很好地解決上述兩個難題,3、公鑰密碼體制特點,公鑰密碼體制使用兩個密鑰公鑰：可以公開發(fā)布，任何人都可以利用公鑰來加密信息或驗證簽名；私鑰：僅僅為信息的接受者所掌握，可以

4、在本地自主產(chǎn)生（不需要分配），利用私鑰來解密信息或創(chuàng)建簽名；注意：公鑰和私鑰是成對產(chǎn)生的，并且具有內(nèi)在的數(shù)學關系，當私鑰改變了，則其對應的公鑰必須重新發(fā)布。公鑰體制是非對稱的（非對稱密碼體制）發(fā)送者可以利用公鑰來加密信息，但是他不能解密信息；同樣，人們可以利用公鑰來驗證信息的簽名，但除了簽名者本人，其他人都不能以他的身份創(chuàng)建簽名。,對公鑰加密體制的要求,公鑰密碼體制必須滿足如下要求1、參與方容易通過計算產(chǎn)生出一對密鑰（公鑰/私

5、鑰）；2、在知道公鑰和明文的情況下，容易計算得到相應的密文；3、在知道私鑰的情況下，容易將密文恢復為相應的明文；4、想通過公鑰計算出私鑰，在計算上是不可行的；5、想通過公鑰和密文，恢復出相應的明文，在計算上是不可行的；6、加解密順序可變（不是所有算法都滿足）。公鑰密碼體制本質(zhì)上是一個“陷門單向函數(shù)”,4、公鑰密碼加解密過程,假設明文分組 X=[ X1, X2, …, Xm ]，密文組 Y=[ Y1, Y2, …, Ym ]

6、，接收者 B 的公鑰/私鑰對為 [KUb, KRb]，則：加密過程：Yi = EKUb( Xi ) //用接收方公鑰解密過程：Xi = DKRb( Yi ) //用自己的私鑰,公鑰密碼的簽名和驗證,假設明文分組X=[ X1, X2, …, Xm ]， “密文”分組Y=[ Y1, Y2, …, Ym ]，發(fā)送者 A 的公鑰/私鑰對為 [KUa, KRa]，則：簽名過程：Yi = EKRa( Xi ) //用自己

7、的私鑰驗證過程：Xi = DKUa( Yi ) //用發(fā)送方公鑰,同時提供簽名和加密,發(fā)送方A：Z = EKUb [EKRa( X )]接收方B：X = DKUa [DKRb( Z )],公鑰體制的主要應用類型,公鑰密碼體制的主要應用類型加密/解密：提供機密性數(shù)字簽名：提供鑒別和不可否認密鑰交換：提供安全地交換會話密鑰并非所有的公鑰體制都能同時適合這三類應用,,5、對公鑰體制的攻擊,強行攻擊和常規(guī)加密一樣, 公鑰體制也

8、可能受到強行攻擊；對抗方法：采用長密鑰；在實踐中，為了使強行攻擊不可行，通常采用較大的密鑰，這使得公鑰算法的速度很慢。分析攻擊例如找到某種根據(jù)公開密鑰計算私有密鑰的方法。到目前為止，對于任何給定的公鑰算法（包括RSA）, 都沒有從數(shù)學上證明這種攻擊是不可能的；可能報文攻擊利用公鑰體制的公鑰是公開的；例如采用RSA加密一個56bit的DES密鑰（報文），則無論RSA采用的密鑰有多大，攻擊者只需窮舉該56bit的密鑰報文即可

9、。定時攻擊（邊信道攻擊）,二、幾個引理,1、費馬定理2、歐拉函數(shù)3、歐拉定理,1、費馬定理,設 p 是素數(shù)，并且 gcd(a, p)=1，則ap-1 mod p = 1 該定理也叫費馬小定理常用于公鑰密碼和素性檢測例：如果a=7, p=19，計算718 mod 19=?72 = 49 = 11 mod 1974 = 121 = 7 mod 1978 = 49 = 11 mod 19716 = 121 = 7 mod

10、 19718 = 716 * 72 = 7 * 11 = 1 mod 19,2、歐拉函數(shù)ø(n),歐拉函數(shù) ø(n)表示比 n 小，并且與 n 互素的正整數(shù)的個數(shù)計算ø(n)需要對整數(shù) n 進行素因子分解兩個特殊情況1）對于素數(shù) p，ø(p) = p-12）對于合數(shù) n = p×q （p、q均為素數(shù)）ø(n) = ø(p×q) = (p-1)

11、×(q-1) 例ø(37) = 36ø(21) = ø(3×7)=(3–1)×(7–1) = 2×6 = 12與21互素的整數(shù)為 (1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20),3、歐拉定理,如果 gcd(a,N)=1，則aø(n) mod N = 1 歐拉定理是費馬定理的一般化例設 a=3; n

12、=10; ø(10)=4，則 3ø(10) = 34 = 81 = 1 mod 10設a=2; n=11; ø(11)=10;則 2ø(11) = 210 = 1024 = 1 mod 11,三、 RSA算法,1、 RSA概況2、 RSA算法描述—密鑰產(chǎn)生3、 RSA算法描述—加解密4、 RSA的正確性5、 RSA的例子,1、RSA概況,由 MIT 的 Rivest, Sha

13、mir & Adleman在1977研制，并于1978年首次發(fā)表是目前最著名、使用最為廣泛的公鑰算法算法基于整數(shù)域中的求冪運算算法中使用了很大的整數(shù)（如1024bit，約10308）算法的安全性基于大整數(shù)分解的困難性,2、RSA的密鑰產(chǎn)生,RSA的用戶都必須通過如下方法產(chǎn)生公鑰/私鑰對1）隨機選擇兩個大素數(shù) p 和 q（1075—10150數(shù)量級）2）計算模數(shù) N = p*q，注意 ø(N) = (p-1)

14、*(q-1) 3）隨機選擇公開（加密）密鑰e，使之滿足1 < e < ø(N), 且 gcd( e, ø(N) )=14）根據(jù)以下條件計算私有（解密）密鑰de * d = 1 mod ø(N)，即 d = e-1 mod ø(N) 5）發(fā)布公開（加密）密鑰 KU={ e, N } 6）將私有（解密）密鑰 KR={ d, p, q } 保密該過程需要花費較長時間，但通常

15、很少進行,3、RSA加解密,為了加密明文消息 M，發(fā)送者必須:1）獲得接收者的公鑰 KU = {e , N} 2）計算密文 C = Me mod N, 其中 0≤M<N （注意：C = Me mod N是一個(陷門)單向函數(shù)，已知C、e、N，計算 M 是計算上不可行的 ）為了解密密文 C，接收者必須:使用自己的私有密鑰 KR={ d, p, q }，并計算M = Cd mod N ( d 是陷門，已知C、d

16、、N，計算 M 是容易的 ),4、RSA的正確性,在RSA中，各參數(shù)的選擇依據(jù)如下:N = p × qø(N) = (p-1) ×(q-1) e * d = 1 mod ø(N) ，即e×d = 1+k×ø(N)因此有如下證明當 M 不是 p , q 的倍數(shù)時( 即gcd(M, N)=1 )，有 Cd = (Me)d = M1+k*ø(N)

17、= M1×(Mø(N))k = M1 × 1k = M1 = M mod N當M是 p或 q 的倍數(shù)時, 也可證明M1+k*ø(N) = M mod N因此RSA的加密和解密是互逆的。,5、RSA的例子（不安全）,1、選擇素數(shù) p =17 ，q=112、計算模數(shù) n = p*q =17×11=1873、計算 ø(

18、n) = (p–1)(q-1) = 16×10 = 1604、隨機選擇 e 滿足 gcd(e,160) = 1，得 e=75、確定 d 滿足 d * e =1 mod 160 ,得 d=23 （因為 23×7 = 161 = 10×160+1 = 1 mod 160）6、公布公鑰 KU = {7,187}7、秘密保存私鑰 KR = { 23, 17, 11 }8、如果給定明文消息 M = 88

19、(88 <187)，加密得C =Me = 887 mod 187 = 11 9、解密密文 C = 11，得M = Cd = 1123 mod 187 = 88,四、RSA算法中的計算問題,1、加密和解密 (模指數(shù)運算)2、密鑰產(chǎn)生: 確定 p 和 q (素數(shù)檢測)3、密鑰產(chǎn)生: 選擇 e 或 d 并計算另一個(求逆運算)4、大整數(shù)的表示和運算問題,參見講義“公鑰算法的實現(xiàn).pptx”,五、RSA的安全性,1、強行攻

20、擊2、數(shù)學攻擊3、定時攻擊4、對RSA的其他攻擊,1、強行攻擊,包括對所有的私有密鑰都進行嘗試，其防范方式與其它密碼系統(tǒng)采用的方法相同，即采用一個大的（私有）密鑰。,2、數(shù)學攻擊,可以有三種以數(shù)學方式攻擊 RSA 的方法1、分解 N=p*q，這樣就可以計算 ø(N) 和 d；2、在不分解 N 的情況下直接計算 ø(N)，并確定d；3、不確定 ø(N) 而直接確定 d（解密指數(shù)）。目前認為這幾種

21、攻擊的時間開銷至少和對 N 進行因子分解一樣大給定 N 直接確定 ø(N) 就等價于對 N 進行因子分解；給定 e 和 N 求 d 似乎在時間開銷上至少和因子分解問題一樣大。,因子分解,因子分解的算法http://www.crypto-world.com/FactorPapers.html因子分解問題的進展（見后面的表）因子分解問題的進展是比較緩慢的；一個新算法的采用可能使因子分解問題取得很大進展。目前來看，10

22、24bit 以上的模數(shù) N 是安全的但在 p 和 q 的選擇上，還應施加一些限制（要選擇安全素數(shù)）。,因子分解的進展,分解RSA模數(shù)挑戰(zhàn)整數(shù) RSA-100, RSA-110 , …, RSA-500 是RSA模的一個列表，發(fā)布在因特網(wǎng)上為分解算法提供“挑戰(zhàn)”數(shù)字。每一個 RSA-d 是一個 d 位的十進制數(shù)，該數(shù)是大約等長的兩個素數(shù)的乘積。,因子分解的進展（續(xù)）,來源：http://www.crypto-world.com/Fa

23、ctorRecords.html,3、定時攻擊,定時攻擊是一種與常規(guī)攻擊方式完全不同的方法這種攻擊主要通過觀察解密時模指數(shù)運算的時間差異。定時攻擊是唯密文攻擊防范措施：常數(shù)取冪時間；隨機延時；盲化。,4、對RSA的其他攻擊,對RSA還存在以下兩種攻擊，但這兩種攻擊并不是由于算法本身的缺陷造成的，而是由于算法參數(shù)選擇不當造成的1、共模攻擊2、低（加密）指數(shù)攻擊,六、其它公鑰密碼體制,1、離散對數(shù)問題2、基于離散對數(shù)問題的

24、公鑰密碼體制,1、離散對數(shù)問題,定義：設 b 是一個整數(shù)，若對模 p 的一個原根 a, 有一整數(shù)x存在使得式子 b = ax (mod p) 成立，則 x 叫做以 a 為底的 b 對模 p 的離散對數(shù)，記為x = loga b (mod p) 或 x = inda,p(b)。注意：只有當 a 是模 p 的原根時，以 a 為底(模p)的離散對數(shù)才唯一存在；例：以2為底模19的部分離散對數(shù)如下,離散對數(shù)的

25、計算,離散對數(shù)問題是模指數(shù)計算問題的逆問題對于等式 b = ax mod p，在給定a、x 和 p時，計算 b 是十分直接的；然而，當給定 a、b 和 p，計算 x 是十分困難的事情（采用離散對數(shù)），難度似乎等同于RSA所必需的素數(shù)因子分解的復雜度。因此也可以說，在相應的群G中（如Z*p, p為素數(shù)），指數(shù)函數(shù)是一個單向函數(shù),2、基于離散對數(shù)問題的公鑰密碼體制,Diffie-Hellman密鑰交換協(xié)議歷史上首次公開提出的公鑰算法

26、，由Whitfield Diffie & Martin Hellman在1976年發(fā)表。ElGamal公鑰密碼體制和簽名算法DSA數(shù)字簽名算法Schnorr身份識別方案……,Diffie-Hellman密鑰交換協(xié)議,第一個公開發(fā)表的公開密鑰算法；由Diffie和Hellman在1976年，隨著公開密鑰密碼編碼學的概念而發(fā)表；該算法可以使兩個用戶安全地交換一個密鑰，以便用于以后的加密；該算法的安全性基于計算離散對數(shù)問

27、題的復雜性；許多商用產(chǎn)品都在使用這種密鑰交換技術。,Diffie-Hellman密鑰交換協(xié)議（續(xù)）,設 p 是一個素數(shù)，滿足 Zp 中的離散對數(shù)問題是難處理的， α∈Zp是一個原根，p 和α是公開的。在此條件下，通信雙方（設為A和B）可以執(zhí)行如下協(xié)議形成共享的秘密密鑰： （1）A隨機選擇 XA，0 <= XA<= p-2； （2）A計算 YA = αXA （mod p），并把YA發(fā)送給B； （3）B

28、隨機選擇 XB，0 <= XB <= p-2； （4）B計算 YB = αXB （mod p），并把YB發(fā)送給A； （5）A計算 K = (YB) XA =(αXB)XA =αXA XB (mod p) 且B計算 K’ = (YA) XB =(αXA)XB =αXA XB (mod p)

29、 顯然K = K’，A、B之間就形成了共享的秘密密鑰。,Diffie-Hellman密鑰交換協(xié)議（續(xù)）,顯然，如果攻擊者能夠計算X = logαY (mod p)， 那么D-H密鑰交換協(xié)議將是不安全的。因此D-H體制安全的一個必要條件是 Zp 上的離散對數(shù)問題是難處理的，這要求p至少有300位的十進制數(shù)，且p-1應該至少具有一個較大的素數(shù)因子。 Diffie-Hellman協(xié)議無法防止中間人攻擊。,Diffie-H

30、ellman的例子,用戶A, B想交換會話密鑰進行保密通信，他們共同選擇素數(shù) p=353, 原根 α=3，并進行如下步驟： 1）A、B分別隨機選擇私鑰:A: xA=97, B : xB=233 2） A、B分別計算公鑰:yA=397 mod 353 = 40 (對A)yB=3233 mod 353 = 248 (對B) 3）交換公鑰 4）A、B分別計算共享的會話密鑰:KAB= (Y

31、B) XA mod 353 = 24897 = 160 (對A)KAB= (YA) XB mod 353 = 40233 = 160 (對B),小結(jié),1、公鑰密碼體制概述2、RSA算法3、RSA的計算問題4、RSA的安全性5、其它公鑰密碼體制主要參考書《現(xiàn)代密碼學》《密碼編碼學與網(wǎng)絡安全:原理和實踐》，第四版《密碼學原理與實踐：第二版》,作業(yè),1、利用RSA算法對下列情況進行加密和解密：1）p=3, q=11,