Further results on implicit factoring in polynomial time (Q2268250)

The paper extends previous results of \textit{A. May} and \textit{M. Ritzenhofen} [PKC 2009, Lect. Notes Comput. Sci. 5443, 1--14 (2009; Zbl 1220.11152)] about the simultaneous factoring of two RSA numbers \(N_1=p_1q_1, N_2=p_2q_2\), where \(p_1,q_1,p_2,q_2\) are primes, \(p_1,p_2\) and moreover \(q_1,q_2\) with the same bitsize and \(p_1,p_2\) share \(t\) bits. While in the paper of May and Ritzenhofen the \(t\) bits are the Least Significant Bits (LSBs) of \(p_1,p_2\) in the present paper those common bits can be the Least Significant, the Most Significant (MSBs), some portion of the LSBs and the MSBs or even to be in the middle. It is worthwhile to point out that the \(t\) common bits are not known, therefore the problem differs from the problem of factoring \(N=pq\) assuming known some bits of \(p\), see \textit{R. Rivest} and \textit{A. Shamir} [Eurocrypt 1985, Lect. Notes Comput. Sci. 219, 31--34 (1986; Zbl 0589.94004)]. Theorem 2.1 (Section 2) gives the conditions under which \(N_1,N_2\) can be factored in polynomial time assuming that \(p_1,p_2\) share some LBSs as well as some MSBs. The used tools are lattice reduction and Gröbner basis. Corollary 1 studies the particular case when \(p_1,p_2\) share only some MSBs and Corollary 2 when they share some LSBs. In this last case the paper provides (Table 1 and Figure 1) the comparison among the results of Corollary 1, the results of May and Ritzenhofen and the experimental results. Section 3 considers the case when \(p_1,p_2\) share \(t\) bits at the middle and Section 4 when also some bits of \(q_1\) or \(q_2\) are also known. The paper includes six examples (for numbers \(N\) of bitsize 1000) with details of the different cases studied.