Factoring RSA moduli when a message is close to a multiple of the primes. Issue 3 (3rd July 2018) - Akchiche, Omar; Khadir, Omar
ABSTRACT: 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 when a low public exponent is used. The idea is generalized to some RSA variants and Rabin system.