Name
Abstract | ||
|---|---|---|
In this paper, we revisit the problem of factoring RSA moduli with implicit hint, where primes of two RSA moduli share some number of middle bits. Suppose that for two n-bit RSA moduli $$N_1=p_1q_1$$N1=p1q1 and $$N_2=p_2q_2$$N2=p2q2, $$q_1$$q1 and $$q_2$$q2 are $$\\alpha n$$αn-bit primes, $$p_1$$p1 and $$p_2$$p2 share tn bits at positions from $$t_1n$$t1n to $$t_2n=t_1+tn$$t2n=t1+tn. Faug$$\\grave{e}$$e`re et al. PKC 2010 showed that when $$t\\ge 4\\alpha $$t﾿4α, one can factor $$N_1$$N1 and $$N_2$$N2 in polynomial time. In this paper, we improve this bound to $$t>4\\alpha -3\\alpha ^2$$t>4α-3α2 by presenting a new method of solving a homogeneous linear equation modulo unknown divisors. Our method is verified by experiments. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-22425-1_5 | International Workshop on Security |
Keywords | Field | DocType |
RSA modulus,Factorization with implicit hint,Coppersmith's technique,Middle bit | Discrete mathematics,Linear equation,Computer science,Homogeneous,Computer security,Modulo,Factorization,Moduli,Time complexity,Divisor | Conference |
Volume | ISSN | Citations |
9241 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 9 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liqiang Peng | 1 | 38 | 8.37 |
| Lei Hu | 2 | 109 | 12.21 |
| Yao Lu | 3 | 1 | 0.35 |
| Zhangjie Huang | 4 | 19 | 4.02 |
| Jun Xu | 5 | 18 | 6.22 |