【作者】 孙波；

【导师】 王明强；

【作者基本信息】 山东大学 ， 信息安全， 2012， 硕士

【摘要】 作为第一个广泛应用的公钥密码体制,RSA的安全性一直是密码学界研究的热点。密码学家对RSA公钥密码体制的安全性进行了全面的分析。1990年Winner在[7]中证明了,对于每一个RSA公私钥对,只要满足d<1/3N1/4,那么可以使用连分数的方法在多项式时间内分解N=p·q。之后,Coppersmith[8,18,20]利川格理论以及LLL算法的相关结论提出了一种求同余方程小根的方法,该方法被Boneh、Durff[9]以及May[5]用于分析RSA安全性,并得到了和Winner相似的结论。经过May等人的研究,Coppersmith方法已经形成一套规范化的步骤,被广泛应用于RSA安全性分析。关于RSA安全性有一个比较有名的基本问题就是已知公私钥对(N.e,d)是否可以分解N=p·q,该问题有一个概率多项式时间的算法,但是确定性多项式时间的算法直到2007[1]年才被J.Coron和A.May找到。Coron和May给出了通过利用Coppersmith方法在多项式时间分解N=p·q的过程,整个算法的时间复杂度是(?)(log9N)。在Coron的文章中,他使用了同余方程组U=e.d-1=0mod (?). φ(N)=N-s=0mod (?).s=p+q-1.并假设已知s的高位比特s0,即s=x0+s0X,0≤x0<X对于某个已知的X。利用上述同余方程组,Coron构造了如下系列多项式可以看出对于所有的(i,j)都有gij(x0)=0mod φm.通过对上述方程利用LLL算法求解,Coron证明了当e·d≤N2的时候,可以在确定性多项式时间内分解N.本文在上述结论基础上进一步考虑了p,q间关系以及对上述结论的影响。通常情况下,为了防止N被常见的因子分解算法顺利的分解,RSA参数选择的过程对N有严格的要求。其中之一就是p和q是平衡的,即p和q有相同的比特长度,或者p-q比较小。可以看出由于p·q=N,在这种情况下s=p+q-2(?)比较小。假设本文证明在α,δ满足关系α·δ<1时,N在确定多项式时间内可以分解。本文通过构造两个不同的同余方程分别得到上述结论。考虑RSA关系式假设A=N+1-2(?)，第一种方法利用了同余方程构造目标求解方程然后采用[3]提到的方法构造了以下一系列方程(详细定义可见第2章相关内容)可以看出对于以上方程都有解(k,s)。对上述方程通过LLL算法求解,通过相应的分析即可得到本文的结论。本文的第二种方法采用了类似Coron文章中的同余方程,文中简单介绍了相关过程,然后对新的参数条件进行分析得到和方法一同样的结论。在论文的第3章分析了一种RSA的变种,这个新的RSA方案中采用子prq形式的RSA模,这里同样假设p,q平衡的情况。在这个方案中假设U=e·d=Nα,可构造余方程相应的目标求解方程为fU(x,y,z)=x(y(z-1)一N)+1,通过这个方程求小值解(k,pr-1,p+g)论文找出了r和α之间的关系,在这种关系下,通过解密指数d分解N存在多项式时间确定性算法。在原始RSA体制中,一般情况下都满足条件α·δ<1,所以结论较好。在prq形式的RSA变种,出现的结论并没有上述结论完美,论文对其进行了简单分析。更多还原

【Abstract】 As a widely used public key cryptosystcm, the security of RSA has been research focus of cryptography. People have conducted a comprehensive anal-ysis of the security of the RSA. in1990, Wiener [7] proved that for each pair of RSA key, if the condition d<1/3N1/4is satisfied, you can use the method of continued fraction factor N=p·q in deterministic polynomial time. Later. Coppersmith[8,18,20] proposed a method of seeking the root of the congru-ence equation using of lattice theory and the conclusions of the LLL algorithm, which been used to analyze the security of the RSA by Boneh、Durff[9] and May[5]. to get similar conclusions with Winner. Coppersmith’s method has formed a set of standardized steps with research of May and so on, and been widely used in analysis of RSA.One of the most fundamental problems concerning the RSA eryptosys-tenr:dose the knowlcadge of the RSA key pair (N,e,d) yield the factorization of N=p·q? It is well known that there is a probabilistic polynomial-time algorithm. and the deterministic polynomial time algorithm been constructed by J.Coron[1] and A.May until2007. Coron and May give a method of fac-toring N=p·q in deterministic polynomial time by using of Coppersmith’s method, the time complexity of their method is (?)(log9N).In Coron s paper, he used congruence equations U=e·d-1=0mod (?), φ(N)=N-s=0mod(?) s=p+q-1. and suppose we are given the; high-order bits s0of s, that is we can write s=x0+s0X,0≤X0<X for some X known to us. He constructed following polynomials with this congruence equations we can see that for all (i, j). Solving these polynomials with LLL algorithm he get that N can be factored in deterministic polynomial time since e· d<N2.In this paper, we further discuss relationship between p. q and analyse how it impact above conclusion. Normally, there arc strict requirement in RSA parameter selection for N, to avoiding N been factored by common fac-torization algorithm. One of these requirement is that p, q must be balanced, that is p,q have a same bits-length, or p-q is small. It can be seen that s=p+q-2(?) is small in this situation since p·q=N. Suppose we prove that we can factor N in deterministic polynomial time if α·δ<1.Our paper get the same conclusion with two different congruence equa-tions. Consider in RSA scheme, and suppose A=N+1-2(?), we use the congruence equations in the first method, and our target equation corresponding is Use the method mentioned in [3], we can construct following equations (see Chapter2for a detailead definition)with root (k,s). Solving these equa-tions with LLL algorithm, and with some analysis we can get our conclusion. The second method mentioned in our paper use a congruence equation witch is similar with the one in Coron’s paper. We present the process simply, then focus on the analysis with different assumptions and conditions and get the same conclusion with above method.In Chapter3, we analyse another type of RSA scheme. In this new situation there is a different RSA modulus pr q and so We also suppose p, q are balanced and construct congruence equation suppose U=e·d=Nα,the target equation corresponding is with root (k,pr-1,p+q). We find that we can factor N=pr q with d in deterministic polynomial time if r and α meet che condition in theorem of Chapter3.更多还原