第10講 公鑰加密算法

《第10講 公鑰加密算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、第十講公鑰加密算法(續(xù))公鑰密碼(續(xù))RSAElGamalalgorithms1.公鑰加密公鑰加密算法:用于加密任何消息常能用于簽名和密鑰交換eg.RSA,ElGamal基于不同有限域的指數(shù)運(yùn)算(galois整數(shù)域、ellipticcurvesetc)其它問題的公鑰體制(ErrorCorrectingCodes)大多數(shù)都被攻破2.RSA(Rivest,Shamir,Adleman)使用最廣泛的公鑰加密算法Rivest,Shamir&Adleman(RSA)in1977RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKey

2、Cryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb19783.RSASetup每個(gè)用戶生成自己的公鑰私鑰對(duì):選擇兩個(gè)隨機(jī)大素?cái)?shù)(~100digit),p,q計(jì)算模數(shù)N=p.q選擇一個(gè)隨機(jī)加密密鑰匙e:e

3、常使用e=216-1=65535解密指數(shù)比較大5.RSAUsage要加密消息M，發(fā)送者要得到接收者的公鑰Kr={er,Nr}計(jì)算:C=MermodNr,where0<=M

4、encehave:M=Cd=Me.d=M1+R?(N)=M1.(M?(N))R=M1.(1)R=M1modN8。RSA舉例例子：1.選素?cái)?shù)p=47和q＝71，得n=3337,?(n)=46×70＝3220；2.選擇e=79，求得私鑰d=e-1?1019(mod3220）。3.公開n=3337和e=79.4.現(xiàn)要發(fā)送明文688，計(jì)算：68879(mod3337)=15705.收到密文1570后，用私鑰d＝1019進(jìn)行解密：15701019（mod3337)=6889。RSA安全性RSA安全性基于計(jì)算?(N)的困難性要求分解模N10.RSA的實(shí)現(xiàn)問題需要計(jì)算模300digits(or1

5、024+bits)的乘法計(jì)算機(jī)不能直接處理這么大的數(shù)（計(jì)算速度很慢）需要考慮其它技術(shù)，加速RSA的實(shí)現(xiàn)11.RSA–的快速實(shí)現(xiàn)加密很快，指數(shù)小解密比較慢，指數(shù)較大利用中國(guó)剩余定理CRT，CRT對(duì)RSA解密算法生成兩個(gè)解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)M2=Mmodq=(Cmodq)dmod(q-1)解方程M=M1modpM=M2modq具有唯一解（利用CRT）：:M=[((M2+q-M1)umodq]p+M1其中p.umodq=112。ElGamal公鑰加密方案Diffie-Hellmankeydistributionscheme的

6、變形能夠用于安全交換密鑰publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性是基于離散對(duì)數(shù)缺點(diǎn)：增加了消息長(zhǎng)度（2倍）13密鑰建立密鑰生成：選取一個(gè)大素?cái)?shù)p及本原元amodp接收者Bob有一個(gè)密秘鑰xB計(jì)算yB=axBmodp14.ElGamal加密為加密M發(fā)送者選擇隨機(jī)數(shù)k,0<=k<=p-1計(jì)算消息密鑰K

7、:K=yBkmodp計(jì)算密文對(duì):C={C1,C2}C1=akmodpC2=K.Mmodp發(fā)送到接收者k需要永久保密15.ElGamal解密首先計(jì)算messagekeyKK=C1xBmodp=ak.xBmodp計(jì)算明文:M=C2.K-1modp16.ElGamalExample選擇p=97及本原根a=5recipientBob選擇秘密鑰xB=58&計(jì)算并發(fā)布公鑰yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公開密鑰yB=44選擇