A better bound for implicit factorization problem with shared middle bits

作者：Wang, Shixiong; Qu, Longjiang^*; Li, Chao; Fu, Shaojing

来源：Science China Information Sciences, 2018, 61(3): 032109.

DOI：10.1007/s11432-017-9176-5

• RSA
• implicit factorization problem
• middle bits
• lattice
• Coppersmith's method

This paper presents our investigation of the implicit factorization problem, where unknown prime factors of two RSA moduli share a certain number of middle bits. The problem is described as follows. Let N-1 = p1q1, N-2 = p2q2 be two different n-bit RSA moduli, where q1, q2 are both alpha n- bit prime integers. Suppose that p1, p2 share tn bits at positions from t(1)n to t(2)n = ( t(1) + t) n. Then this problem focuses on the condition about t, alpha to factor N-1, N-2 efficiently. At PKC 2010, Faug` ere et al. showed that N1, N2 can be factored when t > 4 alpha. Subsequently, in 2015, Peng et al. improved this bound to t > 4 alpha- 3 alpha(2). In this paper, we directly apply Coppersmith's method to the implicit factorization problem with shared middle bits, and a better bound t > 4 alpha - 4 alpha(3/2) is obtained. The correctness of our approach is verified by experiments.

• 出版日期2018-3
• 单位中国人民解放军国防科学技术大学