RSA公鑰密碼體制創(chuàng)新課件

1、RSA公鑰密碼體制公鑰密碼體制e_mail: yongzhe .cn電話：電話：公鑰密碼體制的基本概念公鑰密碼體制的基本概念 公鑰密碼體制的概念是在解決對稱密碼體制中最難解決的兩公鑰密碼體制的概念是在解決對稱密碼體制中最難解決的兩個(gè)問題時(shí)提出的，這兩個(gè)問題是密鑰分配和數(shù)字簽字。個(gè)問題時(shí)提出的，這兩個(gè)問題是密鑰分配和數(shù)字簽字。 對稱密碼體制在進(jìn)行密鑰分配時(shí)，要求通信雙方已經(jīng)有了一對稱密碼體制在進(jìn)行密鑰分配時(shí)，要求通信雙方已經(jīng)有了一個(gè)共享的密鑰，或者可籍助于一個(gè)密鑰分配中心臨時(shí)分配會(huì)個(gè)共享的密鑰，或者可籍助于一個(gè)密鑰分配中心臨時(shí)分配會(huì)話密鑰。對第一個(gè)要求，常?？捎萌斯し绞绞孪葌魉碗p方最話密鑰。對第

2、一個(gè)要求，常常可用人工方式事先傳送雙方最初共享的密鑰，這種方法成本很高，而且還完全依賴信使的初共享的密鑰，這種方法成本很高，而且還完全依賴信使的可靠性。第二個(gè)要求則完全依賴于密鑰分配中心的可靠性?？煽啃浴５诙€(gè)要求則完全依賴于密鑰分配中心的可靠性。 第二個(gè)問題數(shù)字簽字考慮的是如何為數(shù)字化的消息或文件提第二個(gè)問題數(shù)字簽字考慮的是如何為數(shù)字化的消息或文件提供一種類似于為書面文件手書簽字的方法。供一種類似于為書面文件手書簽字的方法。 1976年年W.Diffie和和M.Hellman對解決上述兩個(gè)問題有了突破對解決上述兩個(gè)問題有了突破，從而提出了公鑰密碼體制，從而提出了公鑰密碼體制。公鑰密碼體制的原

3、理公鑰密碼體制的原理 公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將公鑰密碼算法的最大特點(diǎn)是采用兩個(gè)相關(guān)密鑰將加密和解密能力分開，其中一個(gè)密鑰是公開的，稱加密和解密能力分開，其中一個(gè)密鑰是公開的，稱為公開密鑰，簡稱為公開密鑰，簡稱公鑰公鑰，用于加密；另一個(gè)密鑰是，用于加密；另一個(gè)密鑰是為用戶專用，因而是保密的，稱為秘密密鑰，簡稱為用戶專用，因而是保密的，稱為秘密密鑰，簡稱私鑰私鑰，用于解密。因此公鑰密碼體制也稱為雙鑰密，用于解密。因此公鑰密碼體制也稱為雙鑰密碼體制或非對稱密碼體制。碼體制或非對稱密碼體制。算法有以下重要特性：算法有以下重要特性：已知密碼算法和公鑰，求解私鑰在計(jì)算上不可行。已知密碼算

4、法和公鑰，求解私鑰在計(jì)算上不可行。用公鑰加密的消息只能用與之對應(yīng)的私鑰來解密。用公鑰加密的消息只能用與之對應(yīng)的私鑰來解密。加密和解密操作在計(jì)算上可快速執(zhí)行。加密和解密操作在計(jì)算上可快速執(zhí)行。公開密鑰體制用于加密的原理公開密鑰體制用于加密的原理加密加密c=EPKB(m) 解密解密m=DSKB(c)公鑰密碼體制用于認(rèn)證的原理公鑰密碼體制用于認(rèn)證的原理簽名：簽名：s=ESKA(m) 驗(yàn)證簽名：驗(yàn)證簽名：m=DPKA(s)公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足以下要求公鑰密碼算法應(yīng)滿足以下要求: 接收方接收方B產(chǎn)生密鑰對產(chǎn)生密鑰對(PKB,SKB)在計(jì)算上是容在計(jì)算上是容

