Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

01-06-2015 | Original Research | Issue 1-2/2015

Journal of Applied Mathematics and Computing 1-2/2015

Implicit factorization of unbalanced RSA moduli

Journal:
Journal of Applied Mathematics and Computing > Issue 1-2/2015
Authors:
Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin

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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 1-2/2015

Journal of Applied Mathematics and Computing 1-2/2015 Go to the issue

Premium Partner

    Image Credits