Paper 2014/548

Implicit factorization of unbalanced RSA moduli

Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin

Abstract

Let N1 = p1q1 and N2 = p2q2 be two RSA moduli, not necessarily of the same bit-size. In 2009, May and Ritzenhofen proposed a method to factor N1 and N2 given the implicit information that p1 and p2 share an amount of least significant bits. In this paper, we propose a generalization of their attack as follows: suppose that some unknown multiples a1p1 and a2p2 of the prime factors p1 and p2 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 N1 and N2. Using simultaneous diophantine approximations and lattice reduction, we extend the method to factor k >= 3 RSA moduli Ni = piqi, i = 1, . . . , k given the implicit information that there exist unknown multiples a1p1, . . . , akpk sharing an amount of their MSBs or their LSBs. Also, this paper extends many previous works where similar results were obtained when the pi's share their MSBs or their LSBs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Journal of Applied Mathematics and Computing
Keywords
integer factorizationcontinued fractionslattice reduction
Contact author(s)
rezal @ upm edu my
History
2014-07-18: received
Short URL
https://ia.cr/2014/548
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/548,
      author = {Abderrahmane Nitaj and Muhammad Rezal Kamel Ariffin},
      title = {Implicit factorization of unbalanced RSA moduli},
      howpublished = {Cryptology ePrint Archive, Paper 2014/548},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/548}},
      url = {https://eprint.iacr.org/2014/548}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.