第10讲 公钥加密算法

《第10讲 公钥加密算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第十讲公钥加密算法(续)公钥密码(续)RSAElGamalalgorithms1.公钥加密公钥加密算法:用于加密任何消息常能用于签名和密钥交换eg.RSA,ElGamal基于不同有限域的指数运算(galois整数域、ellipticcurvesetc)其它问题的公钥体制(ErrorCorrectingCodes)大多数都被攻破2.RSA(Rivest,Shamir,Adleman)使用最广泛的公钥加密算法Rivest,Shamir&Adleman(RSA)in1977RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKey

2、Cryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb19783.RSASetup每个用户生成自己的公钥私钥对:选择两个随机大素数(~100digit),p,q计算模数N=p.q选择一个随机加密密钥匙e:e

3、常使用e=216-1=65535解密指数比较大5.RSAUsage要加密消息M，发送者要得到接收者的公钥Kr={er,Nr}计算:C=MermodNr,where0<=M

4、encehave:M=Cd=Me.d=M1+Rø(N)=M1.(Mø(N))R=M1.(1)R=M1modN8。RSA举例例子：1.选素数p=47和q＝71，得n=3337,(n)=46×70＝3220；2.选择e=79，求得私钥d=e-11019(mod3220）。3.公开n=3337和e=79.4.现要发送明文688，计算：68879(mod3337)=15705.收到密文1570后，用私钥d＝1019进行解密：15701019（mod3337)=6889。RSA安全性RSA安全性基于计算ø(N)的困难性要求分解模N10.RSA的实现问题需要计算模300digits(or1

5、024+bits)的乘法计算机不能直接处理这么大的数（计算速度很慢）需要考虑其它技术，加速RSA的实现11.RSA–的快速实现加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT对RSA解密算法生成两个解密方程（利用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.安全性是基于离散对数缺点：增加了消息长度（2倍）13密钥建立密钥生成：选取一个大素数p及本原元amodp接收者Bob有一个密秘钥xB计算yB=axBmodp14.ElGamal加密为加密M发送者选择随机数k,0<=k<=p-1计算消息密钥K

7、:K=yBkmodp计算密文对:C={C1,C2}C1=akmodpC2=K.Mmodp发送到接收者k需要永久保密15.ElGamal解密首先计算messagekeyKK=C1xBmodp=ak.xBmodp计算明文:M=C2.K-1modp16.ElGamalExample选择p=97及本原根a=5recipientBob选择秘密钥xB=58&计算并发布公钥yB=558=44mod97Alice要加密M=3toBob首先得到Bob的公开密钥yB=44选择