Factoring RSA moduli when a message is close to a multiple of the primes. Issue 3 (3rd July 2018)

• Record Type: Journal Article
• Authors: Akchiche, Omar; Khadir, Omar
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 3(2018)
• Page Start: 196
• Page End: 203
• Publication Date: 2018-07-03
• Subjects: Integer factorization problem -- RSA system -- Coppersmith's method -- public key cryptography; 11Y05 -- 94A60; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1529709
• Languages: English
• ISSNs: 2379-9927

Abstract

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.