New weak keys in RSA
Baocang Wang, Liu Shuanggen, Yupu Hu · Wuhan University Journal of Natural Sciences · 2006
The security of the RSA system with the prime pairs of some special form is investigated. A new special-purpose algorithm for factoring RSA numbers is proposed. The basic idea of the method is to factor RSA numbers by factoring a well-chosen quadratic polynomial with integral coefficients. When viewed as a general-purpose algorithm, the new algorithm has a high computational complexity. It is shown that the RSA number n=pq can be easily factored if p and q have the special form of p=as+b, q=cs+d , where a, b, c, d are relatively small numbers. Such prime pairs ( p, q ) are the weak keys of RSA, so when we generate RSA modulus, we should avoid using such prime pairs ( p, q ).