Paper Info
Title
Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves.
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 y2=x3+bx2(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(p2−1)(q2−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.
Year
DOI
Venue
2018
10.1016/j.jisa.2018.04.006
Journal of Information Security and Applications
Keywords
Field
DocType
RSA,Elliptic curves,Continued fractions,Coppersmith’s technique
Integer,Prime (order theory),Discrete mathematics,Gaussian integer,Lucas sequence,Exponent,Computer science,Cryptosystem,Theoretical computer science,Elliptic curve,Quadratic field
Journal
Volume
ISSN
Citations 
40
2214-2126
0
PageRank 
References 
Authors
0.34
3
4
Name
Order
Citations
PageRank
Martin Bunder1153.01
Abderrahmane Nitaj27215.00
Willy Susilo34823353.18
Joseph Tonien400.68