5、易的。易的。 發(fā)方發(fā)方A用接收方用接收方B的公鑰對消息的公鑰對消息m加密以產(chǎn)加密以產(chǎn) 生密文生密文c，即，即c=EPKB(m)在計(jì)算上是容易的。在計(jì)算上是容易的。 接收方接收方B用自己的私鑰對密文用自己的私鑰對密文c進(jìn)行解密，即進(jìn)行解密，即 m=DSKB(c)在計(jì)算上是容易的。在計(jì)算上是容易的。公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足的要求 敵手由敵手由B的公鑰的公鑰PKB求其私鑰求其私鑰SKB在計(jì)算上在計(jì)算上 是不可行的。是不可行的。 敵手由密文敵手由密文c和和B的公鑰的公鑰PKB恢復(fù)明文恢復(fù)明文m在計(jì)在計(jì) 算上是不可行的。算上是不可行的。 加、解密次序可換，即加、解密次序可換，即DSKB

6、(EPKB(m) =EPKB(DSKB(m) 其中最后一條雖然非常有用，但不是對所其中最后一條雖然非常有用，但不是對所有的算法都作要求。有的算法都作要求。公鑰密碼算法應(yīng)滿足的要求公鑰密碼算法應(yīng)滿足的要求以上要求的本質(zhì)之處在于要求一個(gè)以上要求的本質(zhì)之處在于要求一個(gè)單向陷門函數(shù)單向陷門函數(shù)。稱一個(gè)函數(shù)是單向陷門函數(shù)，是指該函數(shù)是易于計(jì)算的，但求稱一個(gè)函數(shù)是單向陷門函數(shù)，是指該函數(shù)是易于計(jì)算的，但求它的逆是不可行的，除非再已知某些附加信息。當(dāng)附加信息給它的逆是不可行的，除非再已知某些附加信息。當(dāng)附加信息給定后，求逆可在多項(xiàng)式時(shí)間完成。定后，求逆可在多項(xiàng)式時(shí)間完成。總結(jié)為：單向陷門函數(shù)是一族可逆函數(shù)總

7、結(jié)為：單向陷門函數(shù)是一族可逆函數(shù)ft，滿足：，滿足： Y=ft(X)易于計(jì)算（當(dāng)易于計(jì)算（當(dāng)ft和和X已知時(shí)）。已知時(shí)）。 X=ft-1(Y)在計(jì)算上是不可行的（當(dāng)在計(jì)算上是不可行的（當(dāng)Y、ft已知，但已知，但t未知時(shí)）。未知時(shí)）。 X=ft-1(Y)易于計(jì)算（當(dāng)易于計(jì)算（當(dāng)Y、ft 、t 均已知時(shí)）。均已知時(shí)）。因此，實(shí)現(xiàn)公鑰密碼的核心就是尋找合適的單向陷門函數(shù)。因此，實(shí)現(xiàn)公鑰密碼的核心就是尋找合適的單向陷門函數(shù)。RSA算法算法 RSA算法是算法是1978年由年由R.Rivest, A.Shamir和和L.Adleman提出的提出的一種用數(shù)論構(gòu)造的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。一種用

8、數(shù)論構(gòu)造的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。RivestShamirAdleman2002 Turing Award (June03)RSA的數(shù)論基礎(chǔ)的數(shù)論基礎(chǔ)算法描述算法描述 密鑰的產(chǎn)生密鑰的產(chǎn)生 秘密選取兩個(gè)大素?cái)?shù)秘密選取兩個(gè)大素?cái)?shù)p和和q。 計(jì)算計(jì)算n=pq，(n)=(p-1)(q-1),其中其中(n)是是n的歐拉函數(shù)值。的歐拉函數(shù)值。 選一整數(shù)選一整數(shù)e，滿足，滿足1e(n)，且，且gcd(n),e)=1。 計(jì)算計(jì)算d，滿足，滿足de1 mod (n),即即d是是e在模在模(n)下的乘法逆元，因下的乘法逆元，因e與與(n)互素，由?；ニ?，由模運(yùn)算可知，它的乘法逆元一定存在。運(yùn)算可知

