非對稱加密系統(tǒng)-RSA

非對稱加密系統(tǒng)-RSA資訊工程系102級-張耀仁

wingOutline_1加密方式分類RSA歷史和優(yōu)缺點RSA流程及運(yùn)作原理RSA詳述流程加密方式分類加密方式分類-對稱式複習(xí)對稱式加密體系(SymmetricKey)：加密金鑰和解密金鑰是相同的。為了安全性，密鑰要定期的改變。對稱演算法速度快，所以在處理大量資料的時候被廣泛使用，其關(guān)鍵是保證密鑰的安全。典型的演算法：DES、3DES、IDEA、AES、RC系列。加密方式分類-非對稱式非對稱式金鑰(AsymmetricKey)體系：2把key(鑰匙)-publicandprivatePrivatekey(自己擁有)，publickey(發(fā)佈)兩把key有對應(yīng)的關(guān)係，用公鑰加密的資料只有用私鑰才能解開。自己加密的資料用privatekey簽署，擁有publickey的人就使用它來驗證有效性加密方式分類-非對稱式非對稱式金鑰(AsymmetricKey)體系：其效率低於對稱密鑰體系(慢啊~)典型的演算法：RSA、背包密碼，EllipticCurve等等。最有影響的公鑰加密演算法是RSA足夠位元數(shù)的RSA能夠抵抗到目前為止已知所有密碼攻擊。Outline_1加密方式分類RSA歷史和優(yōu)缺點RSA流程及運(yùn)作原理RSA詳述流程RSA歷史1973年，在英國通訊總部工作的數(shù)學(xué)家CliffordCocks在一個內(nèi)部文件中提出了一個相應(yīng)的演算法，但他的發(fā)現(xiàn)被列入機(jī)密，一直到1997年才被發(fā)表。RSA算取自于它的創(chuàng)始人的名字：於1977年，美國麻省理工學(xué)院Rivest、Shamir、Adelman3位教授所發(fā)表。RSA基於數(shù)學(xué)難題，具有大數(shù)因數(shù)分解。RSA使用兩個密鑰：PublicKey(PK)與PrivateKey(SK)在電子商業(yè)中RSA被廣泛使用(1983年MIT在美國為RSA演算法申請了專利。專利2000年9月21日失效。由於在申請專利前就已經(jīng)被發(fā)表了，世界大多數(shù)地區(qū)不承認(rèn)這個專利權(quán)!)RSA缺點 question:之前介紹的DES等算法跟RSA推算出的年代期時差不多，為什麼沒被普遍採用呢?Answer:RSA需要大數(shù)運(yùn)算，計算量大，1977年電腦執(zhí)行RSA的效率遠(yuǎn)低於DES早期DES用IC晶片作加解密，用硬體做設(shè)計與演算，而RSA若用硬體做計算成本高出許多RSA優(yōu)點如DES、AES等對稱式均一個缺點:須將解密的金鑰告訴對方！傳輸密碼始終是一大問題，總不能將金鑰再加密一次吧(這樣還是要再傳加密金鑰的金鑰！)RSA優(yōu)點雖然可以透過KDC(keydistributioncenter)解決，可是必須完全信賴KDC才行非對稱式的一大優(yōu)勢:不用傳解密的密碼！因未解密金鑰(privatekey)是自己獨(dú)有的！In

cryptography,a

keydistributioncenter

(KDC)ispartofa

cryptosystem

intendedtoreducetherisksinherentinexchanging

keys.KDCsoftenoperateinsystemswithinwhichsomeusersmayhavepermissiontousecertainservicesatsometimesandnotatothers.Outline_1加密方式分類RSA歷史和優(yōu)缺點RSA流程及運(yùn)作原理RSA詳述流程13RSA流程14假設(shè)資料(Data)要由A傳至B：由B用決定固定公式產(chǎn)生兩個key(之後詳述)一個為私鑰PrivateKey，只留在B裡。一個為公開金鑰PublicKey將這個PublicKey透過網(wǎng)路丟給A:這個PublicKey的特性是幾乎不可能反演算出PrivateKeyRSA-運(yùn)作原理3.A將明文用PublicKey加密：這個編碼密文一定得用PrivateKey才解得開。然後A將密文透過網(wǎng)路傳給B。4.B用PrivateKey將資料解碼。RSA-運(yùn)作原理如有第三者竊聽資料時：

只能得到B傳給A的PublicKey和A用PublicKey編碼後的密文。

沒有PrivateKey，第三者無法解碼，所以RSA確實能防止第三者的竊聽。Outline_1加密方式分類RSA歷史和優(yōu)缺點RSA流程及運(yùn)作原理RSA詳述流程RSA詳述-產(chǎn)生兩把key公鑰是兩個正整數(shù)(E,N)私鑰是一個正整數(shù)(D)(有些資料寫(D,N))使用者秘密挑選兩個很大的質(zhì)數(shù)P,Q(例如150位數(shù))然後相乘N=PxQ

