1、信息安全概論2007年8月2022/7/291第4章 非對稱密碼體制 4.1 概述 4.2 RSA密碼算法4.3 其它密碼算法 2022/7/2924.1 概述4.1.1 對稱密碼面臨的困難4.1.2 非對稱密碼的產(chǎn)生4.1.3 非對稱密碼體制4.1.4 單向函數(shù)2022/7/2934.1.1 對稱密碼面臨的困難密鑰的管理、分發(fā)與協(xié)商假設(shè)某個系統(tǒng)有N個用戶相互進(jìn)行保密通信，任意兩個用戶使用互不相同的密鑰。密鑰管理問題：每個用戶需要保存N-1個密鑰。（如果N非常大，如何解決？）密鑰分發(fā)問題：系統(tǒng)總共需要N*(N-1)/2個密鑰：例如N =1000時, 999 *1000/2 = 499500。密

2、鑰協(xié)商問題：第一次協(xié)商好密鑰后，以后可以通過當(dāng)前密鑰秘密發(fā)送新密鑰。但第一次如何協(xié)商密鑰？（用戶秘密會面協(xié)商？陌生人怎么辦？遠(yuǎn)距離怎么辦？）消息發(fā)送者的身份確認(rèn)問題2022/7/2944.1.2 非對稱密碼的產(chǎn)生非對稱密碼的發(fā)展歷程計算機(jī)網(wǎng)絡(luò)特別是Internet的發(fā)展，促使非對稱密碼的出現(xiàn)。1976年，Diffie和Hellman在密碼學(xué)的新方向中提出來非對稱密碼的思想。（單向函數(shù)）1977年，RSA加密算法問世，名字來自3位作者Rivest, Shamir和Adleman。2022/7/2954.1.3 非對稱密碼體制密鑰(PK, SK)公鑰PK (Public Key)：通常公鑰是公開的

3、，可以被任何實(shí)體通過有效渠道獲取；私鑰SK (Secret Key)：通常私鑰是保密的，不能被任何實(shí)體通過非法渠道獲??；加密器EK解密器DK密文明文明文PK密鑰產(chǎn)生器SK2022/7/2964.1.3 非對稱密碼體制密碼算法組成密鑰生成KG( )：根據(jù)輸入的安全參數(shù) ，輸出密鑰對(PK, SK)。加密E( )：根據(jù)輸入的公鑰和消息，輸出密文。解密D( )：根據(jù)輸入的解密私鑰和密文，算法輸出消息或輸出表示密文不合法的特殊符號“?”。2022/7/2974.1.3 非對稱密碼體制設(shè)計要求參與方容易通過計算產(chǎn)生一對密鑰；在知道公開密鑰和待加密消息的情況下，發(fā)送方A容易產(chǎn)生密文；接收方B使用私有密鑰容

4、易通過計算解密所得密文，以便恢復(fù)原來的消息；敵手在知道公開密鑰的情況下，確定私有密鑰計算上不可行；敵手在知道公開密鑰和密文的情況下，恢復(fù)消息計算上不可行；兩個密鑰中的任何一個可以用來加密，對應(yīng)的另一個用來解密。2022/7/2984.1.3 非對稱密碼體制非對稱密碼的特點(diǎn)基于數(shù)學(xué)函數(shù)，而非替換和換位。加密密鑰和解密密鑰不同，且不能相互推理。解決了密碼管理、身份認(rèn)證和數(shù)字簽名等問題。非對稱密碼的關(guān)鍵非對稱密碼的安全性主要取決于構(gòu)造非對稱算法所依賴的數(shù)學(xué)問題。要求加密函數(shù)具有單向性，即求逆的困難性。設(shè)計非對稱密碼體制的關(guān)鍵是尋求一個合適的單向函數(shù)。2022/7/2994.1.4 單向函數(shù)令函數(shù)f是

5、集A到集B的映射，以f：AB表示。若對任意x1x2，x1, x2A，有f(x1)f(x2)，則稱f為單射，或1-1映射，或可逆的函數(shù)。f為可逆的充要條件是：存在函數(shù)g:BA，使對任意xA有g(shù)f(x)=x。一個可逆函數(shù)f：AB，若它滿足：對所有xA，易于計算f(x)；對“幾乎所有xA”由f(x)求x“極為困難”，以至于實(shí)際上不可能做到，則稱f為一單向(One-way)函數(shù)。定義中的“極為困難”是對現(xiàn)有的計算資源和算法而言。2022/7/29104.1.4 單向函數(shù)例一：令f是在有限域GF(p)中的指數(shù)函數(shù)，其中p是大素數(shù)，即 y = f(x) = ax。式中，xGF(p)，x為滿足0 xp1的整

