求多项式方程的小值解及其应用

论文摘要

RSA密码体制由Rivest，Shamir及Adleman始创[41]，是目前世界上所知应用最广泛的公钥密码体制，使用RSA最主要的缺点是加解密操作的费用相当大．多素数RSA为标准RSA密码体制的一个推广，其中模由多于两个的素数相乘得来，当加密操作执行时，模每个素数，而后合并使用中国剩余定理．加密的代价降到每个素数（对于确定大小的模）．因此，当需要降低成本时，多素数RSA可能为RSA的一个现实的选择．RSA的安全性自它创造之日起已被很好的研究（参见Boneh[6]）．若多素数RSA现在实行它的安全性需被更进一步的研究．目前，存在部分私钥泄露攻击，攻击者拥有私钥比特的某些知识并用它来攻破系统，结果是具有实际意义的．因为可能削弱私钥的比特．1998年，Boneh，Durfee和Frankel在[2]提出RSA的几种部分私钥泄露攻击，其中的某些攻击要求知道私钥的最少有效比特（LSBs），另一些要求知道最多有效比特（MSBs）．另外，在他们的攻击中，公钥必须是相对小的．Wiener的攻击[46]及Boneh和Durfee[4]的改进可被看作部分私钥泄露攻击，其中，已知的最多有效比特均等于0．在[2]中提出的问题是是否存在RSA的密钥泄露攻击，可以对比模的平方根大小大的公钥起作用．2003年，Blomer和May[1]描述了一些攻击，允许大一点的公钥，但仍未达到模的实际大小，而后Ernst,Jochemsz等人在[17]中提出攻击对实际大小的公钥，它可以逐渐达到实际的私钥大小的算法．在96欧密会上，Coppersmith提出一种寻找双变量整系数多项式方程小值根的算法，该算法基于格基约化算法．在此基础上发展了分解因子攻击，它适用于知道部分因子的与多素数RSA模相同形式的整数．该攻击是Boneh，Durfee和Howgrave-Graham的格基分解因子思想的推广，模的形式为N=prq．对平衡r素数RSA假设知道N的r个素数中的v个1≤v≤r-2，另外对零或者更多余下的未知素数和私钥，知道最多或最少的有效比特．Coppersmith的解决双变量多项式方程的算法被Howgrave-Graham在[24]中进一步简化．除了更易于理解和应用，Howgrave-Graham的方法的一个显著的优点是可以启发式的延伸到多变量多项式方程．在此基础上Jean-SebastienCoron在[15]中提出了一项简化算法，可以在得知n=pq中p的高位log2n／4比特的前提下分解n.本论文是应用Jean-SebastienCoron的简化算法来求解三变量整系数多项式方程的小根，可以在得知n=pqr中p，q的高位或低位log2n／5比特的前提下分解n．本文主要结论为：定理3．1令p（x，y，z）为Z上三变量不可约多项式，每个单变量的最高次数是δ．令X，Y和Z为期望的整数解（x0，y0，z0）的上界．令对某些ε>0，那么在多项式时间（logW,2δ）内，可以找到使得p（x0，y0，z0）=0，|x0|≤X，|y0|≤Y,|z0|≤Z的所有整数对（x0，y0，z0）．该攻击如同多素数RSA的其它格基攻击一样建立在代数独立假设上．定理3．3对任意的ε>0，给定N=PQR及P,Q的高位或低位1/5log2N比特，我们可以在多项式时间（log N）内得到N的分解式．定理4．1令p（x1,x2,...,xr）为整数上的r变量多项式，每个单变量的最高次数是δ．令X1，X2,...，Xr为期望的整数解x1,x2,...,xr的上界．令W=maxi1,i2,...,ir|pi1,i2,...,ir|X1i1X2i2...Xrir.对某些ε>0，那么在多项式时间内，可以找到使p(x10,x20,...,xr0)=0，|x10|≤X1,|x20|≤X2,...,|xr0|≤Xr的所有整数对(x10,x20,...,xr0)．定理4．2对任意ε>o，对于N=P1,P2...Pr给定其中P1,P2,...,Pr-1的高位1/r+2 log2N比特，我们可以在多项式时间内得到N的分解式．

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 第二章 相关结果及LLL算法
• §2.1 LLL算法
• §2.2 多项式分解背景
• §2.3 相关说明
• 第三章 求三变量整数多项式方程的小值根及因子分解
• §3.1 求三变量整数多项式方程的小值根
• §3.2 因子分解
• 第四章 扩展到多变量情况
• 第五章 已知多素数分解
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表