9、，它的乘法逆元一定存在。 以以e,n為公開鑰為公開鑰,d,n為秘密鑰。為秘密鑰。算法描述算法描述 加密加密 加密時(shí)首先將明文比特串分組，使得每個(gè)分組對應(yīng)加密時(shí)首先將明文比特串分組，使得每個(gè)分組對應(yīng)的十進(jìn)制數(shù)小于的十進(jìn)制數(shù)小于n，即分組長度小于，即分組長度小于log2n。然后對。然后對每個(gè)明文分組每個(gè)明文分組m，作加密運(yùn)算：，作加密運(yùn)算： cme mod n算法描述算法描述 解密解密對密文分組的解密運(yùn)算為：對密文分組的解密運(yùn)算為： mcd mod nRSA 的單向陷門函數(shù)的單向陷門函數(shù) 參數(shù)參數(shù):N=pq. N 1024 bits. p,q 512 bits.e 加密指數(shù)加密指數(shù) gcd(e,

10、(N) ) = 1 . 單向函數(shù)單向函數(shù): RSA(M) = Me (mod N) 其中其中 M ZN* 陷門陷門:d 解密指數(shù)解密指數(shù).其中其中 e d = 1 (mod (N) ) 解密解密:RSA(M)d = Med = Mk (N)+1 = M (mod N)因子分解問題因子分解問題 三種數(shù)學(xué)攻擊方法三種數(shù)學(xué)攻擊方法 分解分解 N=p.q, 因此可計(jì)算出因此可計(jì)算出 (N)，從而確定，從而確定d 直接確定直接確定(N)，然后找到，然后找到d 直接確定直接確定d 大家相信：由大家相信：由N確定確定(N)等價(jià)于因子分解等價(jià)于因子分解舉例舉例選選p=7，q=17。求求n=pq=119，(n)

11、=(p-1)(q-1)=96。取取e=5，滿足，滿足1e(n)，且，且gcd(n),e)=1。確定滿足確定滿足de=1 mod 96且小于且小于96的的d，因?yàn)?，因?yàn)?75=385=496+1，所以，所以d為為77，因此公開鑰為因此公開鑰為5，119，秘密鑰為，秘密鑰為77，119。設(shè)明文設(shè)明文m=19，則由加密過程得密文為，則由加密過程得密文為c195 mod 1192476099 mod 11966解密為解密為6677mod 11919計(jì)算問題：加密與解密過程中的指數(shù)運(yùn)算計(jì)算問題：加密與解密過程中的指數(shù)運(yùn)算求求am可如下進(jìn)行，其中可如下進(jìn)行，其中a，m是正整數(shù)：是正整數(shù)： 將將m表示為二進(jìn)

12、制形式表示為二進(jìn)制形式bk bk-1b0，即，即m=bk2k+bk-12k-1+b12+b0因此因此12012222kkkbbbbbmaaaaaa 例題例題19=124+023+022+121+120，所以，所以a19=(a1)2a0)2a0)2a1)2a1例題例題例例4.9 求求7560 mod 561。將將560表示為表示為1000110000，算法的中間結(jié)果如表所示。所以，算法的中間結(jié)果如表所示。所以7560 mod 561=1。i9876543210bi1000110000c01248173570140 280 560d1749157 526160241 298 166 671例題例題

