Name
Abstract | ||
|---|---|---|
Let \(N_{1} = p_{1}q_{1}\) and \(N_{2} = p_{2}q_{2}\) be two RSA moduli, not necessarily of the same bit-size. In 2009, May and Ritzenhofen proposed a method to factor \(N_{1}\) and \(N_{2}\) given the implicit information that \(p_{1}\) and \(p_{2}\) share an amount of least significant bits. In this paper, we propose a generalization of their attack as follows: suppose that some unknown multiples \(a_{1}p_{1}\) and \(a_{2}p_{2}\) of the prime factors \(p_{1}\) and \(p_{2}\) share an amount of their Most Significant Bits (MSBs) or an amount of their Least Significant Bits (LSBs). Using a method based on the continued fraction algorithm, we propose a method that leads to the factorization of \(N_{1}\) and \(N_{2}\). Using simultaneous diophantine approximations and lattice reduction, we extend the method to factor \(k\ge 3\) RSA moduli \(N_{i}=p_{i}q_{i}, i=1,\ldots ,k\) given the implicit information that there exist unknown multiples \(a_{1}p_{1}, \ldots , a_kp_k\) sharing an amount of their MSBs or their LSBs. Also, this paper extends many previous works where similar results were obtained when the \(p_{i}\)’s share their MSBs or their LSBs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s12190-014-0806-1 | IACR Cryptology ePrint Archive |
Keywords | Field | DocType |
94A60, 11Y05 | Discrete mathematics,Factorization,Moduli,Prime factor,Diophantine equation,Lattice reduction,Mathematics | Journal |
Volume | Issue | ISSN |
2014 | 1-2 | 1865-2085 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abderrahmane Nitaj | 1 | 72 | 15.00 |
| Muhammad Rezal Kamel Ariffin | 2 | 3 | 8.30 |