,N約300位數(shù)(十進(jìn)制)根據(jù)歐拉函數(shù)，<=N且與N互質(zhì)的整數(shù)個數(shù)為(P-1)X(Q-1)再挑一個E<=(P-1)X(Q-1)，且GCD(E,(P-1)X(Q-1))=1(即互質(zhì))算出D，滿足DXEmod((P-1)X(Q-1))=1(D<=(P-1)X(Q-1))記得將N,Q銷毀

(後面有數(shù)學(xué)補(bǔ)充!!!!!)RSA詳述-兩把key舉例假設(shè)P=7,Q=17,挑E=5現(xiàn)在N=7*17=119,

(P-1)=5

,

(Q-1)=16

滿足GCD(E,(P-1)*(Q-1))=GCD(5,6*16)=1所以公鑰(E,N)=(5,119)找一個D滿足D*5mod96=1可用輾轉(zhuǎn)相除法直接算出D=77(77*5=385,385

mod96=1)所以司鑰D=776*16RSA詳述-加解密公鑰(E,N)，私鑰(D)，明文:M，密文:C(當(dāng)然明文要先轉(zhuǎn)為數(shù)字n)(後面補(bǔ)充同餘≡)加密公式C=M^EmodN或解密公式M=C^DmodN或假設(shè)要傳送訊息M，而RSA使用前題是M<N，所以如果M長度很長可以切成數(shù)段加密，EX:8-bits一段加密時把明文分成塊，塊的大小可變，但不超過密鑰的長度。RSA把明文塊轉(zhuǎn)化為與密鑰長度相同的密文補(bǔ)充數(shù)學(xué)-同餘兩個整數(shù)a，b，若它們除以整數(shù)m所得的餘數(shù)相等，則稱a，b對於模m同餘記作RSA系統(tǒng)詳述安全原理:兩個大樹相乘容易，分解難金鑰產(chǎn)生:使用者秘密挑選兩個很大的質(zhì)數(shù)P,Q(例如150位數(shù))選一個E滿足:GCD(E,(P-1)X(Q-1))=1

公鑰(publickey):E與N(N=PxQ)用輾轉(zhuǎn)相除法，算出D滿足DXEmod((P-1)X(Q-1))=1

私鑰(privatekey):D加密:發(fā)文者收到publickey，計算密文C

C=M^EmodN解密:收文者用自己的privatekey，計算明文M

M=C^DmodN補(bǔ)充數(shù)學(xué)-條列歐拉函數(shù):不大於N且與N互質(zhì)的整數(shù)個數(shù)

為(p-1)(q-1)輾轉(zhuǎn)相除法:計算出密鑰D滿足

D

X

Emod((P-1)X(Q-1))=1

費(fèi)馬小定理:證明加解密這邊補(bǔ)充了一些數(shù)學(xué)，為避免打斷RSA介紹，數(shù)學(xué)的詳細(xì)內(nèi)容都在放最後面Outline_2攻擊RSARSA結(jié)論RSA應(yīng)用補(bǔ)充數(shù)學(xué)RSA系統(tǒng)-安全度公鑰和私鑰都是兩個超大質(zhì)數(shù)(P,Q)的函數(shù)從一個密鑰和密文推斷出明文的難度等同於分解兩個大質(zhì)數(shù)的積N偷聽者無法直接獲得密鑰D。要獲得D，可將N分解為P和Q，這樣就可以藉由D

×

E

mod(p-1)(q-1))=1並解出D，導(dǎo)出明文。至今沒有找到一個多項式時間的演算法來分解一個大整數(shù)的因子，也沒有人能證明這種演算法不存在。至今沒有人能夠證明對N進(jìn)行因數(shù)分解是唯一的從c導(dǎo)出明文的方法，但也沒有公開且更簡單的方法。攻擊RSA暴力攻擊(Bruteforce)逐一尋找可能的P,Q，因為P,Q大小差不多都是根號N。EX:N為1024-bits，可逐一嘗試512-bits的所有質(zhì)數(shù)，若能用N除盡就是P,也能找出Q！然後就破解啦！攻擊RSA數(shù)學(xué)攻擊法(mathematicalattacks)攻擊方式有很多種，例如尋找大數(shù)分解法快速計算出N，或當(dāng)私鑰D<N^0.292時，研究人員可用其他方法破解RSA比爆力快！攻擊RSA計時攻擊(timingattack)利用解密時間差異來猜測金鑰在2進(jìn)制中，bit=1所花的運(yùn)算時間比bit=0多若1多，則計算時間慢；若1少，則計算時間快若能得到多組訊息與其加密時間，就會有機(jī)會可以反推出私鑰的內(nèi)容。攻擊RSA-結(jié)論目前都可以有效預(yù)防只要P,Q夠大(150位)，使得N足夠大(300位)，RSA系統(tǒng)便可安全使用但是未來有更多的挑戰(zhàn)攻擊RSA-結(jié)論-未來挑戰(zhàn)1994年P(guān)eterShor證明一臺量子計算機(jī)可以在多項式時間內(nèi)進(jìn)行因數(shù)分解。假如量子計算機(jī)未來成為可行的技術(shù)，Shor的演算法可以淘汰RSA和相關(guān)的衍生演算法。（依賴分解大整數(shù)困難性的加密演算法）假如未來找到一種有效的分解大整數(shù)的演算法的話，或假如量子計算機(jī)可行的話那麼就會展開一場密碼長度的競爭。但那時，從原理上來說RSA是不可靠的。大數(shù)分解懸賞RSAsecurity公司懸賞大數(shù)分解N=P*Q目前最大的數(shù)為RSA-2048

