密碼學(xué)基礎(chǔ) 課件 第5章　公鑰密碼與RSA

公鑰密碼學(xué)與RSA6學(xué)時對稱密碼的弱點(diǎn)及公鑰密碼的原理MH背包公鑰密碼Diffie-Hellman密鑰交換RSA密碼主要內(nèi)容密鑰量大密鑰管理困難：傳遞、換發(fā)、保存無法實現(xiàn)網(wǎng)絡(luò)中的簽名、認(rèn)證等應(yīng)用對稱密碼的弱點(diǎn)第一節(jié)公鑰密碼的原理密鑰量大對稱密碼的弱點(diǎn)設(shè)系統(tǒng)中共有n個用戶，兩兩進(jìn)行保密通信，總共需要多少個密鑰？當(dāng)n=5時，C（5，2）=10當(dāng)n=1000時，C（1000，2）=499500密鑰量大對稱密碼的弱點(diǎn)設(shè)系統(tǒng)中共有n個用戶，兩兩進(jìn)行保密通信，每個用戶有多少個密鑰？n-1個密鑰管理困難對稱密碼的弱點(diǎn)對稱密碼的弱點(diǎn)無法適應(yīng)網(wǎng)絡(luò)應(yīng)用數(shù)字簽名身份認(rèn)證消息認(rèn)證公鑰密碼的原理基本原理使用兩個不同的密鑰，一個用于加密，一個用于解密用于加密的密鑰Ek可以公開，用于解密的密鑰Dk保密Ek與Dk之間有聯(lián)系，但不能由Ek很容易地算出Dk公鑰密碼的原理加密與解密公鑰密碼的原理c=Ek(m)m=Dk(c)公鑰密碼的優(yōu)點(diǎn)密鑰數(shù)量大大減少密鑰管理方便公鑰密碼的原理公鑰密碼的安全性公鑰密碼的原理計算復(fù)雜性理論公鑰密碼的原理如何構(gòu)造陷門單向函數(shù)：利用困難問題背包問題離散對數(shù)問題整數(shù)分解問題橢圓曲線離散對數(shù)問題公鑰密碼的原理典型公鑰密碼背包密碼RSA密碼Rabin密碼ElGamal密碼橢圓曲線密碼背包密碼1978年，Merkle和Hellman提出了基于背包問題的公鑰密碼體制。如何解決背包問題：窮舉法背包問題當(dāng)物品個數(shù)為100時，有2100≈1.27×1030種可能性。把全世界所有的5億臺計算機(jī)全部聯(lián)網(wǎng)來求解這個問題，需要1000萬年！

背包密碼的安全性破譯方法： Shamir方法 L3格基歸約方法：由AKLenstra,HWLenstra&LLovasz提出 Lagarias-Odlyzko-Brickell的方法Diffie-Hellman密鑰交換功能：在沒有秘密信道的情況下，讓兩個用戶共享一個秘密密鑰理論基礎(chǔ)：離散對數(shù)問題方法：利用用戶的公鑰和私鑰Diffie-Hellman密鑰交換計算Diffie-Hellman問題（CDH問題）：已知ga和gb，計算gab如果CDH問題是容易的，則gab可以由p,g,ga,gb計算得到。背景數(shù)學(xué)基礎(chǔ)加密解密過程安全性及應(yīng)用第二節(jié)RSA密碼復(fù)習(xí)：歐拉定理

如果a,n互素，則有a

Ф(n)≡1modn設(shè)n=pq,p,q均為素數(shù)，且a,n互素，則Ф(n)=(p-1)(q-1)aФ(n)=a

(p-1)(q-1)≡1modn

第二節(jié)RSA密碼

選擇p,qp,q均為素數(shù)且p≠q

計算n=pq

計算Ф(n)=(p-1)(q-1)

選擇e1<e<Ф(n)且gcd(e,Ф(n))=1

計算dd≡e-1modФ(n)

公開n,e

保密d系統(tǒng)構(gòu)造對明文m=374加密計算c≡memodn≡37431mod2173=446解密：計算cd≡446671mod2173=374RSA：Example選擇p=53,q=41,n=pq=2173,