RSA密码

第6章RSA密码1.2©2006第6章RSA密码教学目的•了解公开密匙密码系统•了解RSA算法、数论背景和数字签名•了解二次筛法与Pollard的p-1法•了解利用RSA私钥因数分解•了解Wiener低幂次d攻击•了解Rabin密码1.3©2006第6章RSA密码公开密钥密码系统本章内容RSA算法RSA的数论背景RSA数字签名同时进行RSA加密和RSA数字签名RSA-129挑战与因数分解1.4©2006第6章RSA密码二次筛法与Pollard的p-1法本章内容利用RSA私钥因数分解RSA密码系统实用的注意事项Wiener低幂次d攻击Rabin密码1.5©2006第6章RSA密码公开密匙密码系统6.1公开密匙密码系统（1）将一已加密的信息m解密，即可还原m，即（2）加密以及解密函数、必须是容易计算的。（3）公开加密函数，并不会提供任何简易计算解密函数的方法，在实际应用中，这意味着只有Bob才能将任何经加密函数加密的信息有效地解密，也只有Bob知道“陷门”（Trapdoor）从而有效计算。（4）若将任何信息m先用解密函数运算，再用加密函数运算，亦可还原信息m，即BobBobD(E(m))mBobE()BobD()BobE()BobD()BobE()BobD()BobBobE(D(m))m定义单向陷门函数，TrapdoorOne-WayFunction函数若满足性质（1）、（2）、（3），就称为单向陷门函数，若性质（1）、（2）、（3）、（4）皆满足，就称为单向陷门置换（TrapdoorOne-WayPermutation）。BobE()1.6©2006第6章RSA密码数字封装1.7©2006第6章RSA密码RSA算法6.2RSA算法•密匙产生：Bob取相异质数p、q（保密），计算RSA模数（RSAModulus）n=pq，将其公开，取e为加密密钥将其公开，其中e必须与φ(n)互质，在此情况下，Bob的公开密钥为(n,e)；Bob计算d为解密密钥（保密），(n,d)为Bob的私钥（PrivateKey）其中(n)(p1)(q1)ed1(mod(n))•加密：Alice取得Bob的公开密钥(n,e)，用加密函数计算ecE(m)m(modn)将密文c传给Bob。•解密：Bob用解密函数计算dmD(c)c(modn)解密还原成明文。1.8©2006第6章RSA密码RSA算法举例密匙产生Bob取质数p=241、q=311，计算n=pq=74951，取e=1033为加密钥，在此情况，Bob的公开密钥为(n,e)=(74951,1033)；Bob用广义辗转相除法计算解密密钥(n)(p1)(q1)2403107440011de10333097(mod74400)1.9©2006第6章RSA密码RSA算法举例加密Alice的明文（令a=0、b=1、…、z=25），取得Bob的公开密钥为，加密得密文26m'rsa'(17,18,0)21726182611960(n,e)(74951,1033)103e1033102222222221cm1196011960((11960))((11960))1196063302472901196051922(mod74951)次平方。1.10©2006第6章RSA密码RSA算法举例解密111043d3097111022222222222222222221mc5192251922((51922))((51922))((51922))((51922))51922580714573249264739775192211960(mod74951)次平方次平方,26m11960(17,18,0)'rsa'所以1.11©2006第6章RSA密码RSA的数论背景6.3RSA的数论背景Euler定理令整数a、n，其中a与n互质。则(n)a1(modn)Euler定理推广了费马小定理定理令整数a、n，其中a与n互质。则p1a1(modp)1.12©2006第6章RSA密码RSA加密解密函数定理RSA加密解密函数令p、q为相异质数，令n=pq，令e为与(p-1)(q-1)互质的整数，令d满足ed1(mod(p1)(q1))令加密函数eE(m)m(modn)，解密函数dD(c)c(modn)则对所有整数m皆满足D(E(m))m(modn)且E(D(m))m(modn)1.13©2006第6章RSA密码RSA修订版令Alice想将明文m加密成密文c传至Bob，而Bob将密文c解密还原成明文m。•密匙产生Bob取相异质数p、q（保密），计算RSA模数n=pq，将其公开，取e为密钥将其公开，其中e必须与互质，Bob的公开密钥为(n,e)；计算(n)lcm(p1,q1)•加密Alice取得Bob的公开密钥(n,e)，用加密函数计算ecE(m)m(modn)将密文c传给Bob。•解密Bob有两种解密计算方式：一是d1mD(c)c(modn)以及用中国余式定理加速解密1de(mod(n))pdd(modp1)qdd(modq1)1qxq(modp)Bob的私钥为pqq(n,d,d,d,x)pqCRTddqqmD(c)xq(cmodp)(1xq)(cmodq)(modn)。1.14©2006第6章RSA密码RSA数论背景定理对所有整数m皆满足CRTD(E(m))m(modn)且CRTE(D(m))m(modn)证明：pqddeeCRTqqD(E(m))xq((m)modp)(1xq)((m)modq)(modn)pedm(modq)1e(dk(q1))m(modq)1ek(q1)1klcm(p1,q1)mmm(modq)若q|m，此时CRTD(E(m))0m(modq)同理可得：再用中国余式定理得CRTD(E(m))m(modp)(某整数K1)pqpppddeeCRTqqededpppqedD(E(m))xq((m)modp)(1xq)((m)modq)(modn)(1-xp)mxpm(gcd(p,q)=1,xp+xq=1)m(modp)2e(d+kp)m(modp)2ekp1k1cm(p1,q1)mmm(modp)(某整数K2）)1.15©2006第6章RSA密码RSA数字签名6.4RSA数字签名RSA数字签名是一种可回复式数字签名法（RecoveryScheme）Bob利用RSA密码系统，数字签名一简短的文件，并传递给他所有认识的人。例：m'bobcrackedrsa'1.16©2006第6章RSA密码密匙产生•密匙产生Bob的RSA密钥为(n,e,d)(24206811682801236799169,31,19521622324306440686971);其中RSA模数npq(p622354832383,q38895514943)加密密钥为e=31，解密密钥为11de(mod(n))(p1)(q1)31(mod24206811682139986451844)19521622324306440686971。1.17©2006第6章RSA密码数字签名•数字签名假设代码空白=0、a=1、b=2、…、z=26，又2727[logn][log24206811682801236799169]15故以全文为一组编码，得代码27141312109876542'bobcrackedrsa'(2,15,2,0,3,18,1,3,11,5,4,0,18,19,1)227+1527+227+327+1827+127+327+1127+527+427+1827+1927+1279927250081200479782m,再以解密函数分别对此代码“数字签名”BobD()d19521622324306440686971sm(modn)279927250081200479782(mod24206811682801236799169)17083178691394655337512并将“数字签名”s17083178691394655337512传给所有她想要传送的人。1.18©2006第6章RSA密码签名还原•签名还原Alice收到了Bob的“数字签名”，经过计算e31ms(modn)17083178691394655337512(mod24206811682801236799169)27992725008120047978227=(2,15,2,0,3,18,1,3,11,5,4,0,18,19,1)'bobcrackedrsa',1.19©2006第6章RSA密码同时RSA加密和RSA签名6.5同时RSA加密和RSA签名1.20©2006第6章RSA密码RSA-129挑战与因数分解6.6RSA-129挑战与因数分解例：Bob的RSA公开密钥为(n,e)=(782741,7)。攻击者Eve截收到Alice传给Bob的密文144310，并知道Alice与Bob的通信代码为：a=0、b=1、c=2、…、z=25。计算，知道每4个字母为一组代码。如果Eve知道n的质因数分解，即知道是何质数p、q使得pq=782741，就可计算，再以广义辗转相除法或xeuclidean()程序计算得解密密钥2626[logn]=[log782741]=4(n)(p1)(q1)1d7mod(n)便可还原明文的代码dm144310mod(782741)1.21©2006第6章RSA密码RSA-129挑战与因数分解如何找到质因数p、q使得抛弃＝782741？Eve试着从2到小于等于的质数试除，（共计有153个质数）在第150个质数时发现[782741]884782741/863=907=q因此，(n)(p1)(q1)862906780972(n)(p1)(q1)862906780972。以广义辗转相除法得1d=7223135(mod(n)780972)所以明文代码为223135144310126037(mod782741)126037而26126037=484726+15=(18626+11)26+15=((726+4)26+11)26+15=(7,4,11,15)。因此明文为“help”。1.22©2006第6章RSA密码质数分解的记录年份十进制的位数备注1964201974451983692251－1用二次筛法1989106用二次筛法1994129RSA-129用二次筛法1996130RSA-130用代数数体筛法1999155RSA-155用代数数体筛法1.23©2006第6章RSA密码二次筛法Pollard的p－1法6.7二次筛选法Pollard的p-1法定义B-smooth令B为某若干质数与-1所形成的集合。令x为一整数：称x为B-smoothx的质因子均在集合B中。1.24©2006第6章RSA密码利用RSA私钥因数分解6.8利用RSA私钥因数分解例：假设Alice的RSA密钥为(n,e,d)(291999619490932896138040207735768920167,273353824517871327944626733911805527157,60102512763177539335068764336403641333)。Alice自行因数分解n如下：（1）随机找一个整数x60541520037091837230139960944836511430很正常地gcd(x,n)1（2）计算1ed1s2821462586347437743281354669886526070179902583699556