A Method for Solving Generalized Implicit Factorization Problem

摘要

The problem of factoring RSA moduli with the implicit hint was firstly proposed by May and Ritzenhofen at PKC'09 where unknown prime factors of several RSA moduli shared some number of least significant bits (LSBs), and was later considered by Faugere et al. where some most significant bits (MSBs) were shared between the primes. Recently, Nitaj and Ariffin proposed a generalization of the implicit factorization problem. Let N_1 = p_1q_1 and N_2 = p_2q_2 be two distinct RSA moduli, Nitaj and Ariffin showed that when a_1p_1 and a_2p_2 share enough bits, N_1 , N_2 can be factored in polynomial time, where a_1 and a_2 are some unknown positive integers. They also extended their work to the case of k( ≥ 3) moduli. In this paper, we revisit Nitaj-Ariffin's work and transform the problem into solving small roots of a modular equation. Then by utilizing Coppersmith's method, for the case of two moduli we improve Nitaj-Ariffin's result when the unknowns a_1 , a_2 are relatively small, and our result is always better than Nitaj-Ariffin's result for the case of k( ≥ 3) moduli.