Some remarks on Lucas-Based cryptosystems

We review the well-known relation between Lucas sequences and exponentiation. This leads to the observation that certain public-key cryptosystems that are based on the use of Lucas sequences have some elementary properties their re-inventors were apparently not aware of. In particular, we present a chosen-message forgery for LUC' [Smith, 1993] and [Smith and Lennon, 1993], and we show that LUCELG' and `LUCDIF' [Smith, 1994] and [Smith and Skinner, 1994] are vulnerable to subexponential time attacks. This proves that various claims that were made about Lucas-based cryptosystems are incorrect