第7讲 公钥密码体制

密码学韦宝典副教授中山大学电子系[e-mail]第7讲：公钥密码体制一：公钥密码原理二：RSA密码体制三：Rabin密码体制四：离散对数五：ElGamal密码体制六：Diffie-Hellman密钥协商七：公钥密码总结一、公钥密码原理双(公)钥密码体制1976年W.Diffie和M.Hellman;R.Merkle[1978]可用于保密通信，也可用于数字签字密码学史上划时代的事件为解决计算机信息网中的安全提供了新的理论和技术基础加密变换(公钥)公开解密变换(私钥)保密一、公钥密码原理公钥密码方案•RSAscheme(‘78):R.L.Rivest,A.Shamir,L.Adleman,“AMethodforObtainingDigitalSignaturesandPublicKeyCryptosystems”,CACM,Vol.21,No.2,pp.120-126,Feb,1978•McEliecescheme(‘78)•Rabinscheme(‘79)•Knapsackscheme(‘79-):Merkle-Hellman,Chor-Rivest•Williamsscheme(‘80)•ElGamalscheme(‘85)•EllipticCurvebasedscheme(‘85):Koblitz,Miller•HiddenFieldEquations(’95):C*,Patarin•LatticeCryptography(’97-):Ajtai(AD,DDH,NTRU)•NonabeliangroupCryptography(2000):Braid一、公钥密码原理二、RSA密码体制1978年MIT三位年青数学家R.L.Rivest，A.Shamir和L.Adleman用数论构造双钥密码的方法，称作MIT体制，后被广泛称为RSA体制它既可用于加密、又可用于数字签名易懂且易于实现，是目前仍然安全并且逐步被广泛应用的一种体制国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准Internet采用的PGP(PrettyGoodPrivacy)也将RSA作为传送会话密钥和数字签名的标准算法RSA算法的安全性基于数论中大整数分解的困难性参数选择：独立地选取两大素数p1和p2(各512bit的数)，计算n=p1×p2其欧拉函数值(n)=(p1－1)(p2－1)随机选一整数e，1e(n)，((n),e)=1(因而在模(n)下e有逆元)d=e-1mod(n)公钥为n，e;私钥为d(p1,p2不再需要，可以销毁)二、RSA密码体制加密、解密：将明文分组，各组长1024比特明文集Az={x：1xn,(x,n)=1}注意，(x,n)1是很危险的xAz的概率：加密y=xemodn解密x=ydmodn证明：yd=(xe)d=xde，因为de1mod(n)即de=q(n)＋1由欧拉定理，(x,n)=1意味x(n)1modn，故有yd=xde=xq(n)+1xxq(n)=x1=xmodn陷门函数：Z=(p1,p2,d)11111)1)(1()(21212121ppppppppnn二、RSA密码体制例子：p1=47，p2=71，n=47×71=3337，(n)=46×70=3220e=79，d=e-1(mod3220)=1019公开n=3337和e=79保密私钥d=1019销毁p1,p2令x=6882326879666683，分组x1=688，x2=232，x3=687，x4=966，x5=668，x6=3x1的加密为(688)79(mod3337)=1570=C1，类似计算出其他各组密文，y=15702756209122762423158第一组密文解密为(1570)1019mod3337=688=x类似解出其他各组密文二、RSA密码体制RSA加密实质上是一种Zn*Zn*上的单表代换！给定n=p1p2和合法明文xZn*，密文y=xemodnZn*对于xx’，必有yy’Zn*中的元素是一个明文，也是与某个明文相对应的一个密文因此，RSA是ZnZn的一种单表代换密码关键在于：n极大时，若不知陷门信息，则极难确定这种对应关系由于这种一一对应性，RSA不仅可以用于加密也可用于数字签名二、RSA密码体制安全性:分解模数n理论上，RSA的安全性取决于模n分解的困难性，但数学上至今还未证明分解模就是攻击RSA的最佳方法，也未证明分解大整数就是NP问题，可能有尚未发现的多项式时间分解算法。人们完全可以设想有另外的途径破译RSA，如求出解密指数d或找到(p1－1)(p2－1)等。但这些途径都不比分解n来得容易。甚至Alexi等[1988]曾揭示，从RSA加密的密文恢复某些比特的困难性也和恢复整组明文一样困难。这一视在困难性问题是个NP问题，但还没人证明它为NPC问题。二、RSA密码体制采用广义数域筛分解不同长度RSA公钥模所需的计算机资源二、RSA密码体制密钥长(bit)所需的MIPS-年*1164001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,000,000*MIPS-年指以每秒执行1,000,000条指令的计算机运行一年安全性:分解模数n技术进展使分解算法和计算能力在不断提高，计算所需的硬件费用在不断下降RSA-129：110位十进制数字早已能分解。Rivest等最初悬赏$100的RSA-129，已经由包括五大洲43个国家600多人参加，用1600台机子同时产生820条指令数据，通过Internet网，耗时8个月，于1994年4月2日利用二次筛法分解出为64位和65位的两个因子，所给密文的译文为“这些魔文是容易受惊的鱼鹰”。这是有史以来最大规模的数学运算。原来估计要用4亿亿年。RSA-130于1996年4月10日利用数域筛法分解出来。RSA-140于1999年2月分解出来。RSA-154(512bit)于1999年8月分解出来。RSA-160,2003.01(~zimmerma/records/rsa160)RSA-174(576bit),2003.12二、RSA密码体制安全性:分解模数n从n若能求出(n)，则可求得p1,p2。n－(n)＋1=p1p2－(p1－1)(p2－1)＋1=p1＋p2((p1+p2)2-4n)1/2=p1-p2但已证明：求(n)等价于分解n的困难从n求d亦等价于分解n目前尚不知是否存在一种无需籍助于分解n的攻击法也未能证明破译RSA的任何方法都等价于大整数分解问题二、RSA密码体制安全性:其它途径Simmons和Norris提出迭代/循环攻击法：给定一RSA的参数为(n,e,y)=(35,17,3)，由y0=y=3计算y1=317=33mod35再由y1计算y2=y117=3mod35从而得到明文x=y1=33mod35。一般对明文x加密多次，直到再现x为止。Rivest证明：当p1－1和p2－1中含有大素数因子，且n足够大时，这种攻击法成功的概率趋于0。二、RSA密码体制安全性:迭代攻击法消息破译0）收集用户A以公钥e加密的密文y=xemodn，目标分析出消息x1）选随机数rn，计算y1=remodn，这意味r=y1dmodn2）计算y2=y1×ymodn3）令t=r-1modn=y1-dmodn4）请A对消息y2进行签字(用私钥，但不能用Hash函数)得到s=y2dmodn5）攻击者计算tsmodn=y1-d×y2dmodn=y1-d×(y1d×yd)modn=ydmodn=x得到了明文。二、RSA密码体制安全性:选择明文攻击消息破译y=xemodn，目标分析出消息x=ydmodn=ydy1dy1-dmodn=(yy1)dy1-dmodn=(yre)d(re)-dmodn=y2dr-1modn=y2dtmodny1=remodny2=yy1=yremodnt=r-1modn二、RSA密码体制安全性:选择明文攻击多人共用同一模数n，各自选择不同e和d，实现简单但不安全若消息以两个互素(一般如此)的密钥加密，在共用同一个模下，则可用任一密钥恢复明文e1和e2是两个互素的不同密钥，共用模为n，对同一消息x加密得y1=xe1modn,y2=xe2modn分析者知道n,e1,e2,y1和y2因为(e1,e2,)=1，所以由Euclidean算法有re1+se2=1计算(y1-1)-ry2s=xmodn(假设r是负数)二、RSA密码体制安全性:公用模攻击小的e可加快加密和验证签字速度，且所需的存储密钥空间小但若加密钥e选择得太小，则容易受到攻击网中三用户的加密钥e均选3，分别模n1,n2,n3(互素，否则可求出公因子，而降低安全性)一用户将消息x传给三个用户的密文分别为y1=x3modn1xn1利用中国余定理，y2=x3modn2xn2可从y1,y2,y3求出y3=x3modn3xn3y=x3mod(n1n2n3)由xn1,xn2,xn3，可得x3n1n2,n3，故有x=y1/3扩展为k个用户：将相同的消息x传给k个人，只要ke(e+1)/2，采用低指数亦可有效攻击为抗击这种攻击e必须选得足够大e选为16位素数，既可兼顾快速加密，又可防止这类攻击二、RSA密码体制安全性:低加密指数攻击在x后加时戳y1=(2tx+t1)3modn1y2=(2tx+t2)3modn2y3=(2tx+t3)3modn3t是t1,t2,t3的二元表示位数可防止这类攻击对短的消息，可用随机数字填充以防止低加密指数攻击d小也不行：对en，dn1/4，也可以攻破这类RSA体制二、RSA密码体制安全性:低加密指数攻击构造y=xemodn，猜测d值，做ydmodn，直到试凑出ydxmodnWiener给出对小d的系统攻击法，证明了当d长度小于n的1/4时，由连分式算法，可在多项式时间内求出d值利用测定RSA解密所进行的模指数运算的时间来估计解密指数d，而后再精确定出d的取值。可通过将解密运算量与参数d无关化来挫败此攻击(R.Rivest)还可采用盲化技术：将数据盲化后再密，而后做去盲运算这样做虽然不能使解密运算时间保持不变，但计算时间被随机化而难于推测解密进行的指数运算的时间二、RSA密码体制安全性:定时攻击法(Timing:P.Kocher)对明文x，0xn－1，采用RSA体制加密，可能出现xe=xmodn，致使消息暴露这是明文在RSA加密下的不动点总有一些不动点，如x=0，1和n－1一般有[1+gcd(e－1,p－1)][1+gcd(e－1,q－1)]个不动点由于e－1，p－1和q－1都是偶数所以不动点至少为9个一般来说，不动点个数相当少而可忽略二、RSA密码体制安全性:消息隐匿问题D.Boneh.TwentyYearsofAttacksontheRSACryptosystem.NoticesoftheAmericanMathematicalSociety,46(2):203-213,1999.~dabo/abstracts/RSAattack-survey.html二、RSA密码体制安全性(1)n=p×q的确定：p与q必须为强素数强素数p的条件：(a)存在两个大素数p1和p2，p1|(p－1)，p2|(p＋1)(b)存在4个大素数r1,s1,r2及s2，使r1|(p1－1),r2|(p2－1),s1|(p1＋1),s2|(p2＋1)。p1和p2为二级素数；r1,r2,s1和s2为三级素数二、RSA密码体制RSA参数的选择采用强素数的理由如下：若，pi为素数，ai为正整数分解式中piB，B为已知一个小整数则存在一种p－1的分解法，使我们易于分解n令n=pq，且p－1满足上述条件，piB