13、計(jì)算計(jì)算551 mod 97計(jì)算問題：密鑰的產(chǎn)生中的計(jì)算問題計(jì)算問題：密鑰的產(chǎn)生中的計(jì)算問題 尋找大素?cái)?shù)尋找大素?cái)?shù) 如何選取滿足如何選取滿足1e(n)和和gcd(n),e)=1的的e，并計(jì)，并計(jì)算滿足算滿足de1 mod (n)的的d。這一問題可由推廣的。這一問題可由推廣的Euclid算法完成。算法完成。例題例題已知已知 RSA公鑰加密方案中公鑰加密方案中 p=29 q=67 n=1943 e=701 m=23求密文求密文例題例題已知已知 RSA公鑰加密方案中公鑰加密方案中 p=29 q=67 n=1943 e=701 c=1926求明文求明文RSA中參數(shù)的選擇：密鑰長度中參數(shù)的選擇：密鑰長度

14、 估計(jì)在未來一段比較長的時(shí)期，密鑰長度介于估計(jì)在未來一段比較長的時(shí)期，密鑰長度介于1024比特至比特至2048比特之間的比特之間的RSA是安全的。是安全的。NIST:Cipher key-sizeModulus size 56 bits 512 bits. 80 bits 1024 bits 112bits 2048 bits 128 bits 3072 bits 192 bits 7680 bits 256 bits (AES)15360 bits RSA中參數(shù)的選擇：中參數(shù)的選擇：p和和q的選擇的選擇（1） |p-q|要大要大（2） p-1和和q-1都應(yīng)有大素因子都應(yīng)有大素因子強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)

15、強(qiáng)素?cái)?shù)是滿足如下條件的安全素?cái)?shù)強(qiáng)素?cái)?shù)是滿足如下條件的安全素?cái)?shù): p - 1 和和q- 1 的最大公因子應(yīng)該較小的最大公因子應(yīng)該較小, p + 1 和和q+ 1 都應(yīng)有都應(yīng)有大的素因子大的素因子, p - 1 和和q- 1 都應(yīng)有大的素因子都應(yīng)有大的素因子, 分別分別記為記為p 和和q, p - 1 和和q- 1 都應(yīng)有大的素因子。都應(yīng)有大的素因子。強(qiáng)素?cái)?shù)可以大大增強(qiáng)其抗窮舉攻擊和因子分解攻擊的強(qiáng)素?cái)?shù)可以大大增強(qiáng)其抗窮舉攻擊和因子分解攻擊的強(qiáng)度強(qiáng)度例題例題3999991是兩個(gè)素?cái)?shù)的乘積，那么較大的素?cái)?shù)是？是兩個(gè)素?cái)?shù)的乘積，那么較大的素?cái)?shù)是？例題例題已知已知RSA算法中算法中n=323, (n)=

16、288求求p,q例題例題某一用戶，在某一用戶，在RSA算法使用過程中，暴露了私鑰，其算法使用過程中，暴露了私鑰，其不改變模，而只改變公鑰和私鑰，問這樣安全嗎？不改變模，而只改變公鑰和私鑰，問這樣安全嗎？例題例題 Bob的的 RSA 模數(shù)為模數(shù)為 n = pq， p q 為不同的大素?cái)?shù)為不同的大素?cái)?shù). 他的公開密鑰是他的公開密鑰是e. Alice 發(fā)送發(fā)送 Bob 對消息對消息m加密后加密后的密文的密文 c me (mod n). Bob 在對消息解密之后在對消息解密之后, Bob 通知通知 Eve 消息具有這樣的特性：消息具有這樣的特性：m12345 1 (mod n). Eve 已知已知 n

17、; e; c, 但是不知道但是不知道 p; q;m. 但但Eve可以根據(jù)可以根據(jù)Bob 提示信息發(fā)現(xiàn)消息提示信息發(fā)現(xiàn)消息 m. 說明說明Eve是如何得到是如何得到 m的的. The Extended Euclidean AlgorithmExample 1: m = 65; n = 40Step 1: The (usual) Euclidean algorithm:(1) 65 = 1 40 + 25(2) 40 = 1 25 + 15(3) 25 = 1 15 + 10(4) 15 = 1 10 + 510 = 2 5Therefore: gcd(65; 40) = 5.Step 2: Us

