1、Chapter 9 公鑰密碼學(xué)與公鑰密碼學(xué)與RSA 2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院22022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院3公鑰密碼體制公鑰密碼體制n密碼學(xué)發(fā)展歷史中最偉大的一次革命密碼學(xué)發(fā)展歷史中最偉大的一次革命n采用兩個(gè)密鑰：一個(gè)公鑰，一個(gè)私鑰采用兩個(gè)密鑰：一個(gè)公鑰，一個(gè)私鑰n參與方不對(duì)等，所以是非對(duì)稱的；參與方不對(duì)等，所以是非對(duì)稱的；n基于數(shù)論中的結(jié)論基于數(shù)論中的結(jié)論n是私鑰密碼的補(bǔ)充而不是代替是私鑰密碼的補(bǔ)充而不是代替2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院4為什么需要公鑰密碼為什么需要公鑰密碼?n兩個(gè)考慮：兩個(gè)考慮：q密鑰分配密鑰分配 - KDCq數(shù)字簽名數(shù)字簽名n

2、公認(rèn)該發(fā)明屬于公認(rèn)該發(fā)明屬于Stanford Uni 的的Whitfield Diffie 和和 Martin Hellman ，于，于1976年。年。nNew Directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 nJames Ellis (UK CESG) 在在1970年曾提出此概念年曾提出此概念2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院5公鑰密碼體制公鑰密碼體制n公鑰公鑰/雙鑰雙鑰/非對(duì)稱非對(duì)稱 密碼都是指使用兩個(gè)密鑰密碼都是指使用兩個(gè)密鑰: q公鑰：公鑰：可以對(duì)任何人

3、公開的密鑰，用于加密消息可以對(duì)任何人公開的密鑰，用于加密消息或驗(yàn)證簽名。或驗(yàn)證簽名。 q私鑰：私鑰：只能由接收者私存，用于解密消息或簽名。只能由接收者私存，用于解密消息或簽名。n非對(duì)稱非對(duì)稱q用于加密消息或驗(yàn)證簽名的人不能進(jìn)行消息的加密或用于加密消息或驗(yàn)證簽名的人不能進(jìn)行消息的加密或消息的簽名。消息的簽名。2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院6公鑰密碼體制公鑰密碼體制2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院7公鑰密碼體制特點(diǎn)公鑰密碼體制特點(diǎn)n公鑰密碼算法依賴于公鑰密碼算法依賴于:q僅僅知道算法和加密密鑰，推導(dǎo)解密密鑰計(jì)算僅僅知道算法和加密密鑰，推導(dǎo)解密密鑰計(jì)算上是不可行的上是不可行的q

4、已知加解密密鑰時(shí)，進(jìn)行加解密運(yùn)算計(jì)算上是已知加解密密鑰時(shí)，進(jìn)行加解密運(yùn)算計(jì)算上是容易的容易的q兩個(gè)密鑰中的任何一個(gè)都可以用來加密，而另兩個(gè)密鑰中的任何一個(gè)都可以用來加密，而另一個(gè)用來解密。一個(gè)用來解密。2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院8單向陷門函數(shù)單向陷門函數(shù)n單向陷門函數(shù)：?jiǎn)蜗蛳蓍T函數(shù)：q若若k和和X已知，則容易計(jì)算已知，則容易計(jì)算 Y = fk(X).q若若k和和Y已知，則容易計(jì)算已知，則容易計(jì)算X = fk-1(Y).q若若Y已知但已知但k未知，則計(jì)算出未知，則計(jì)算出X = fk-1(Y)是不可行的是不可行的.n尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵尋找合適的單向陷門函

5、數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵n單向陷門函數(shù)舉例：?jiǎn)蜗蛳蓍T函數(shù)舉例：q離散對(duì)數(shù)離散對(duì)數(shù)q大整數(shù)分解大整數(shù)分解q背包問題背包問題2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院9公鑰密碼體制：保密性和認(rèn)證公鑰密碼體制：保密性和認(rèn)證2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院10公鑰算法分類公鑰算法分類nPublic-Key Distribution Schemes (PKDS) q用于交換秘密信息(依賴于雙方主體) q常用于對(duì)稱加密算法的密鑰nPublic Key Encryption (PKE) q用于加密任何消息 q任何人可以用公鑰加密消息 q私鑰的擁有者可以解密消息 q任何公鑰加密方案能夠用于密鑰分配

