網(wǎng)絡(luò)安全-09：公鑰密碼學(xué)RSA

Chapter9

公鑰密碼學(xué)RSA

《密碼編碼學(xué)與網(wǎng)絡(luò)安全》

2023/2/32為什么需要公鑰密碼?

1）對(duì)稱密碼體制的密鑰分配問題：通信雙方要進(jìn)行加密通信，需要通過秘密的安全信道協(xié)商加密密鑰，而這種安全信道可能很難實(shí)現(xiàn)；2）對(duì)稱密碼體制的密鑰管理問題：在有多個(gè)用戶的網(wǎng)絡(luò)中，任何兩個(gè)用戶之間都需要有共享的秘密鑰，當(dāng)網(wǎng)絡(luò)中的用戶n很大時(shí)，需要管理的密鑰數(shù)目是非常大。3）對(duì)稱密碼體制沒有簽名功能：當(dāng)主體A收到主體B的電子文擋（電子數(shù)據(jù)）時(shí)，無(wú)法向第三方證明此電子文檔確實(shí)來(lái)源于B。2023/2/33公鑰密碼體制密碼學(xué)發(fā)展歷史中最偉大的一次革命公認(rèn)該發(fā)明屬于StanfordUni

的WhitfieldDiffie

和

MartinHellman，于1976年。"NewDirectionsinCryptography",IEEETrans.InformationTheory,IT-22,pp644-654,Nov1976JamesEllis(UKCESG)在1970年曾提出此概念基于數(shù)論中的結(jié)論公鑰密碼體制公鑰/雙鑰/非對(duì)稱密碼都是指使用兩個(gè)密鑰:公鑰：可以對(duì)任何人公開的密鑰，用于加密消息或驗(yàn)證簽名。

私鑰：只能由接收者私存，用于解密消息或簽名。非對(duì)稱用于加密消息或驗(yàn)證簽名的密鑰不能進(jìn)行解密消息的或消息的簽名。2023/2/352023/2/36公鑰密碼體制的應(yīng)用分為三類:加密/解密

(提供保密性)數(shù)字簽名(提供認(rèn)證)密鑰交換

(會(huì)話密鑰)一些算法可用于上述三類，而有些只適用用于其中一類或兩類。2023/2/37DSS：美國(guó)數(shù)字簽名標(biāo)準(zhǔn)2023/2/38公鑰密碼體制的應(yīng)用是私鑰密碼的補(bǔ)充而不是代替三種誤解：比傳統(tǒng)密碼更安全；傳統(tǒng)密碼已過時(shí)；公鑰密碼分配非常簡(jiǎn)單。2023/2/39公鑰密碼體制的應(yīng)用：保密性2023/2/310公鑰密碼體制的應(yīng)用：認(rèn)證2023/2/311公鑰密碼體制的應(yīng)用：保密性和認(rèn)證2023/2/312公鑰密碼的要求公私鑰對(duì)產(chǎn)生在計(jì)算上容易；加密在計(jì)算上容易；解密在計(jì)算上容易；已知公鑰，求私鑰在計(jì)算上不可行；已知公鑰和密文，恢復(fù)明文計(jì)算上不可性。加密和解密函數(shù)的順序可以交換（附加條件）2023/2/313單向陷門函數(shù)單向陷門函數(shù)：若k和X已知，則容易計(jì)算Y=fk(X).若k和Y已知，則容易計(jì)算X=fk-1(Y).若Y已知但k未知，則計(jì)算出X=fk-1(Y)是不可行的.尋找合適的單向陷門函數(shù)是公鑰密碼體制應(yīng)用的關(guān)鍵單向陷門函數(shù)舉例：離散對(duì)數(shù)大整數(shù)分解2023/2/314公鑰密碼體制安全性分析一樣存在窮舉攻擊從安全性考慮，使用的密鑰一般都非常大(>512bits)為了便于實(shí)現(xiàn)加解密，密鑰又必須足夠短。公鑰密碼目前僅限與密鑰管理和簽名中。另外一種攻擊方法：從給定的公鑰計(jì)算出私鑰的方法。到目前為止，還未在數(shù)學(xué)上證明對(duì)一特定公鑰算法這種攻擊是不可行的。（包括RSA）公鑰體制特有的攻擊窮舉消息攻擊

2023/2/315§9.2RSA1977由MIT的Rivest,Shamir和

Adleman發(fā)明已知的且被廣泛使用的公鑰密碼方案有限域中的乘方運(yùn)算乘方運(yùn)算需要

O((logn)3)操作(容易的)使用一些大的整數(shù)

(例如.1024bits)安全性基于大數(shù)的素因子分解的困難性素因子分解需要O(e

lognloglogn)操作(困難的)2023/2/3162023/2/3172023/2/318RSA密鑰的建立每一個(gè)用戶通過以下方法產(chǎn)生一個(gè)公鑰/私鑰對(duì):隨機(jī)地選擇兩個(gè)大的素?cái)?shù)p,q計(jì)算方案中的模數(shù)n=p.q

