現(xiàn)代密碼學(xué)第七講：公鑰密碼學(xué)2

《現(xiàn)代密碼學(xué)第七講：公鑰密碼學(xué)2》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、1公鑰密碼（二）《現(xiàn)代密碼學(xué)》第七章上節(jié)內(nèi)容回顧公鑰密碼體制的提出及分類公鑰密碼體制的基本概念單向陷門函數(shù)的概念設(shè)計公鑰加密算法--背包密碼體制3本節(jié)主要內(nèi)容RSA算法及其分析ElGmal算法橢圓曲線密碼體制其它公鑰密碼算法4RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPubl

2、icKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb1978RSA算法51.密鑰的產(chǎn)生①選兩個安全的大素數(shù)p和q。②計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1

3、數(shù)是否為素數(shù)2以往素檢測的算法都是概率性的，即存在一定的錯誤概率；32003年，印度人發(fā)表文章“PrimesisinP”，證明了素判定問題是一個多項式時間問題。1）輾轉(zhuǎn)相除法2）利用歐拉定理求e^{φ(φ(n))}-1思考：分析兩種計算方法的效率62.加密加密時首先將明文比特串分組，使得每個分組對應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n。然后對每個明文分組m，作加密運(yùn)算：c≡memodnRSA算法73.解密對密文分組的解密運(yùn)算為：m≡cdmodn證明RSA算法中解密過程的正確性.證明：由加密過程知c≡memodn，所以cdmodn≡medmodn≡m1modφ(n)modn≡

4、mkφ(n)+1modnRSA算法8下面分兩種情況：①m與n互素，則由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含義，由于n=pq，所以gcd(m,n)=1意味著m不是p的倍數(shù)也不是q的倍數(shù)。因此gcd(m,n)≠1意味著m是p的倍數(shù)或q的倍數(shù)，不妨設(shè)m=tp，其中t為一正整數(shù)。此時必有g(shù)cd(m,q)=1，否則m也是q的倍數(shù)，從而是pq的倍數(shù)，與m

5、odq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq因此存在一整數(shù)r，使得mkφ(n)=1+rq，兩邊同乘以m=tp得mkφ(n)+1=m+rtpq=m+rtn即mkφ(n)+1≡mmodn，所以cdmodn≡m.RSA算法10例：選p=7，q=17.求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，滿足1

6、5mod119≡2476099mod119≡66;解密過程為m≡6677mod119≡19.RSA算法11RSA中的計算問題1.RSA的加密與解密過程RSA的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計算，則中間結(jié)果非常大，有可能超出計算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。RSA算法122.模指數(shù)運(yùn)算的快速算法例如求x16，直接計算的話需做15次乘法。然而如果重復(fù)對每

7、個部分結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16則只需4次乘法。求am可如下進(jìn)行，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此RSA算法13例：求a1919=1×24+0×23+0×22+1×21+1×20所以a19=((((a1)2a0)2a0)2a1)2a1練習(xí)：求a7和a8，并統(tǒng)計快速運(yùn)算法的運(yùn)算次數(shù).RSA算法14RSA算法RSA的快速實現(xiàn)加密很快，指數(shù)小；解密比較慢，指數(shù)較大.利用中國剩余定理CR