6、數(shù)，其逆運(yùn)算是GF(p)中定義的對數(shù)運(yùn)算，即 x=logay (0 xp1)由x求y：即使當(dāng)p很大，也不難實(shí)現(xiàn)。為方便計算令a=2。例如p=2100時，需作100乘法。利用高速計算機(jī)由x計算ax可在0.1毫秒內(nèi)完成。從ax計算x：當(dāng)p=2100時，以平均速度的計算機(jī)進(jìn)行計算需時約1010.7秒(1年=107.5秒，故約為1600年！其中假定存儲量的要求能夠滿足)。2022/7/29114.1.4 單向陷門函數(shù)滿足下列條件的函數(shù)f稱為單向陷門函數(shù)：給定x，計算y = f(x)是容易的；給定y，計算x使y = f(x)是困難的；存在z，已知z時, 對給定的任何y，若相應(yīng)的x存在，則計算x使y =

7、f(x)是容易的。兩個難題陷門函數(shù)實(shí)際上不是單向函數(shù)，因?yàn)閱蜗蚝瘮?shù)是在任何條件下求逆都是困難的；陷門可能不止一個，通過試驗(yàn)一個個陷門就能容易地找到逆。如果陷門信息的保密性不強(qiáng)，求逆也就不難。2022/7/29124.2 RSA公鑰密碼體制4.2.1 概述4.2.2 算法描述4.2.3 算法舉例4.2.4 算法安全性2022/7/29134.2.1 概述RSA算法是1977年由MIT三位密碼學(xué)家Rivest、Shamirh和Adleman發(fā)明，是迄今為止最為成熟完善的公鑰密碼體制。RSA算法基于數(shù)論構(gòu)造，具體難度問題是大素數(shù)乘積的因子分解。將兩個大素數(shù)相乘十分容易，但對其乘積進(jìn)行因式分解卻極其困

8、難，因此可以將乘積作為加密密鑰公開。RSA算法的缺陷是無法從理論上把握它的保密性RSA算法的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明RSA算法的破譯難度等價于大數(shù)分解難度。2022/7/29144.2.2 算法描述密鑰對生成選取兩個大素數(shù)p和q，n=p*q；計算n的歐拉函數(shù)(n) =(p-1)*(q-1)；隨機(jī)選取與(n)互素的加密密鑰e（公開），即 gcd(e, (n)=1；利用擴(kuò)展歐幾里德算法計算解密密鑰d，滿足de=1 mod (n)；公鑰為(n, e)，私鑰為(n, d)。2022/7/29154.2.2 算法描述加密過程y =E(x) =xe mod n. (xn)解密過程x

9、 =D(y) =yd mod n正確性驗(yàn)證yd mod n = xed mod n = xk(n)+1 mod n = x*xk(n) mod n = x*1 mod n = x歐拉定理：若n, x為正整數(shù)，且n, x互素，即gcd(x, n) = 1，則x(n) 1 (mod n)2022/7/29164.2.2 算法描述正確性驗(yàn)證（歐拉定理）x與n互素，則由歐拉定理x (p-1)(q-1) mod n 1 mod n得x*xk (p-1)(q-1) mod n x mod n gcd(x,n)1，由于n=pq，且p和q都是素數(shù)，則x是p或q的倍數(shù)。設(shè)x=tp，其中t為一正整數(shù)，而gcd(x

10、,q) =1(mn)。由歐拉定理xq-1 mod q 1 mod q得1) xk(p-1)(q-1) mod q 1 mod q xk(p-1)(q-1) =1+rq (兩邊同時乘以x=tp)2) x*xk(p-1)(q-1) =(1 + rq) tp = tp + rtpq = x + rtn3) x*xk(p-1)(q-1)modn (x + rtn)modn x modn 2022/7/29174.2.3 算法舉例產(chǎn)生密鑰對選取p=17，q=13，則n=p*q=221，(n)=(p-1)*(q-1)= 192再選取與(n)互素的e=11，則公鑰為(n, e)= (221,11)根據(jù)擴(kuò)展歐

