A New Attack on Three Variants of the RSA Cryptosystem
In 1995, Kuwakado, Koyama and Tsuruoka presented a new RSA-type scheme based on singular cubic curves \(y^2\equiv x^3+bx^2\pmod N\) where \(N=pq\) is an RSA modulus. Then, in 2002, Elkamchouchi, Elshenawy and Shaban introduced an extension of the RSA sche
- PDF / 192,215 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 214 Views
School of Mathematics and Applied Statistics, University of Wollongong, Wollongong, Australia [email protected] 2 D´epartement de Math´ematiques, Universit´e de Caen, Caen, France [email protected] 3 School of Computing and Information Technology, Centre for Computer and Information Security Research, University of Wollongong, Wollongong, Australia {wsusilo,joseph tonien}@uow.edu.au
Abstract. In 1995, Kuwakado, Koyama and Tsuruoka presented a new RSA-type scheme based on singular cubic curves y 2 ≡ 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 = P Q 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 exponent e is an integer satisfying the key equa public tion ed − k p2 − 1 q 2 − 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.
Keywords: RSA
1
· Elliptic curves · Continued fractions
Introduction
The public key cryptosystem RSA was introduced by Rivest, Shamir and Adleman [10] in 1978. It is the most popular and widely used public-key cryptosystem. The RSA operations system are based on modular arithmetic. Let p and q be two large primes. The product N = pq is called the RSA modulus and the product φ(N ) = (p − 1)(q − 1) is the Euler totient function. In RSA, the public exponent e and the private exponent d are integers satisfying ed ≡ 1 (mod φ(N )). A message m is encrypted as c ≡ me (mod N ) and decrypted using m ≡ cd (mod N ). Since its introduction, the RSA cryptosystem has been generalized in various ways, including extensions to singular elliptic curves and Gaussian integers. c Springer International Publishing Switzerland 2016 J.K. Liu and R. Steinfeld (Eds.): ACISP 2016, Part II, LNCS 9723, pp. 258–268, 2016. DOI: 10.1007/978-3-319-40367-0 16
A New Attack on Three Variants of the RSA Cryptosystem
259
In 1995, Kuwakado, Koyama and Tsuruoka [8] presented a new RSA-type scheme based on singular cubic curves with equation y 2 ≡ x3 + bx2 (mod N ) where N = pq is an RSA ∈ Z/N Z. The public exponent is an and b modulus integer e such that gcd e, p2 − 1 q2 − 1 = 1 and the decryption exponent is wededuce that e and the integer d ≡ e−1 (mod p2 − 1 q 2 − 1 ). From this, d satisfy a key equation of the form ed − k p2 − 1 q 2 − 1 = 1 where k is a positive integer. In 2002, Elkamchouchi, Elshenawy and Shaban [5] introduced an extension of RSA to the ring of Gaussian integers. A Gaussian integer is a complex number of the form a + ib where both a and b are integers and i2 = −1. The set of all Gaussian integers is denoted Z[i]. A Gaussian prime number is a Gaussian integer that cannot be
Data Loading...