|
|
 |
| |
|
|
|
Factoring RSA Modulus with Primes not Necessarily Sharing Least Significant Bits |
|
|
|
PP: 243-249 |
|
|
|
doi:10.18576/amis/110130
|
|
|
|
Author(s) |
|
|
|
Hatem M. Bahig,
Dieaa I. Nassr,
Ashraf Bhery,
|
|
|
|
Abstract |
|
|
| 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 |
|
|
|
|
|
|
|