?(n)=(p-1)(q-1)隨機(jī)地選擇一個(gè)加密密鑰e滿足1<e<?(n),gcd(e,?(n))=1求解下面的方程，以得到解密密鑰de.d≡1mod?(n)and0≤d≤n公開公鑰:PU={e,n}保密私鑰:PR={d,n}2023/2/319RSA的使用為了加密消息M，發(fā)送方:獲得接收方的公鑰PU={e,n}計(jì)算:C=Memodn,其中0≤M<n為了解密密文C，接收者:使用自己的私鑰PR={d,n}計(jì)算:M=Cdmodn消息M一定要比模數(shù)n小(如果需要的話，可以進(jìn)行分組)2023/2/320RSA的工作原理Euler定理:a?(n)modn≡1其中(a,n)=1RSA中:n=p.q?(n)=(p-1)(q-1)仔細(xì)地選擇e和d使得mod?(n)下，兩者互逆因此存在某個(gè)整數(shù)k，使得e.d=1+k.?(n)成立所以:

Cd=Me.d

=M1+k.?(n)=M1.(M?(n))k

≡M1.(1)k=M1=Mmodn2023/2/321RSA舉例–密鑰的建立選擇素?cái)?shù):p=17&q=11計(jì)算n=pq=17x11=187計(jì)算

?(n)=(p–1)(q-1)=16x10=160選擇e:

gcd(e,160)=1;選擇e=7確定d:de=1mod160且

d<160

d=23因?yàn)?3x7=161=10x160+1公鑰

PU={7,187}私鑰

PR={23,187}2023/2/322RSA舉例–加密/加密明文消息M=88(注意88<187)加密:C=887mod187≡11解密:M=1123mod187≡882023/2/323冪運(yùn)算可以用平方和乘法運(yùn)算N次方，只需要O(log2n)次乘法運(yùn)算如.75=74.71=3.7=10mod11如.3129=3128.31=5.3=4mod112023/2/324冪運(yùn)算longPowerMod(inta,intb,intk){longtmp=a;longret=1;while(b){if(b&1)ret=ret*tmp%k;

tmp=tmp*tmp%k;b>>=1;}returnret;}2023/2/3252023/2/326加密的效率加密要計(jì)算e次方冪若e較小,計(jì)算將很快通常選擇

e=65537(216+1)或選擇

e=3或

e=17但若e太小

(如

e=3)將易受到攻擊用中國(guó)剩余定理解決方法：M隨機(jī)填充一個(gè)唯一的偽隨機(jī)比特串必須確保gcd(e,?(n))=12023/2/327解密的效率解密計(jì)算d次方冪d的值太小容易遭受窮舉攻擊和其他形式的攻擊。用中國(guó)剩余定理分別計(jì)算modp和modq，則可以得到所希望的答案比直接快約4倍只有知道p和q及私鑰的接收者可以直接采用這個(gè)技術(shù)進(jìn)行計(jì)算2023/2/328RSA密鑰的產(chǎn)生RSA的用戶必須:隨機(jī)確定兩個(gè)素?cái)?shù)p,q選擇e或d，并求出另一個(gè)素?cái)?shù)

p,q一定不能從n=p.q輕易得到意味著數(shù)要足夠大典型地用猜測(cè)或可能性測(cè)試（Miller-Rabin）指數(shù)e,d是互逆的（歐幾里得擴(kuò)展算法）2023/2/329RSA安全性分析攻擊RSA可能的方法有:窮舉搜索

(對(duì)于給定的數(shù)字規(guī)模是不可行的)數(shù)學(xué)攻擊(基于計(jì)算?(n)的困難性,模n的因子分解的困難性)計(jì)時(shí)攻擊

(基于解密的運(yùn)行情況)選擇密文攻擊(RSA的已知特性)2023/2/330分解因子問題數(shù)學(xué)攻擊的三種形式:分解

n=p.q,計(jì)算?(n)從而得到d直接確定

?(n)

并計(jì)算

d（等價(jià)于因子分解n）直接尋找d（至少和因子分解問題一樣費(fèi)時(shí)）對(duì)于因子分解問題很多年來(lái)進(jìn)展很慢用“LatticeSieve”(LS),算法，最好的是分解了200位十進(jìn)制數(shù)(663bit)最大的改進(jìn)就是對(duì)改進(jìn)算法的改良

QStoGHFStoLS當(dāng)前假設(shè)1024-2048bitRSA是安全的確保

p,q有相似的大小并滿足其它約束2023/2/331MIPS：一臺(tái)每秒執(zhí)行百萬(wàn)條指令的處理器運(yùn)行1年1GHz的奔騰機(jī)約等于一臺(tái)250MIPs2023/2/332RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)RSA系統(tǒng)安全性與系統(tǒng)的參數(shù)有很大關(guān)系，X.931標(biāo)準(zhǔn),ISO/IEC14752對(duì)此提出以下幾點(diǎn)：p和q的長(zhǎng)度應(yīng)僅差幾位。（p-1）和（q-1）都應(yīng)有大的素因子；gcd(p-1,q-1)應(yīng)該?。?023/2/333計(jì)時(shí)攻擊20世紀(jì)90年代由PaulKocher提出類似于竊賊通過觀察他人轉(zhuǎn)動(dòng)保險(xiǎn)柜撥號(hào)盤的時(shí)間長(zhǎng)短來(lái)猜測(cè)密碼。探測(cè)操作中的時(shí)間變化eg.multiplyingbysmallvslargenumber基于所耗時(shí)間的大小，對(duì)操作數(shù)的大小進(jìn)行猜測(cè)Countermeasures(解決辦法)useconstantexponentiationtime（不變的冪運(yùn)算時(shí)間）addrandomdelays（隨機(jī)時(shí)延）blind