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

DOWNLOAD

REPORT


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