Factoring The RSA Modulus With Secret Key D

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.