.png){kind=icon}
.png){kind=icon}
Return
A better bound for implicit factorization problem with shared middle bits
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-017-9176-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
RSA
implicit factorization problem
middle bits
lattice
Coppersmith's method
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K