Skip to main content
Erschienen in: Journal of Applied Mathematics and Computing 1-2/2013

01.07.2013 | Computational mathematics

A new attack on RSA with two or three decryption exponents

verfasst von: Abderrahmane Nitaj

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2013

Einloggen

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

search-config
loading …

Abstract

Let N=pq be an RSA modulus, i.e. the product of two large unknown primes of equal bit-size. In this paper, we describe an attack on RSA in the presence of two or three exponents e i with the same modulus N and satisfying equations e i x i ϕ(N)y i =z i , where ϕ(N)=(p−1)(q−1) and x i , y i , z i are unknown parameters. The new attack is an extension of Guo’s continued fraction attack as well as the Blömer and May lattice-reduction basis attack.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Blömer, J., May, A.: A generalized Wiener attack on RSA. In: Public Key Cryptography—PKC 2004. Lecture Notes in Computer Science, vol. 2947, pp. 1–13. Springer, Berlin (2004) CrossRef Blömer, J., May, A.: A generalized Wiener attack on RSA. In: Public Key Cryptography—PKC 2004. Lecture Notes in Computer Science, vol. 2947, pp. 1–13. Springer, Berlin (2004) CrossRef
2.
Zurück zum Zitat Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N 0.292. In: Advances in Cryptology, Eurocrypt’99. Lecture Notes in Computer Science, vol. 1592, pp. 1–11. Springer, Berlin (1999) Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N 0.292. In: Advances in Cryptology, Eurocrypt’99. Lecture Notes in Computer Science, vol. 1592, pp. 1–11. Springer, Berlin (1999)
3.
Zurück zum Zitat Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997) MathSciNetMATHCrossRef Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997) MathSciNetMATHCrossRef
4.
Zurück zum Zitat Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford University Press, London (1965) Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford University Press, London (1965)
5.
Zurück zum Zitat Hinek, M.J., Lam, C.C.Y.: Common modulus attacks on small private exponent RSA and some fast variants (in practice). J. Math. Cryptol. 4(1), 58–93 (2010) MathSciNetMATHCrossRef Hinek, M.J., Lam, C.C.Y.: Common modulus attacks on small private exponent RSA and some fast variants (in practice). J. Math. Cryptol. 4(1), 58–93 (2010) MathSciNetMATHCrossRef
6.
Zurück zum Zitat Howgrave-Graham, N., Seifert, J.-P.: Extending Wiener’s attack in the presence of many decrypting exponents. In: Secure Networking—CQRE (Secure)’99. Lecture Notes in Computer Science, vol. 1740, pp. 153–166. Springer, Berlin (1999) Howgrave-Graham, N., Seifert, J.-P.: Extending Wiener’s attack in the presence of many decrypting exponents. In: Secure Networking—CQRE (Secure)’99. Lecture Notes in Computer Science, vol. 1740, pp. 153–166. Springer, Berlin (1999)
7.
Zurück zum Zitat Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978) MathSciNetMATHCrossRef Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978) MathSciNetMATHCrossRef
8.
9.
Zurück zum Zitat Sarkar, S., Maitra, S.: Cryptanalysis of RSA with more than one decryption exponent. Inf. Process. Lett. 110(8–9), 336–340 (2010) MathSciNetMATHCrossRef Sarkar, S., Maitra, S.: Cryptanalysis of RSA with more than one decryption exponent. Inf. Process. Lett. 110(8–9), 336–340 (2010) MathSciNetMATHCrossRef
Metadaten
Titel
A new attack on RSA with two or three decryption exponents
verfasst von
Abderrahmane Nitaj
Publikationsdatum
01.07.2013
Verlag
Springer-Verlag
Erschienen in
Journal of Applied Mathematics and Computing / Ausgabe 1-2/2013
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI
https://doi.org/10.1007/s12190-012-0618-0

Weitere Artikel der Ausgabe 1-2/2013

Journal of Applied Mathematics and Computing 1-2/2013 Zur Ausgabe