Cryptanalysis of RSA-type cryptosystems: A visit
Marc Jóye, Jean-Jacques Quisquater · DIMACS series in discrete mathematics and theoretical computer science · 1997
. This paper surveys RSA-type implementations based on Lucas sequences and on elliptic curves. The main focus is the way how some known attacks on RSA were extended to LUC, KMOV and Demytko's system. It also gives some directions for the choice of the most appropriate RSA-type system for a given application. 1. INTRODUCTION In 1978, Rivest, Shamir and Adleman [63] introduced the so-called RSA cryptosystem. Its security mainly relies on the difficulty of factoring carefully chosen large integers. After this breakthrough, other structures were proposed to produce analogues to RSA. So, Muller and Nobauer [54, 55] presented a cryptosystem using Dickson polynomials. This system was afterwards slightly modified and rephrased in terms of Lucas sequences by Smith and Lennon [70, 72]. More recently, Koyama, Maurer, Okamoto and Vanstone [41] exhibited new one-way trapdoor functions similar to RSA on elliptic curves, the so-called KMOV cryptosystem. Later, Demytko [20] also pointed out a new one-...