第10讲 公钥加密算法

第十讲公钥加密算法(续)•公钥密码(续)•RSA\ElGamalalgorithms1.公钥加密•公钥加密算法:用于加密任何消息•常能用于签名和密钥交换•eg.RSA,ElGamal•基于不同有限域的指数运算(galois整数域、ellipticcurvesetc)•其它问题的公钥体制(ErrorCorrectingCodes)•大多数都被攻破2.RSA(Rivest,Shamir,Adleman)•使用最广泛的公钥加密算法•Rivest,Shamir&Adleman(RSA)in1977•RLRivest,AShamir,LAdleman,OnDigitalSignaturesandPublicKeyCryptosystems,CommunicationsoftheACM,vol21no2,pp120-126,Feb1978•3.RSASetup•每个用户生成自己的公钥\私钥对:•选择两个随机大素数(~100digit),p,q•计算模数N=p.q•选择一个随机加密密钥匙e:eN,gcd(e,ø(N))=1•解下列同余方程,求解密密钥d:•e.d=1modø(N)and0=d=N•公开加密密钥:Kr={er,Nr}•保存其解密似钥:•K-1r={d,p,q}4。RSA参数选择•需要选择足够大的素数p,q•通常选择小的加密指数e,且与ø(N)互素•e对所有用户可以是相同的•最初建议使用e=3•现在3太小•常使用e=216-1=65535•解密指数比较大5.RSAUsage•要加密消息M，发送者要得到接收者的公钥Kr={er,Nr}•计算:C=MermodNr,where0=MN•为解密C，接收者使用私钥•K-1r={d,p,q}•计算:M=CdmodNr6.RSA理论•RSA基于Fermat'sTheorem:•ifN=pqwherep,qareprimes,then:Xø(N)=1modN•forallxnotdivisiblebyporq,iegcd(x,ø(N))=1•whereø(N)=(p-1)(q-1)•但在RSA中，e&d是特殊选择的•iee.d=1modø(N)或e.d=1+Rø(N)•hencehave:M=Cd=Me.d=M1+Rø(N)=M1.(Mø(N))R=M1.(1)R=M1modN•8。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(or1024+bits)的乘法•计算机不能直接处理这么大的数•（计算速度很慢）•需要考虑其它技术，加速RSA的实现11.RSA–的快速实现•加密很快，指数小•解密比较慢，指数较大•利用中国剩余定理CRT，•CRT对RSA解密算法生成两个解密方程（利用M=CdmodR）•即:M1=Mmodp=(Cmodp)dmod(p-1)•M2=Mmodq=(Cmodq)dmod(q-1)•解方程M=M1modp•M=M2modq•具有唯一解（利用CRT）：•:M=[((M2+q-M1)umodq]p+M1•其中p.umodq=112。ElGamal公钥加密方案•Diffie-Hellmankeydistributionscheme的变形•能够用于安全交换密钥•publishedin1985byElGamal:•T.ElGamal,APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.•安全性是基于离散对数•缺点：增加了消息长度（2倍）13密钥建立•密钥生成：•选取一个大素数p及本原元amodp•接收者Bob有一个密秘钥xB•计算yB=axBmodp•14.ElGamal加密•为加密M•发送者选择随机数k,0=k=p-1•计算消息密钥K:•K=yBkmodp•计算密文对:C={C1,C2}•C1=akmodp•C2=K.Mmodp•发送到接收者•k需要永久保密15.ElGamal解密•首先计算messagekeyK•K=C1xBmodp=ak.xBmodp•计算明文:•M=C2.K-1modp16.ElGamalExample•选择p=97及本原根a=5•recipientBob选择秘密钥xB=58&计算并发布公钥yB=558=44mod97•Alice要加密M=3toBob•首先得到Bob的公开密钥yB=44•选择随机k=36计算:K=4436=75mod97•计算密文对:•C1=536=50mod97•C2=75.3mod97=31mod97•发送{50,31}toBob•Bob恢复messagekeyK=5058=75mod97•Bob计算K-1=22mod97•Bob恢复明文M=31.22=3mod9717。公钥密码现状•已知的安全算法是有限域上指数运算素数域GF(p)上的整数运算•多项式运算GF(2^n)•椭圆曲线上的运算(ellipticcurves)(hardertocomputesousesmallersizes)•基于其它困难问题的体制18.公钥密码方案的实际应用•实现速度•通常用于交换对称算法的加密密钥•数字签名算法（下节内容）19小结•RSA算法•ElGamal算法•实现问题Exercises1.IllustratetheoperationofRSA,giventhefollowingparameters:Systemmodulusn=119(7x17)encryptionexpe=11Determinethedecryptionexponentd,andhencedetailsthepublicandprivatekeysforthisuser.ThenshowhowamessageM=20wouldbeencryptedanddecrpyted.•END!