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

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

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

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

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

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

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

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

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

9、。定時(shí)攻擊（邊信道攻擊）,二、幾個(gè)引理,1、費(fèi)馬定理2、歐拉函數(shù)3、歐拉定理,1、費(fèi)馬定理,設(shè) p 是素?cái)?shù)，并且 gcd(a, p)=1，則ap-1 mod p = 1 該定理也叫費(fèi)馬小定理常用于公鑰密碼和素性檢測(cè)例：如果a=7, p=19，計(jì)算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ù)的個(gè)數(shù)計(jì)算ø(n)需要對(duì)整數(shù) n 進(jìn)行素因子分解兩個(gè)特殊情況1）對(duì)于素?cái)?shù) p，ø(p) = p-12）對(duì)于合數(shù) n = p×q （p、q均為素?cái)?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 歐拉定理是費(fèi)馬定理的一般化例設(shè) a=3; n

12、=10; ø(10)=4，則 3ø(10) = 34 = 81 = 1 mod 10設(shè)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ù)域中的求冪運(yùn)算算法中使用了很大的整數(shù)（如1024bit，約10308）算法的安全性基于大整數(shù)分解的困難性,2、RSA的密鑰產(chǎn)生,RSA的用戶都必須通過(guò)如下方法產(chǎn)生公鑰/私鑰對(duì)1）隨機(jī)選擇兩個(gè)大素?cái)?shù) p 和 q（1075—10150數(shù)量級(jí)）2）計(jì)算模數(shù) N = p*q，注意 ø(N) = (p-1)

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

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

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

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

18、n) = (p–1)(q-1) = 16×10 = 1604、隨機(jī)選擇 e 滿足 gcd(e,160) = 1，得 e=75、確定 d 滿足 d * e =1 mod 160 ,得 d=23 （因?yàn)?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算法中的計(jì)算問(wèn)題,1、加密和解密 (模指數(shù)運(yùn)算)2、密鑰產(chǎn)生: 確定 p 和 q (素?cái)?shù)檢測(cè))3、密鑰產(chǎn)生: 選擇 e 或 d 并計(jì)算另一個(gè)(求逆運(yùn)算)4、大整數(shù)的表示和運(yùn)算問(wèn)題,參見(jiàn)講義“公鑰算法的實(shí)現(xiàn).pptx”,五、RSA的安全性,1、強(qiáng)行攻

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

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

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

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

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

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

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

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

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

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

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

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