11、幾里得算法求得d =e-1 mod (n) =11-1 mod 192 =35，則私鑰為(n, d)= (221, 35)加解密過程設(shè)明文x=9，加密：y =xe mod n = 911 mod 221 = 185。解密：x =yd mod n = 18535 mod 221 = 9。2022/7/29184.2.3 算法舉例加解密的計算問題18535 mod 221，如果先計算18535再模221，那么中間結(jié)果遠(yuǎn)遠(yuǎn)超出了計算機(jī)所允許的整數(shù)取值范圍。(a b) mod n (a mod n) (b mod n)mod n計算yd (18535)d = dk2k + dk-12k-1 + d12

12、 + d0，其中di0或1 (i= 0, , k)yd = (ydk)2ydk-1)2ydk-2)2yd1)2yd0例如35 =125 + 024 + 023 + 022 + 121 + 120 y35= (y1)2y0)2y0)2y0)2y1)2y12022/7/29194.2.4 算法安全性RSA算法的安全性依賴于大數(shù)分解的難度從數(shù)學(xué)上從未證明過需要分解n才能從y和e中計算出x；可通過猜測(p-1)(q-1)的值來攻擊RSA，但這種攻擊沒有分解n容易；可嘗試每一種可能的d，直到獲得正確的一個，這種窮舉攻擊還沒有試圖分解n更有效；129位十進(jìn)制數(shù)字的模數(shù)是能分解的臨界數(shù)，n應(yīng)該大于這個數(shù)。1

13、994年4月26日，RSA-129被因子分解，并破解了附帶的密文。2022/7/29204.2.4 算法安全性人類數(shù)學(xué)史上最給力的數(shù)學(xué)論文之一論文標(biāo)題：RSA-129。 論文作者： （六百多位）論文內(nèi)容：11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541 =34905 29510 84765 09491 47849 61990 38981

14、33417 76463 84933 87843 99082 0577 * 32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 885332022/7/2921對RSA的選擇密文攻擊例一(對協(xié)議的攻擊)：Eve在Alice的通信過程中進(jìn)行竊聽，設(shè)法成功選取了一個用她的公開密鑰加密的密文c。Eve想讀出信息m，m = cd。Eve選取一個隨機(jī)數(shù)r，滿足r小于n。她得到Alice的公鑰e：x re modn y xc modn t r-1 modnEve讓Alice用她的私人密鑰對y簽名，以便解密y：u yd

15、 modnEve計算：tu modn r-1yd modn r-1xdcd modn cd modn m2022/7/2922對RSA的選擇密文攻擊例二(對協(xié)議的攻擊)：Trend是一個公開的計算機(jī)公證人，Mallory想讓Trend對一個本來不愿意簽名的消息簽名，例如m1。Mallory計算(如果可能的話)：m1 m2m3 modnEve讓Alice用她的私人密鑰對m2和m3分別簽名；Eve計算：m1d (m2d modn) (m3d modn)利用的缺陷：指數(shù)運(yùn)算保持了輸入的乘法結(jié)構(gòu)(xm)d modn = xdmd modn2022/7/2923對RSA的公共模數(shù)攻擊不同的使用者采用相同

16、模數(shù)n，即使e和d不同，假如兩個公鑰互素，則無需任何的解密技術(shù)就可以恢復(fù)明文。設(shè)m位明文，兩個公鑰為e1和e2，模數(shù)為n，兩個密文為：c1 me1 modn c2 me2 modn由于e1和e2互素，根據(jù)擴(kuò)展歐幾里德算法找出r和s，滿足：re1 + se2 = 1假定r是負(fù)數(shù)(r或s中有一個必須是負(fù)數(shù))，用歐幾里德算法可計算c1-1：(c1-1)-r c2s = m modn2022/7/2924對RSA的低加/解密指數(shù)攻擊對RSA的低加密指數(shù)攻擊選取較低的e值可以加快計算速度；采用不同的RSA公鑰及相同的e值，對e(e+1)/2個線形相關(guān)的消息加密，則存在一種能攻擊該系統(tǒng)的方法阻止該攻擊的方

17、法是用獨(dú)立隨機(jī)值填充消息，使得m和n大小一樣。對RSA的低解密指數(shù)攻擊如果d達(dá)到n的1/4大小，且e比n小，那么存在一種攻擊能夠恢復(fù)d；假如e和d隨機(jī)選擇，該攻擊很少發(fā)生；假如e的值很小，則d的值會比較大，該攻擊不可能發(fā)生。消息比較短，則md和ce都小于n保證memodn me2022/7/2925實(shí)現(xiàn)RSA密碼方案的限制根據(jù)前面成功的攻擊，Jadith Moore列出了使用RSA的一些限制知道了對于一個給定模數(shù)的一個加/解密密鑰指數(shù)對，攻擊者就能分解這個模數(shù)；知道了對于一個給定模數(shù)的一個加/解密密鑰指數(shù)對，攻擊者無需分解n就可以計算出別的加/解密對；在通信網(wǎng)絡(luò)中，利用RSA的協(xié)議不應(yīng)該使用公

