Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Applicable Algebra in Engineering, Communication and Computing
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 3/2018

21.08.2017 | Original Paper

Factoring RSA moduli with primes sharing bits in the middle

verfasst von: Omar Akchiche, Omar Khadir

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We address the problem of factoring a large RSA modulus \(N=pq\) with p and q sharing a portion of bits in the middle. New polynomial time algorithms for computing the prime decomposition of N under certain conditions are presented. As an application, several attacks against RSA system using this class of moduli with low public exponent are described. Our results suggest that such integers are not appropriate for cryptographic purposes.
Vorheriger Artikel LCD codes from adjacency matrices of graphs
Nächster Artikel Near-rings on digital Hopf groups

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Bach, E., Shallit, J.: Algorithmic Number Theory: Efficient Algorithms. MIT press, Cambridge (1996)MATH
2.
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key \(d\) less than \(N^{0.292}\). In: Stern, J. (ed.) Advances in Cryptology, EUROCRYPT’99, pp. 1–11. Springer, Berlin (1999)
3.
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key \(d\) less than \(N^{0.292}\). IEEE Trans. Inf. Theory 46(4), 1339–1349 (2000)MathSciNetCrossRefMATH
4.
5.
Boneh, D., Durfee, G., Frankel, Y.: An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds.) Advances in Cryptology, ASIACRYPT’98, pp. 25–34. Springer, Berlin (1998)CrossRef
6.
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)MathSciNetCrossRefMATH
7.
8.
9.
10.
Lenstra, A.K., Lenstra Jr., H.W.: The Development of the Number Field Sieve, vol 1554. Lecture Notes in Mathematics. Springer (1993)
11.
Lenstra Jr., H.W. : Factoring integers with elliptic curves. Ann. Math. 649–673 (1987)
12.
Pollard, J.M. :Theorems on factorization and primality testing. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 76. Cambridge University Press, pp. 521–528 (1974)
13.
14.
Pomerance, C.: The quadratic sieve factoring algorithm. In: Beth, T., Cot, N., Ingemarsson, I., (eds.), Advances in Cryptology, EUROCRYPT’84 . pp. 169–182 (1985)
15.
Rivest, R.L., Shamir, A.: Efficient factoring based on partial information. In: Pichler, F. (ed.) Advances in Cryptology, EUROCRYPT’85, pp. 31–34. Springer, Berlin (1985)
16.
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)MathSciNetCrossRefMATH
17.
Steinfeld, R., Zheng, Y.: An advantage of low-exponent RSA with modulus primes sharing least significant bits. In: Naccache, D. (ed.) Topics in Cryptology, CT-RSA 2001, pp. 52–62. Springer, Berlin (2001)CrossRef
18.
Steinfeld, R., Zheng, Y.: On the security of RSA with primes sharing least-significant bits. Appl. Algebra Eng. Commun. Comput. 15(3–4), 179–200 (2004)MathSciNetCrossRefMATH
19.
Sun, H.-M., Wu, M.-E., Steinfeld, R., Guo, J., Wang, H.: Cryptanalysis of short exponent RSA with primes sharing least significant bits. In: Franklin, M.K., Hui, L.C.K., Wong, D.S. (eds.) Cryptology and Network Security, CANS 2008, pp. 49–63. Springer, Berlin (2008)
20.
Sun, H.-M., Wu, M.-E., Wang, H., Guo, J.: On the improvement of the BDF attack on LSBS-RSA. In: Mu, Y., Susilo, W., Seberry, J. (eds.) Information Security and Privacy, ACISP 2008, pp. 84–97. Springer, Berlin (2008)CrossRef
21.
22.
Zhao, Y.-D., Qi, W.-F.: Small private-exponent attack on RSA with primes sharing bits. In: Garay, J.A., Lenstra, A.K., Mambo, M., Peralta, R. (eds.) Information Security, ISC 2007, pp. 221–229. Springer, Berlin (2007)
Metadaten
Titel
Factoring RSA moduli with primes sharing bits in the middle
verfasst von
Omar Akchiche
Omar Khadir
Publikationsdatum
21.08.2017
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 3/2018
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-017-0340-0

Weitere Artikel der Ausgabe 3/2018

Applicable Algebra in Engineering, Communication and Computing 3/2018 Zur Ausgabe

Original Paper

Two infinite classes of rotation symmetric bent functions with simple representation

Original Paper

Two classes of linear codes and their weight distributions

Original Paper

Near-rings on digital Hopf groups

Original Paper

LCD codes from adjacency matrices of graphs