云計算與安全_公開密鑰算法RSA及其實現(xiàn)

1、云計算與安全云計算與安全-公開密鑰算法公開密鑰算法Topicsq網(wǎng)絡(luò)安全的需求網(wǎng)絡(luò)安全的需求q云計算的需求云計算的需求q云計算與網(wǎng)絡(luò)安全的關(guān)系云計算與網(wǎng)絡(luò)安全的關(guān)系qRSA算法概述算法概述qRSA算法的實現(xiàn)算法的實現(xiàn)云計算與安全云計算與安全-公開密鑰算法公開密鑰算法 公開密鑰算法是非對稱算法，即密鑰分為公鑰和私公開密鑰算法是非對稱算法，即密鑰分為公鑰和私鑰，因此稱雙密鑰體制鑰，因此稱雙密鑰體制 雙鑰體制的公鑰可以公開，因此也稱公鑰算法雙鑰體制的公鑰可以公開，因此也稱公鑰算法 公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法的出現(xiàn)，給密碼的發(fā)展開辟了新的方向。公鑰算法雖然已經(jīng)歷了公鑰算法雖然

2、已經(jīng)歷了2020多年的發(fā)展，但仍具有強勁多年的發(fā)展，但仍具有強勁的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域的發(fā)展勢頭，在鑒別系統(tǒng)和密鑰交換等安全技術(shù)領(lǐng)域起著關(guān)鍵的作用起著關(guān)鍵的作用加密與解密由不同的密鑰完成加密與解密由不同的密鑰完成 加密：加密： 解密：解密：知道加密算法，從加密密鑰得到解密密鑰在計算上是知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的不可行的兩個密鑰中任何一個都可以作為加密而另一個用作解兩個密鑰中任何一個都可以作為加密而另一個用作解密（不是必須的）密（不是必須的）公開密鑰算法的基本要求公開密鑰算法的基本要求:( )KUXY Y EX:( )( )KRKRKUYX X

3、D YDEX基于公開密鑰的加密過程基于公開密鑰的加密過程用公鑰密碼實現(xiàn)保密用公鑰密碼實現(xiàn)保密 用戶擁有自己的密鑰對用戶擁有自己的密鑰對(KU,KR) 公鑰公鑰 KU公開，私鑰公開，私鑰KR保密保密 :( )bKUAB YEX:( )( )bbbKRKRKUB DYDEXX基于公開密鑰的鑒別過程基于公開密鑰的鑒別過程用公鑰密碼實現(xiàn)鑒別用公鑰密碼實現(xiàn)鑒別 條件：兩個密鑰中任何一個都可以用作加密而另外條件：兩個密鑰中任何一個都可以用作加密而另外一個用作解密一個用作解密鑒別：鑒別： 鑒別保密鑒別保密 :( ):( )( )aabaKRKUKUKRAALL YEXALL DYDEXX:():( )baa

4、bKUKRKUKRAB ZEDXB EDZX公開密鑰算法公開密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：公鑰算法的種類很多，具有代表性的三種密碼： 基于整數(shù)分解難題（基于整數(shù)分解難題（IFPIFP）的算法體制）的算法體制 基于離散對數(shù)難題（基于離散對數(shù)難題（DLPDLP）算法體制）算法體制基于橢圓曲線離散對數(shù)難題（基于橢圓曲線離散對數(shù)難題（ECDLPECDLP）的算法體制）的算法體制RSA 算法算法Euler 函數(shù)函數(shù) 所有模所有模m和和r同余的整數(shù)組成剩余類同余的整數(shù)組成剩余類r 剩余類剩余類r中的每一個數(shù)和中的每一個數(shù)和m互素的充要條件是互素的充要條件是r和和m互素互素 和和m互素的

