Skip to main content
placeholder image

Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves

Journal Article


Abstract


  • © 2018 Elsevier Ltd In this paper, we apply the continued fraction method to launch an attack on the three RSA-type cryptosystems when the private exponent d is sufficiently small. The first cryptosystem, proposed by Kuwakado, Koyama and Tsuruoka in 1995, is a scheme based on singular cubic curves y 2 =x 3 +bx 2 (modN) where N=pq is an RSA modulus. The second cryptosystem, proposed by Elkamchouchi, Elshenawy and Shaban in 2002, is 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. The third cryptosystem, proposed by Castagnos in 2007, is a scheme over quadratic field quotients with an RSA modulus N=pq based on Lucas sequences. In the three cryptosystems, the public exponent e is an integer satisfying the key equation ed−k(p 2 −1)(q 2 −1)=1. Our attack is applicable to primes p and q of arbitrary sizes and we do not require the usual assumption that p and q have the same bit size. Thus, this is an extension of our recent result presented at ACISP 2016 conference. Our experiments demonstrate that for a 513-bit prime p and 511-bit prime q, our method works for values of d of up to 520 bits.

Publication Date


  • 2018

Citation


  • Bunder, M., Nitaj, A., Susilo, W. & Tonien, J. (2018). Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves. Journal of Information Security and Applications, 40 193-198.

Scopus Eid


  • 2-s2.0-85046026711

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/1449

Number Of Pages


  • 5

Start Page


  • 193

End Page


  • 198

Volume


  • 40

Place Of Publication


  • United Kingdom

Abstract


  • © 2018 Elsevier Ltd In this paper, we apply the continued fraction method to launch an attack on the three RSA-type cryptosystems when the private exponent d is sufficiently small. The first cryptosystem, proposed by Kuwakado, Koyama and Tsuruoka in 1995, is a scheme based on singular cubic curves y 2 =x 3 +bx 2 (modN) where N=pq is an RSA modulus. The second cryptosystem, proposed by Elkamchouchi, Elshenawy and Shaban in 2002, is 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. The third cryptosystem, proposed by Castagnos in 2007, is a scheme over quadratic field quotients with an RSA modulus N=pq based on Lucas sequences. In the three cryptosystems, the public exponent e is an integer satisfying the key equation ed−k(p 2 −1)(q 2 −1)=1. Our attack is applicable to primes p and q of arbitrary sizes and we do not require the usual assumption that p and q have the same bit size. Thus, this is an extension of our recent result presented at ACISP 2016 conference. Our experiments demonstrate that for a 513-bit prime p and 511-bit prime q, our method works for values of d of up to 520 bits.

Publication Date


  • 2018

Citation


  • Bunder, M., Nitaj, A., Susilo, W. & Tonien, J. (2018). Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves. Journal of Information Security and Applications, 40 193-198.

Scopus Eid


  • 2-s2.0-85046026711

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers1/1449

Number Of Pages


  • 5

Start Page


  • 193

End Page


  • 198

Volume


  • 40

Place Of Publication


  • United Kingdom