Cryptanalysis of RSA with Small Prime Combination

Let N = pq be RSA modulus where primes p and q are of the same bit-length. If |ρq - p| = N1/4+γwhere ρ is a known constant satisfying 1 ≤ ρ ≤ 2 and the constant γ satisfies 0 < γ < 1/4, we show the factorization attack on N and weak key attack against RSA modulus N. We present algorithms to find the factorization of N in time O(Nγ+e) by some square root attacks, such as the baby-step giant-step method and a more sophisticated square root attack. Using similar techniques of Blomer and May (PKC 2004), we present a weak key attack and find new weak keys over the work of Maitra and Sarkar (ISC 2008).