6、方案PKDS q許多公鑰加密方案也是數(shù)字簽名方案nSignature Schemes q用于生成對(duì)某消息的數(shù)字簽名q私鑰的擁有者生成數(shù)字簽名q任何人可以用公鑰驗(yàn)證簽名 2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院11公鑰密碼體制的應(yīng)用公鑰密碼體制的應(yīng)用n分為三類分為三類:q加密加密/解密解密 (提供保密性提供保密性)q數(shù)字簽名數(shù)字簽名 (提供認(rèn)證提供認(rèn)證)q密鑰交換密鑰交換 (會(huì)話密鑰會(huì)話密鑰)n一些算法可用于上述三類，而有些只適用一些算法可用于上述三類，而有些只適用用于其中一類或兩類。用于其中一類或兩類。2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院122022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院1

7、3公鑰密碼體制安全性分析公鑰密碼體制安全性分析n一樣存在窮舉攻擊一樣存在窮舉攻擊n但所使用的密鑰一般都非常大但所使用的密鑰一般都非常大 ( 512bits ) n安全性基于安全性基于容易容易（加解密）和（加解密）和困難困難（破譯）之間（破譯）之間巨大的差別巨大的差別n許多算法沒有得到證明是安全的。（包括許多算法沒有得到證明是安全的。（包括RSA） n需要采用一些特別大的數(shù)字需要采用一些特別大的數(shù)字n與私鑰密碼體制相比，速度慢。與私鑰密碼體制相比，速度慢。2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院149.2 RSAn1977由由MIT的的Rivest, Shamir 和和 Adleman發(fā)明發(fā)明

8、n已知的且被廣泛使用的公鑰密碼方案已知的且被廣泛使用的公鑰密碼方案n有限域中的乘方運(yùn)算有限域中的乘方運(yùn)算q乘方運(yùn)算需要乘方運(yùn)算需要 O(log n)3) 操作操作 (容易的容易的) n使用一些大的整數(shù)使用一些大的整數(shù) (例如例如. 1024 bits)n安全性基于大數(shù)的素因子分解的困難性安全性基于大數(shù)的素因子分解的困難性q素因子分解需要素因子分解需要 O(e log n log log n) 操作操作 (困難的困難的) 2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院15RSAn1977由由MIT的的Rivest, Shamir 和和 Adleman發(fā)明發(fā)明n已知的且被廣泛使用的公鑰密碼方案已知的且

9、被廣泛使用的公鑰密碼方案n有限域中的乘方運(yùn)算有限域中的乘方運(yùn)算q乘方運(yùn)算需要乘方運(yùn)算需要 O(log n)3) 操作操作 (容易的容易的) n使用一些大的整數(shù)使用一些大的整數(shù) (例如例如. 1024 bits)n安全性基于大數(shù)的素因子分解的困難性安全性基于大數(shù)的素因子分解的困難性q素因子分解需要素因子分解需要 O(e log n log log n) 操作操作 (困難的困難的) 2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院162022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院172022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院18RSA的工作原理的工作原理nEuler定理定理:qa(n) mod n 1 其中

10、其中(a, n) = 1nRSA中中:qn = pqq(n) = (p-1) (q-1) q仔細(xì)地選擇仔細(xì)地選擇 e 和和 d 使得使得 mod (n) 下，兩者互逆下，兩者互逆q因此存在某個(gè)整數(shù)因此存在某個(gè)整數(shù)k，使得，使得ed = 1 + k(n) 成立成立n所以所以 :Cd = Med = M1+k.(n) = M1 (M(n)k M1 (1)k = M1 = M mod n 2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院19冪冪 運(yùn)運(yùn) 算算n可以用平方和乘法運(yùn)算可以用平方和乘法運(yùn)算nN 次方，只需要次方，只需要 O(log2 n) 次乘法運(yùn)算次乘法運(yùn)算q如如. 75 = 7471 = 37

11、 = 10 mod 11q如如. 3129 = 312831 = 53 = 4 mod 112022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院20加密的效率加密的效率n加密要計(jì)算加密要計(jì)算 e 次方冪次方冪n若若 e 較小較小, 計(jì)算將很快計(jì)算將很快q通常選擇通常選擇 e = 65537 (216-1)q或選擇或選擇 e = 3 或或 e = 17n但若但若 e太小太小 (如如 e = 3)將易受到攻擊將易受到攻擊q用中國(guó)剩余定理用中國(guó)剩余定理n必須確保必須確保(e, (n) = 12022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院21解密的效率解密的效率n解密計(jì)算解密計(jì)算d次方冪次方冪q看起來很大，否則不安

12、全看起來很大，否則不安全n用中國(guó)剩余定理分別計(jì)算用中國(guó)剩余定理分別計(jì)算mod p和和mod q，則可以得到所希望的答案則可以得到所希望的答案q比直接快約比直接快約4倍倍2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院22RSA 密鑰的產(chǎn)生密鑰的產(chǎn)生nRSA的用戶必須的用戶必須:q隨機(jī)確定兩個(gè)素?cái)?shù)隨機(jī)確定兩個(gè)素?cái)?shù) p, q q選擇選擇e或或d，并求出另一個(gè)，并求出另一個(gè)n素?cái)?shù)素?cái)?shù) p, q 一定不能從一定不能從n = pq輕易得到輕易得到q意味著數(shù)要足夠大意味著數(shù)要足夠大q典型地用猜測(cè)或可能性測(cè)試典型地用猜測(cè)或可能性測(cè)試n指數(shù)指數(shù)e, d 是互逆的是互逆的2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院23

