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

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

1、1公鑰密碼（二）《現(xiàn)代密碼學(xué)》第七章上節(jié)內(nèi)容回顧公鑰密碼體制的提出及分類公鑰密碼體制的基本概念單向陷門函數(shù)的概念設(shè)計(jì)公鑰加密算法--背包密碼體制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)生①選兩個(gè)安全的大素?cái)?shù)p和q。②計(jì)算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1

3、數(shù)是否為素?cái)?shù)2以往素檢測的算法都是概率性的，即存在一定的錯(cuò)誤概率；32003年，印度人發(fā)表文章“PrimesisinP”，證明了素判定問題是一個(gè)多項(xiàng)式時(shí)間問題。1）輾轉(zhuǎn)相除法2）利用歐拉定理求e^{φ(φ(n))}-1思考：分析兩種計(jì)算方法的效率62.加密加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長度小于log2n。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算：c≡memodnRSA算法73.解密對(duì)密文分組的解密運(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ù)。此時(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中的計(jì)算問題1.RSA的加密與解密過程RSA的加密、解密過程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。RSA算法122.模指數(shù)運(yùn)算的快速算法例如求x16，直接計(jì)算的話需做15次乘法。然而如果重復(fù)對(duì)每

7、個(gè)部分結(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)計(jì)快速運(yùn)算法的運(yùn)算次數(shù).RSA算法14RSA算法RSA的快速實(shí)現(xiàn)加密很快，指數(shù)??；解密比較慢，指數(shù)較大.利用中國剩余定理CR