Overview and security analysis of RSA-type cryptosystems against various attacks

Marc Joye and Jean-Jacques Quisquater
UCL Crypto Group, Université de Louvain

In 1978, Rivest, Shamir and Adleman introduced the so-called RSA cryptosystem. Its security mainly relies on the difficulty of factoring large numbers. More recently, Koyama, Maurer, Okamoto and Vanstone and later Demytko pointed out new one-way trapdoor functions similar to RSA on elliptic curves over the ring Zn. The resulting cryptosystems are respectively called KMOV (from the last names of their inventors) and Demytko. On the other hand, Smith proposed to use Lucas sequences in order to produce LUC, an alternative to the RSA.

Due to its popularity, the original RSA was subject to an extensive cryptanalysis. Most of these attacks were more or less successfully extended to their Lucas-based and elliptic curves analogues.

In this paper, we survey for the first time a collection of attacks against the RSA and its variations. We also give an analysis in terms of security in order to choose the most adequate RSA system for a given application.

Marc Joye (joye@agel.ucl.ac.be)
Last modified: Mon Nov 4 10:28:45 MET 1996