最大懸賞金額US$200,000RSA公司只是想宣導(dǎo)大數(shù)分解是很困難的！Outline_2攻擊RSARSA結(jié)論RSA應(yīng)用補(bǔ)充數(shù)學(xué)對極大整數(shù)做因數(shù)分解的難度決定了RSA演算法的可靠性。對一極大整數(shù)做因數(shù)分解愈困難，RSA演算法愈可靠。如果找到一種快速因數(shù)分解的演算法的話，RSA加密的可靠性就會極度下降。(找到如此演算法的可能性非常小)RSA-結(jié)論今天只有短的RSA金鑰才可能被強(qiáng)力解破。針對RSA最流行的攻擊一般是基於大數(shù)因數(shù)分解。1999年，RSA-155（512bits）被成功分解2002年，RSA-158也被成功因數(shù)分解。2009年12月12日，編號為RSA-768

(768bits,232digits）數(shù)也被成功分解。這一事件威脅了現(xiàn)通行的1024-bit密鑰的安全性，普遍認(rèn)為用戶應(yīng)儘快升級到2048-bit或以上。RSA-結(jié)論只要金鑰長度足夠長，加密的資訊實際上是不能被解破的。1997年後開發(fā)的系統(tǒng)，用戶應(yīng)使用1024位密鑰，證書認(rèn)證機(jī)構(gòu)應(yīng)用2048位或以上。但在分布式計算技術(shù)和量子計算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)。RSA-結(jié)論Outline_2攻擊RSARSA結(jié)論RSA應(yīng)用補(bǔ)充數(shù)學(xué)RSA應(yīng)用-SSLRSA應(yīng)用-SSL由Netscape所發(fā)展，是介於ApplicationProtocol和TCP/IP間一個公開的、公用的資料安全性之通訊協(xié)定。為網(wǎng)路通信提供安全及數(shù)據(jù)完整性的一種安全協(xié)議，在傳輸層對網(wǎng)路連接進(jìn)行加密。可動態(tài)選擇加密的演算法（例如RSA）功能有傳輸資料加密、連結(jié)伺服器之認(rèn)證、確保傳送信息之完整性等。RSA應(yīng)用-SSL左圖為一般的TCP/IP架構(gòu)，右圖加入了一層SSL。由應(yīng)用層送出的資訊經(jīng)SSL加密後，再送到傳輸層傳送接收端接到傳輸層的封包後，經(jīng)由SSL解密後，再傳到應(yīng)用層RSA應(yīng)用-數(shù)位簽章非對稱式金鑰系統(tǒng)數(shù)位簽章的功能確認(rèn)性不可否認(rèn)性RSA應(yīng)用-數(shù)位簽章運(yùn)作程序：先使用hashfunction我們用privatekey簽署簽章碼

對方用publickey檢視簽章碼Outline_2攻擊RSARSA結(jié)論RSA應(yīng)用補(bǔ)充數(shù)學(xué)補(bǔ)充數(shù)學(xué)-歐拉函數(shù)不大於N且與N互質(zhì)的整數(shù)個數(shù)為(p-1)(q-1)為什麼??歐拉函數(shù)φ(n)是小於或等於n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。又稱φ函數(shù)、歐拉商數(shù)φ(1)=1Ex:所以φ(N)=φ(P*Q)=(P^1-1)(P-1)*(Q^1-1)(Q-1)

=1*(P-1)*1*(Q-1)補(bǔ)充數(shù)學(xué)-輾轉(zhuǎn)相除法又稱歐幾里得演算法由於每一步的餘數(shù)都在減小並且不為負(fù)數(shù)，必然存在第N步時rN等於0，使演算法終止，rN?1

就是a和b的最大公約數(shù)。其中N不可能無窮大，因為在r0和0之間只有有限個自然數(shù)。a

=

q0

b

+

r0

b