【教学课件】第十讲公钥加密算法(续).ppt
第十讲公钥加密算法(续),公钥密码(续)RSA ElGamal algorithms,1.公钥加密,公钥加密算法:用于加密任何消息常能用于签名和密钥交换eg.RSA,ElGamal 基于不同有限域的指数运算(galois 整数域、elliptic curves etc)其它问题的公钥体制(Error Correcting Codes)大多数都被攻破,2.RSA(Rivest,Shamir,Adleman),使用最广泛的公钥加密算法Rivest,Shamir&Adleman(RSA)in 1977 R L Rivest,A Shamir,L Adleman,On Digital Signatures and Public Key Cryptosystems,Communications of the ACM,vol 21 no 2,pp120-126,Feb 1978,3.RSA Setup,每个用户生成自己的公钥私钥对:选择两个随机大素数(100 digit),p,q 计算模数 N=p.q 选择一个随机加密密钥匙 e:eN,gcd(e,(N)=1 解下列同余方程,求解密密钥 d:e.d=1 mod(N)and 0=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.RSA Usage,要加密消息 M，发送者要得到接收者的公钥Kr=er,Nr 计算:C=Mer mod Nr,where 0=MN 为解密 C，接收者使用私钥 K-1r=d,p,q 计算:M=Cd mod Nr,6.RSA理论,RSA 基于Fermats Theorem:if N=pq where p,q are primes,then:X(N)=1 mod N for all x not divisible by p or q,ie gcd(x,(N)=1 where(N)=(p-1)(q-1)但在 RSA 中，e&d 是特殊选择的ie e.d=1 mod(N)或e.d=1+R(N)hence have:M=Cd=Me.d=M1+R(N)=M1.(M(N)R=M1.(1)R=M1 mod N,8。RSA举例,例子：1.选素数p=47和q71，得n=3337,(n)=46703220；2.选择e=79，求得私钥d=e-1 1019(mod 3220）。3.公开n=3337和e=79.4.现要发送明文688，计算：68879(mod 3337)=15705.收到密文1570后，用私钥d1019进行解密：15701019（mod 3337)=688,9。RSA 安全性,RSA 安全性基于计算(N)的困难性 要求分解模N,10.RSA的实现问题,需要计算模 300 digits(or 1024+bits)的乘法计算机不能直接处理这么大的数（计算速度很慢）需要考虑其它技术，加速RSA的实现,11.RSA 的快速实现,加密很快，指数小解密比较慢，指数较大利用中国剩余定理CRT，CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod R）即:M1=M mod p=(C mod p)d mod(p-1)M2=M mod q=(C mod q)d mod(q-1)解方程 M=M1 mod p M=M2 mod q 具有唯一解（利用CRT）：:M=(M2+q-M1)u mod q p+M1 其中 p.u mod q=1,12。El Gamal 公钥加密方案,Diffie-Hellman key distribution scheme 的变形能够用于安全交换密钥published in 1985 by ElGamal:T.ElGamal,A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,IEEE Trans.Information Theory,vol IT-31(4),pp469-472,July 1985.安全性是基于离散对数 缺点：增加了消息长度（2倍）,13 密钥建立,密钥生成：选取一个大素数p及本原元a mod p接收者 Bob有一个密秘钥 xB 计算 yB=axB mod p,14.El Gamal 加密,为加密 M 发送者选择随机数k,0=k=p-1 计算消息密钥 K:K=yBk mod p 计算密文对:C=C1,C2 C1=ak mod p C2=K.M mod p 发送到接收者k 需要永久保密,15.El Gamal 解密,首先计算 message key K K=C1xB mod p=ak.xB mod p 计算明文:M=C2.K-1 mod p,16.El Gamal Example,选择 p=97 及本原根 a=5 recipient Bob 选择 秘密钥xB=58&计算并发布公钥yB=558=44 mod 97 Alice 要加密 M=3 to Bob 首先得到 Bob的公开密钥 yB=44 选择随机 k=36 计算:K=4436=75 mod 97 计算密文对:C1=536=50 mod 97 C2=75.3 mod 97=31 mod 97 发送 50,31 to Bob Bob 恢复 message key K=5058=75 mod 97 Bob 计算 K-1=22 mod 97 Bob 恢复明文 M=31.22=3 mod 97,17。公钥密码现状,已知的安全算法是有限域上指数运算 素数域GF(p)上的整数运算多项式运算 GF(2n)椭圆曲线上的运算(elliptic curves)(harder to compute so use smaller sizes)基于其它困难问题的体制,18.公钥密码方案的实际应用,实现速度 通常用于交换对称算法的加密密钥数字签名算法（下节内容）,19 小结,RSA 算法ElGamal 算法实现问题,Exercises,Illustrate the operation of RSA,given the following parameters:System modulus n=119(7x17)encryption exp e=11 Determine the decryption exponent d,and hence details the public and private keys for this user.Then show how a message M=20 would be encrypted and decrpyted.,END!,
