Login New user?  
01-Applied Mathematics & Information Sciences
An International Journal


Volumes > Volume 11 > No. 1


Factoring RSA Modulus with Primes not Necessarily Sharing Least Significant Bits

PP: 243-249
Hatem M. Bahig, Dieaa I. Nassr, Ashraf Bhery,
The security of many public-key cryptosystems, such as RSA, is based on the difficulty of factoring a composite integer. Until now, there is no known polynomial time algorithm to factor any composite integer with classical computers. In this paper, we study factoring n when n= pq is a product of two primes p and q satisfying that p≡lk1 mod 2q1 and q≡lk2 mod 2q2 for some positive integers q1,q2, k1, k2 ≤ logn and l.We show that n can be factored in time polynomial in logn if l < 2q and either | p−lk1 2q1 || q−lk2 2q2 |< lk or 2q ′ ≥ n1/4, where q = min{q1,q2}, q ′ = max{q1,q2} and k = min{k1, k2}. We also show that the result of Steinfeld and Zheng [21] when the two primes p and q share least significant bits is a special case of our results. Our results point out the warring for cryptographic designers to be careful when generating primes for the RSA modulus

  Home   About us   News   Journals   Conferences Contact us Copyright naturalspublishing.com. All Rights Reserved