5、同余類數(shù)目用互素的同余類數(shù)目用(m)表示，稱表示，稱m的的Euler函函數(shù)數(shù) 當(dāng)當(dāng)m是素數(shù)時，小于是素數(shù)時，小于m的所有整數(shù)均與的所有整數(shù)均與m互素，因互素，因此此(m)=m-1對對n=pq, p和和q 是素數(shù)，是素數(shù)，(n)=(p)(q)=(p-1)(q-1)Euler 函數(shù)函數(shù)舉例舉例 設(shè)設(shè)p=3, q=5, 那么那么 （15）=（3-1）* *（5-1）=8 這這8個模個模15的剩余類是的剩余類是： 1，2，4，7，8，11，13，14 q Med =M mod nq 加密加密: C=Me mod nq 解密解密: M=Cd mod N = (Me)d mod n= Med mod nn

6、計算Me和Cd是比較容易的n由e和n確定d是不可行的q Mk(n)1 = M mod N (N)=(p-1)(q-1) qed=k(N)+1qed1 mod (N)RSA算法的實現(xiàn)算法的實現(xiàn) 實現(xiàn)的步驟如下：實現(xiàn)的步驟如下：Bob為實現(xiàn)者為實現(xiàn)者 (1) Bob尋找出兩個大素數(shù)尋找出兩個大素數(shù)p和和q (2) Bob計算出計算出n=pq 和和(n)=(p-1)(q-1) (3) Bob選擇一個隨機數(shù)選擇一個隨機數(shù)e (0e (n)，滿足，滿足(e,(n)=1 (4) Bob使用輾轉(zhuǎn)相除法計算使用輾轉(zhuǎn)相除法計算d=e-1(mod(n) (5) Bob在目錄中公開在目錄中公開n和和e作為公鑰作為公

7、鑰密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點在于如何分解體制的關(guān)鍵點在于如何分解n。若分。若分解成功使解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后由公，然后由公開的開的e，解出秘密的，解出秘密的dRSA算法編制算法編制 參數(shù)參數(shù)T=NT=N；私鑰私鑰SK=DSK=D；公鑰公鑰PK=EPK=E； 設(shè)：明文設(shè)：明文M M，密文，密文C C，那么：，那么： 用公鑰作業(yè)：用公鑰作業(yè)：M ME E mod N = C mod N = C 用私鑰作業(yè)：用私鑰作業(yè)：M MD D mod N = M mod N = MRSA算法舉例算法舉例設(shè)設(shè) p=7, q=17, n=7p=

8、7, q=17, n=7* *17=119; 17=119; 參數(shù)參數(shù)T=n=119;T=n=119;(n)=(7-1)(17-1)=96;(n)=(7-1)(17-1)=96;選擇選擇e=5, gcd(5,96)=1; e=5, gcd(5,96)=1; 公鑰公鑰pk=5;pk=5;計算計算d, ( dd, ( d* *e) mod 96=1; d=77; e) mod 96=1; d=77; 私鑰私鑰sk=77;sk=77;設(shè)設(shè): :明文明文m=19m=19 加密：（加密：（1919）5 5 mod 119 = 66 mod 119 = 66 脫密：（脫密：（6666）7777 mod 1

9、19 = 19 mod 119 = 19RSA算法的安全性分析算法的安全性分析密碼分析者攻擊密碼分析者攻擊RSA體制的關(guān)鍵點在于如何分解體制的關(guān)鍵點在于如何分解n若分解成功使若分解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后由公開的然后由公開的e，解出秘密的，解出秘密的d若使若使RSA安全，安全，p與與q必為足夠大的素數(shù)，使分析者必為足夠大的素數(shù)，使分析者沒有辦法在多項式時間內(nèi)將沒有辦法在多項式時間內(nèi)將n分解出來分解出來RSA算法的安全性分析算法的安全性分析建議選擇建議選擇p和和q大約是大約是100位的十進(jìn)制素數(shù)位的十進(jìn)制素數(shù)模模n的長度要求至少是的長度要求至少是512比特比特EDI攻擊標(biāo)準(zhǔn)使用的攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定算法中規(guī)定n的長度為的長度為512至至1024比特位之間，但必須是比特位之間，但必須是128的倍數(shù)的倍數(shù)國際數(shù)字簽名標(biāo)準(zhǔn)國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定中規(guī)定n的長度位的長度位512比比