13、RSA 安全性分析安全性分析n攻擊攻擊RSA可能的方法有可能的方法有:q窮舉搜索窮舉搜索 (對(duì)于給定的數(shù)字規(guī)模是不可行的對(duì)于給定的數(shù)字規(guī)模是不可行的)q數(shù)學(xué)攻擊數(shù)學(xué)攻擊 (基于計(jì)算基于計(jì)算(n)的困難性的困難性, 模模n的因子分解的因子分解的困難性的困難性)q計(jì)時(shí)攻擊計(jì)時(shí)攻擊 (基于解密的運(yùn)行情況基于解密的運(yùn)行情況)q選擇密文攻擊選擇密文攻擊(RSA的已知特性的已知特性)2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院24RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)系統(tǒng)安全性與系統(tǒng)的參數(shù)nRSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系，系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系，X.931標(biāo)準(zhǔn)標(biāo)準(zhǔn), ISO/IEC 14752對(duì)此提

14、出以下幾點(diǎn)：對(duì)此提出以下幾點(diǎn)：q如果公鑰如果公鑰e是奇數(shù)，是奇數(shù)，e應(yīng)與應(yīng)與p-1，q-1互質(zhì)；互質(zhì)；q如果公鑰如果公鑰e是偶數(shù)，是偶數(shù)，e必須與必須與(p-1)/2, (q-1)/2互質(zhì)，且互質(zhì)，且 pq mod 8不成立；不成立；q模數(shù)的長(zhǎng)應(yīng)該為模數(shù)的長(zhǎng)應(yīng)該為1024 + 256x，x = 0, 1 ；q質(zhì)數(shù)質(zhì)數(shù)p，q 應(yīng)通過質(zhì)數(shù)檢測(cè)應(yīng)通過質(zhì)數(shù)檢測(cè)qp-1, q-1, p+1, q+1應(yīng)有大質(zhì)數(shù)因子；應(yīng)有大質(zhì)數(shù)因子；qgcd(p-1, q-1)應(yīng)該小；應(yīng)該??；qp/q不應(yīng)靠近兩個(gè)小整數(shù)比值，且；不應(yīng)靠近兩個(gè)小整數(shù)比值，且；q|p-q|應(yīng)有大質(zhì)數(shù)因子。應(yīng)有大質(zhì)數(shù)因子。 2022-6-9西安電

15、子科技大學(xué)計(jì)算機(jī)學(xué)院25分解因子問題分解因子問題n數(shù)學(xué)攻擊的三種形式數(shù)學(xué)攻擊的三種形式:q分解分解 n = pq, 計(jì)算計(jì)算(n) 從而得到從而得到 dq直接確定直接確定 (n) 并計(jì)算并計(jì)算 dq直接尋找直接尋找d n對(duì)于因子分解問題對(duì)于因子分解問題q很多年來進(jìn)展很慢很多年來進(jìn)展很慢n用用“Lattice Sieve” (LS),算法，算法，最好的是分解了最好的是分解了200位十進(jìn)位十進(jìn)制數(shù)制數(shù)(663 bit) q最大的改進(jìn)就是對(duì)改進(jìn)算法的改良最大的改進(jìn)就是對(duì)改進(jìn)算法的改良n QS to GHFS to LSq當(dāng)前假設(shè)當(dāng)前假設(shè)1024-2048bit RSA 是安全的是安全的n確保確保 p

16、, q 有相似的大小并滿足其它約束有相似的大小并滿足其它約束2022-6-9西安電子科技大學(xué)計(jì)算機(jī)學(xué)院26計(jì)計(jì) 時(shí)時(shí) 攻攻 擊擊n20世紀(jì)世紀(jì)90年代由年代由Paul Kocher提出提出n探測(cè)操作中的時(shí)間變化探測(cè)操作中的時(shí)間變化qeg. multiplying by small vs large number qor IFs varying which instructions executedn基于所耗時(shí)間的大小，對(duì)操作數(shù)的大小進(jìn)行猜測(cè)基于所耗時(shí)間的大小，對(duì)操作數(shù)的大小進(jìn)行猜測(cè)nRSA exploits time taken in exponentiationnCountermeasures(解決辦法解決辦法)quse constant exponentiation time（不變的（不變的 冪運(yùn)算時(shí)間）冪運(yùn)算時(shí)間）qad