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