18、ing the method of back-substitution:(4)5 =15 - 10(3) = 15 - (25 - 15) = 2 15 - 25(2) = 2(40 - 25) - 25 = 2 40 - 3 25(1) = 2 40 - 3(65 - 40) = 5 40 - 3 65Conclusion: 65(-3) + 40(5) = 5.對對RSA的攻擊：共模廣播攻擊的攻擊：共模廣播攻擊 在實(shí)現(xiàn)在實(shí)現(xiàn)RSA時(shí)，為方便起見，可能給每一用戶相同的模數(shù)時(shí)，為方便起見，可能給每一用戶相同的模數(shù)n，雖然加解密密鑰不同，然而這樣做是不行的。，雖然加解密密鑰不同，然而這樣做是不行

19、的。 設(shè)兩個(gè)用戶的公開鑰分別為設(shè)兩個(gè)用戶的公開鑰分別為e1和和e2，且，且e1和和e2互素（一般情互素（一般情況都成立），明文消息是況都成立），明文消息是m，密文分別是，密文分別是 c1me1(mod n) c2me2(mod n) 敵手截獲敵手截獲c1和和c2后，可按如下方法恢復(fù)后，可按如下方法恢復(fù)m。 用推廣的用推廣的Euclid算法求出滿足算法求出滿足 re1+se2=1 的兩個(gè)整數(shù)的兩個(gè)整數(shù)r和和s，其中一個(gè)為負(fù)，設(shè)為，其中一個(gè)為負(fù)，設(shè)為r。再次用推廣的。再次用推廣的Euclid算法求出算法求出c-11，由此得，由此得(c-11)-rcs2m(mod n)。例題例題user1n1,e1

20、=299,3user2n2,e2=299,5某用戶傳遞給二個(gè)用戶相同的消息某用戶傳遞給二個(gè)用戶相同的消息m, 密文分別為密文分別為129，205問：攻擊者是否可以據(jù)此得出明文問：攻擊者是否可以據(jù)此得出明文對對RSA的攻擊：低指數(shù)廣播攻擊的攻擊：低指數(shù)廣播攻擊假定將假定將RSA算法同時(shí)用于多個(gè)用戶（為討論方便，以算法同時(shí)用于多個(gè)用戶（為討論方便，以下假定下假定3個(gè)），然而每個(gè)用戶的加密指數(shù)（即公開鑰個(gè)），然而每個(gè)用戶的加密指數(shù)（即公開鑰）都很小。設(shè)）都很小。設(shè)3個(gè)用戶的模數(shù)分別為個(gè)用戶的模數(shù)分別為ni(i=1,2,3)，當(dāng)，當(dāng)ij時(shí)，時(shí)，gcd(ni,nj)=1，否則通過，否則通過gcd(ni,

21、nj)有可能得有可能得出出ni和和nj的分解。的分解。設(shè)明文消息是設(shè)明文消息是m，密文分別是，密文分別是c1m3(mod n1)c2m3(mod n2)c3m3(mod n3)由中國剩余定理可求出由中國剩余定理可求出m3(mod n1n2n3)。由于。由于m3n1n2n3，可直接由，可直接由m3開立方根得到開立方根得到m。例題例題user1n1,e1=319,3user2n2,e2=299,3user2n3,e3=323,3某用戶傳遞給三個(gè)用戶相同的消息某用戶傳遞給三個(gè)用戶相同的消息m, 密文分別為密文分別為80，235，121問：攻擊者是否可以據(jù)此得出明文問：攻擊者是否可以據(jù)此得出明文教科書

22、教科書 RSA 教科書教科書 RSA 加密加密: 公鑰公鑰: (N,e) 加密加密: C = Me (mod N) 私鑰私鑰: d 解密解密: Cd = M (mod N) (M ZN* )對教科書對教科書 RSA的一種攻擊的一種攻擊 Session-key K is 64 bits. View K 0,264Eavesdropper sees: C = Ke (mod N) . Suppose K = K1 K2 where K1, K2 234 . (prob. 20%)Then: C/K1e = K2e (mod N) Build table: C/1e, C/2e, C/3e, , C

