Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves
RIS ID
127095
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 Details
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.