18、共模數(shù)；消息應(yīng)用隨機(jī)數(shù)填充以避免對加密指數(shù)的攻擊；解密指數(shù)應(yīng)該大。2022/7/29264.2.4 算法安全性不能證明RSA密碼破譯等同于大數(shù)因子分解速度問題：提高pq將使開銷指數(shù)級增長至少有9個明文，加密后不變，即xe mod n=x普通用戶難于選擇p、q。對p、q的基本要求：p、q不相同，即不要太接近，又不能差別太大p-1、q-1都有大素數(shù)因子，增加猜測(n) 難度gcd( p-1,q-1)應(yīng)當(dāng)小p、q選擇不當(dāng)，則變換周期性、封閉性而泄密。例：p=17，q=11，e=7，則n=187。設(shè)x=123，則明文x經(jīng)過4次加密，恢復(fù)成明文。2022/7/29274.3 其它密碼算法 4.3.1 D

19、iffie-Hellman密碼算法4.3.2背包密碼算法4.3.3 ElGamal密碼算法 4.3.4 橢圓曲線密碼算法2022/7/29284.3.1 Diffie-Hellman密碼算法Diffie和Hellman在密碼學(xué)新方向一文中給出了非對稱密碼算法的思想。它不是真正意義上的非對稱密碼實(shí)例，僅僅是一個單向函數(shù)；算法的目的是使得兩個用戶安全地交換一個會話密鑰。密鑰交換(秘密共享)發(fā)送方和接受方基于公鑰密碼體制交換會話密鑰；會話密鑰采用對稱加密體制加密需要保密傳輸?shù)南ⅰ?022/7/29294.3.1 Diffie-Hellman密碼算法密鑰交換系統(tǒng)工作原理發(fā)送者接收者接收者的公鑰加密接

20、收者的私鑰解密加密解密會話密鑰交換階段保密信息交換階段2022/7/29304.3.2背包密碼算法Ralph Merkle和Martin Hellman開發(fā)了第一個非對稱密碼算法背包算法。(背包算法只能用于加密)背包問題的描述：給定一堆物品，每個重量不同，能否將這些物品中的幾件放入一個背包中，使之等于一個給定的重量？給定一系列值m1,m2,mn和一個和s，計算bi使之滿足s = b1m1 + b2m2 + + bimi背包密碼體制的安全性基于背包難題，它證明了如何將一個NP完全問題應(yīng)用到非對稱密碼學(xué)，后來被證明是不安全的。2022/7/29314.3.3 ElGamal密碼算法 ElGamal

21、密碼算法由T.ElGamal在1985年提出ElGamal的安全性基于求解離散對數(shù)問題的困難性 ElGamal算法描述所有的用戶都共享一個素數(shù)p以及一個Zp的生成元a，系統(tǒng)中每一個用戶U都隨機(jī)挑選一個整數(shù)mu， 并計算Cu =amu mod p，然后用戶U公開Cu作為公開密鑰，并保存整數(shù)mu作為自己的私鑰。2022/7/29324.3.3 ElGamal密碼算法 密鑰對產(chǎn)生辦法首先選擇一個素數(shù)p，兩個隨機(jī)數(shù)g和x(g, x p)，計算 y = gx (mod p)，則其公鑰為g和p，私鑰是x。g和p可由一組用戶共享。ElGamal 加解密過程被加密信息為m，首先選擇一個隨機(jī)數(shù)k，k與 p-1互質(zhì)，計算a = gk ( mod p) ，b =m*yk ( mod p ) ( a, b )為密文，是明文的兩倍長。解密時計算m = b / ax ( mod p) 2022/7/29334.3.3 ElGamal密碼算法 ElGamal密碼算法最大的特點(diǎn)是非確定性由于密文依賴于執(zhí)行加密過程所選擇的隨機(jī)數(shù)k，所以加密相同的明文可能會產(chǎn)生不同的密文。ElGamal密碼算法的安全性依賴于乘法群 上的離散對數(shù)計算復(fù)雜度。一般