23、/234e . time: 234For K2 = 0, 234 test if K2e is in table. time: 234 34 Attack time: 240 264WebBrowserWebServerCLIENT HELLOSERVER HELLO (e,N)dC=RSA(K)Randomsession-key K通用通用 RSA 加密加密 不要使用教科書不要使用教科書 RSA. 實(shí)際中的實(shí)際中的RSA :msgPreprocessingciphertextRSAPKCS1 V1.5 PKCS1 mode 2:(encryption)02random padFFmsg102

24、4 bits16 bits對對RSA的選擇密文攻擊的選擇密文攻擊原理原理 E(e,m1) E(e,m2)=E(e,m1 m2）PKCS1 V2.0 - OAEP New preprocessing function: OAEP (BR94). Thm: RSA is trap-door permutation OAEP is CCS when H,G are “random oracles”. In practice: use SHA-1 or MD5 for H and G.H+G+Plaintext to encrypt with RSArand.M01 00.0Check padon d

25、ecryption.Reject CT if invalid.0,1n-1Rabin密碼體制密碼體制 它不是以一一對應(yīng)的單向陷門函數(shù)為基礎(chǔ)，對同一它不是以一一對應(yīng)的單向陷門函數(shù)為基礎(chǔ)，對同一密文，可能有兩個(gè)以上對應(yīng)的明文密文，可能有兩個(gè)以上對應(yīng)的明文; 破譯該體制等價(jià)于對大整數(shù)的分解。破譯該體制等價(jià)于對大整數(shù)的分解。 RSA中選取的公開鑰中選取的公開鑰e滿足滿足1e(n)，且，且gcd(e,(n)=1。Rabin密碼體制則取密碼體制則取e=2。Rabin算法：算法：密鑰的產(chǎn)生密鑰的產(chǎn)生 隨機(jī)選擇兩個(gè)大素?cái)?shù)隨機(jī)選擇兩個(gè)大素?cái)?shù)p、q，滿足，滿足pq3 mod 4，即，即這兩個(gè)素?cái)?shù)形式為這兩個(gè)素?cái)?shù)形

26、式為4k+3；計(jì)算；計(jì)算n=pq。以。以n作為公作為公開鑰，開鑰，p、q作為秘密鑰。作為秘密鑰。Rabin算法：加密算法：加密cm2 mod n其中其中m是明文分組，是明文分組，c是對應(yīng)的密文分組。是對應(yīng)的密文分組。Rabin算法：解密算法：解密解密就是求解密就是求c模模n的平方根，即解的平方根，即解x2c mod nRabin算法：解密算法：解密由中國剩余定理知解該方程等價(jià)于解方程組由中國剩余定理知解該方程等價(jià)于解方程組由于由于pq3 mod 4，下面將看到，方程組的解可容易地求出，下面將看到，方程組的解可容易地求出，其中每個(gè)方程都有兩個(gè)解，即，其中每個(gè)方程都有兩個(gè)解，即xm mod p,x

27、-m mod pxm mod q,x-m mod q22modmodxcpxcqRabin算法：解密算法：解密經(jīng)過組合可得經(jīng)過組合可得4個(gè)同余方程組個(gè)同余方程組由中國剩余定理可解出每一方程組的解，共有由中國剩余定理可解出每一方程組的解，共有4個(gè)，即每一密個(gè)，即每一密文對應(yīng)的明文不惟一。為了有效地確定明文文對應(yīng)的明文不惟一。為了有效地確定明文,可在可在m中加入某中加入某些信息些信息,如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間如發(fā)送者的身份號(hào)、接收者的身份號(hào)、日期、時(shí)間等。等。mod ,mod ,mod ,mod ,mod ,mod ,mod ,mod ,xmpxmpxmqxmqxmpxmpxmqxmq Rabin算法：解密算法：解密當(dāng)當(dāng)pq3 mod 4，兩個(gè)方程，兩個(gè)方程x2c mod p,x2c mod q的平方根都可容易地求出。的