Factoring RSA moduli when a message is close to a multiple of the primes

摘要

Let N = pq be an RSA modulus. Assume that we are given the ciphertext of a message that is close to a multiple of the divisors of N. We show that it is possible to factor N in polynomial time in log N when a low public exponent is used. The idea is generalized to some RSA variants and Rabin system.