main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.06.2015 | Original Research | Ausgabe 1-2/2015

# Implicit factorization of unbalanced RSA moduli

Zeitschrift:
Journal of Applied Mathematics and Computing > Ausgabe 1-2/2015
Autoren:
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.

### 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
• 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
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

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

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Zur Ausgabe