现代密码学第7讲：公钥密码学2

1公钥密码（二）《现代密码学》第七讲上节内容回顾公钥密码体制的提出及分类公钥密码体制的基本概念单向陷门函数的概念设计公钥加密算法--背包密码体制3本节主要内容RSA算法及其分析ElGmal算法椭圆曲线密码体制其它公钥密码算法4RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制，该体制已得到广泛的应用。它既可用于加密、又可用于数字签字。RSA算法的安全性基于数论中大整数分解的困难性。RLRivest,AShamir,LAdleman,OnDigitalSignaturesandPublicKeyCryptosystems,CommunicationsoftheACM,vol21no2,pp120-126,Feb1978RSA算法51.密钥的产生①选两个安全的大素数p和q。②计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e，满足1eφ(n)，且gcd(φ(n),e)=1。④计算d，满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。⑤以{e,n}为公开钥,{d,n}为秘密钥。RSA算法1选取大素数的方法：随机产生一个大整数，利用素性检测算法判定该整数是否为素数2以往素检测的算法都是概率性的，即存在一定的错误概率；32003年，印度人发表文章“PrimesisinP”，证明了素判定问题是一个多项式时间问题。1）辗转相除法2）利用欧拉定理求e^{φ(φ(n))}-1思考：分析两种计算方法的效率62.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：c≡memodnRSA算法73.解密对密文分组的解密运算为：m≡cdmodn证明RSA算法中解密过程的正确性.证明：由加密过程知c≡memodn，所以cdmodn≡medmodn≡m1modφ(n)modn≡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的倍数也不是q的倍数。因此gcd(m,n)≠1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾RSA算法9由gcd(m,q)=1及Euler定理得mφ(q)≡1modq，所以mkφ(q)≡1modq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq因此存在一整数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，满足1eφ(n)，且gcd(φ(n),e)=1，计算满足d·e=1mod96且小于96的d.因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}.设明文m=19，则由加密过程得密文为c≡195mod119≡2476099mod119≡66;解密过程为m≡6677mod119≡19.RSA算法11RSA中的计算问题1.RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。RSA算法122.模指数运算的快速算法例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此12012222kkkbbbbbmaaaaaaRSA算法13例：求a1919=1×24+0×23+0×22+1×21+1×20所以a19=((((a1)2a0)2a0)2a1)2a1练习：求a7和a8，并统计快速运算法的运算次数.RSA算法14RSA算法RSA的快速实现加密很快，指数小；解密比较慢，指数较大.利用中国剩余定理CRT，加快计算速度.CRT对RSA解密算法生成两个解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)modpM2=Mmodq=(Cmodq)dmod(q-1)modq解方程组M=M1modp;M=M2modq.利用CRT,具有唯一解：M=[((M2+q-M1)umodq]p+M1.其中p.umodq=1.15整数分解问题：已知n是两个大素数的乘积，求n的素分解RSA的安全性是基于分解大整数困难的假定如果RSA的模数n被成功地分解为p×q，则获得φ(n)=(p-1)(q-1)，从而攻击者能够从公钥e解出d，即d≡e-1modφ(n)，攻击成功.RSA算法的安全性16至今还未能证明分解大整数就是NPC问题，也许有尚未发现的多项式时间分解算法.随着人类计算能力的不断提高，原来被认为是不可能分解的大数已被成功分解.例如RSA-129（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解.RSA算法的安全性17分解算法的进一步改进.过去分解算法都采用二次筛法,如对RSA-129的分解.而对RSA-130的分解则采用了一个新算法，称为推广的数域筛法，该算法在分解RSA-130时所做的计算仅比分解RSA-129多10%.1）在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的.RSA算法的安全性182）|p-q|要大由，如果|p-q|小，则(p-q)2/4也小；因此(p+q)2/4稍大于n,即(p+q)/2稍大于n1/2。那么①顺序检查大于n1/2的每一整数x，直到找到一个x使得x2-n是某一整数（记为y）的平方。②由x2-n=y2，得n=(x+y)(x-y)，可得n的分解.222444pqpqpqnpqRSA算法的安全性193）p-1和q-1都应有大素因子设攻击者截获密文c，可如下进行重复加密：2223111modmodmodmodtttttteeeeeeeeeeeeeeeecmmncmmncmmncmmnRSA算法的安全性20若，即，则有，即，所以在重复加密的倒数第2步就可以恢复出明文m.这种攻击法只有在t较小时才是可行的，为抵抗这种攻击，应保证使t很大.所以为使t大，p-1和q-1都应有大的素因子，且Φ((p-1)*(q-1))有大的素因子1modteccnmodteeccn1(())modteeecmnmodtecmnRSA算法的安全性1mod(1)teccn11mod()(2)ten1|((1)(1))(3)tpqRSA算法的安全性4）RSA的选择密文攻击一般攻击者是将希望解密的信息C作一下伪装reC，让拥有私钥的实体解密。然后，经过解密计算就可得到它所想要的信息。(reC)d=red*Cdmodn=r*Mmodn，所以M=(reC)d*r-1这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，只有采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密。RSA算法的安全性5）RSA的公共模数攻击若系统中用户共有一个模数n，而拥有不同的e和d。若存在同一信息（设为P）分别用不同的公钥（e1和e2）加密，C1=Pe1modn；C2=pe2modn设密码分析者截获n、e1、e2、C1和C2，若恰好e1和e2互质，则他可以得到P。RSA算法的安全性证明：因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r*e1+s*e2=1则(C1)r*(C2)s=(Pe1)r*(pe2)smodn=Pr*e1+s*e2modn=Pmodn不要共享模数n其它共模攻击方法：在共模假设下，一对e和d将有利于攻击者分解模数；或者计算出其它成对的e’和d’，而无需分解模数。24RSA算法的安全性RSA存在很多种攻击，并不是因为算法本身存在缺陷，而是由于参数选择不当造成的，为保证算法足够安全，参数须满足下面几个基本要求：需要选择足够大的素数p,q,|p-q|较大，且(p-1)和(q-1)没有小的素因子.通常选择小的加密指数e,且与ø(N)互素，e对所有用户可以是相同的，最初建议使用e=3，现在3太小，常使用e=216-1=65535.解密指数比较大25Diffie-Hellmankeydistributionscheme的变形能够用于安全交换密钥Publishedin1985byElGamal:T.ElGamal,APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms,IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.安全性基于有限域上的离散对数问题的困难性.缺点：增加了传送信息长度（2倍）ElGamal算法261)密钥产生过程：首先选择一素数p,生成元g和小于p的随机数x，计算y≡gxmodp，以(y,g,p)作为公开密钥，x作为秘密密钥.2)加密过程：设欲加密明文消息为M.随机选一与p-1互素的整数k，0=k=p-1；计算密文对:C={C1,C2},发送给接收者.C1≡gkmodp,C2≡ykMmodp.ElGamal算法273)解密过程:计算明文:因为.21modxCMpC21modmodmodmodkkxkxkCyMyMpppMpCgyElGamal算法k需要永久保密，且不能重复使用.为什么？281)密钥生成.选择公开参数：p=97及本原根a=5；Bob选择秘密钥xB=58，计算并发布公钥yB=558=44mod97.2)Alice要加密M=3给Bob.首先得到Bob的公开密钥yB=44，选择随机k=36计算:K=4436=75mod97.计算密文对:C1=536=50mod97；C2=75.3mod97=31mod97.发送{50,31}给Bob.3)Bob解密消息.恢复消息密钥K=5058=75mod97.Bob计算K-1=22mod97.Bob恢复明文M=31*22=3mod97.ElGamal算法ElGamal算法有限域上离散对数问题已知（Zp，+，*）是一个有限域，g为Zp*的生成元，y∈Zp，求x使得y=gxmodp如果求离散对数问题是容易的，则获得公钥攻击者能够解出x，则算法完全破译.ElGamal算法为什么离散对数问题难解？RSA与ElGamal比较RSAElGamal加密一次模幂运算两次模幂+一次模乘解密一次模幂运算一次模幂运算密文密文不扩张密文扩张确定算法不确定算法安全RSA问题离散对数问题32椭圆曲线密码体制ECC（ellipticcurvecryptography）被IEEE公钥密