A new attack on three variants of the RSA cryptosystem

Authors

Martin W. Bunder, University of WollongongFollow
Abderrahmane Nitaj, Universite de Caen
Willy Susilo, University of WollongongFollow
Joseph Tonien, University of WollongongFollow

RIS ID

106716

Publication Details

Bunder, M. W., Nitaj, A., Susilo, W. & Tonien, J. (2016). A new attack on three variants of the RSA cryptosystem. Lecture Notes in Computer Science, (9723), 258-268. Melbourne, Australia 21st Australasian Conference, ACISP 2016.

Abstract

In 1995, Kuwakado, Koyama and Tsuruoka presented a new RSA-type scheme based on singular cubic curves y² ≡ x³+bx² (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 = PQ 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 public exponent e is an integer satisfying the key equation ed - k(p²-1) (q²-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.