Skip to main content
placeholder image

A new attack on three variants of the RSA cryptosystem

Conference Paper


Abstract


  • In 1995, Kuwakado, Koyama and Tsuruoka presented a new RSA-type scheme based on singular cubic curves y2 = x3 + bx2 (mod N) where N = pq is an RSA modulus. Then, in 2002, Elkamchouchi, Elshenawy and Shaban introduced an extension of the RSA scheme to the field of Gaussian integers using a modulus N = PQ where P and Q are Gaussian primes such that p = |P| and q = |Q| are ordinary primes. Later, in 2007, Castagnos proposed a scheme over quadratic field quotients with an RSA modulus N = pq. In the three schemes, the public exponent e is an integer satisfying the key equation ed - k (p2 - 1) (q2 - 1) = 1. In this paper, we apply the continued fraction method to launch an attack on the three schemes when the private exponent d is sufficiently small. Our attack can be considered as an extension of the famous Wiener attack on the RSA.

Publication Date


  • 2016

Citation


  • Bunder, M., Nitaj, A., Susilo, W., & Tonien, J. (2016). A new attack on three variants of the RSA cryptosystem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 9723 (pp. 258-268). doi:10.1007/978-3-319-40367-0_16

Scopus Eid


  • 2-s2.0-84978821812

Web Of Science Accession Number


Start Page


  • 258

End Page


  • 268

Volume


  • 9723

Abstract


  • In 1995, Kuwakado, Koyama and Tsuruoka presented a new RSA-type scheme based on singular cubic curves y2 = x3 + bx2 (mod N) where N = pq is an RSA modulus. Then, in 2002, Elkamchouchi, Elshenawy and Shaban introduced an extension of the RSA scheme to the field of Gaussian integers using a modulus N = PQ where P and Q are Gaussian primes such that p = |P| and q = |Q| are ordinary primes. Later, in 2007, Castagnos proposed a scheme over quadratic field quotients with an RSA modulus N = pq. In the three schemes, the public exponent e is an integer satisfying the key equation ed - k (p2 - 1) (q2 - 1) = 1. In this paper, we apply the continued fraction method to launch an attack on the three schemes when the private exponent d is sufficiently small. Our attack can be considered as an extension of the famous Wiener attack on the RSA.

Publication Date


  • 2016

Citation


  • Bunder, M., Nitaj, A., Susilo, W., & Tonien, J. (2016). A new attack on three variants of the RSA cryptosystem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 9723 (pp. 258-268). doi:10.1007/978-3-319-40367-0_16

Scopus Eid


  • 2-s2.0-84978821812

Web Of Science Accession Number


Start Page


  • 258

End Page


  • 268

Volume


  • 9723