At PKC 2009, May and Ritzenhofen proposed the implicit factorization problem (IFP). They showed that it is undemanding to factor two h-bit RSA moduli N1=p1q1, N2=p2q2 where q1, q2 are both αh-bit, and p1, p2 share uh>2αh the least significant bits (LSBs). Subsequent works mainly focused on extending the IFP to the cases where p1, p2 share some of the most significant bits (MSBs) or the middle bits (MBs). In this paper, we propose a novel generalized IFP where p1 and p2 share an arbitrary number of bit blocks, with each block having a consistent displacement in its position between p1 and p2, and we solve it successfully based on Coppersmith’s method. Specifically, we generate a new set of shift polynomials to construct the lattice and optimize the structure of the lattice by introducing a new variable z=p1. We derive that we can factor the two moduli in polynomial time when u>2(n+1)α(1−α^1/(n+1)) with p1, p2 sharing n blocks. Further, no matter how many blocks are shared, we can theoretically factor the two moduli as long as u>2αln(1/α). In addition, we consider two other cases where the positions of the shared blocks are arbitrary or there are k>2 known moduli. Meanwhile, we provide the corresponding solutions for the two cases. Our work is verified by experiments.

Let (N,e) be a public key of the RSA cryptosystem, and d be the corresponding private key. In practice, we usually choose a small e for quick encryption. In this paper, we improve partial private key exposure attacks against RSA with a small public exponent e. The key idea is that under such a setting we can usually obtain more information about the prime factor of N and then by solving a univariate modular polynomial with Coppersmith's method, N can be factored in polynomial time. Compared to previous results, we reduce the number of d's leaked bits needed to mount the attack by log_2 (e) bits. Furthermore, our experiments show that for 1024-bit N, our attack can achieve the theoretical bound on a personal computer, which verified our attack.