Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves. (June 2018)

• Record Type: Journal Article
• Authors: Bunder, Martin; Nitaj, Abderrahmane; Susilo, Willy; Tonien, Joseph
• Is Part Of: Journal of information security and applications. Volume 40(2018)
• Page Start: 193
• Page End: 198
• Publication Date: 2018-06
• Subjects: RSA -- Elliptic curves -- Continued fractions -- Coppersmith's technique; 94A60 -- 11Y05; Computer security -- Periodicals; Information technology -- Security measures -- Periodicals; 005.805
• DOI: 10.1016/j.jisa.2018.04.006
• Languages: English
• ISSNs: 2214-2126

Abstract

Abstract: 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 + b x 2 ( mod N ) where N = p q 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 = P Q 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 = p q based on Lucas sequences. In the three cryptosystems, the public exponent e is an integer satisfying the key equation e d − 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.