Some Remarks on Lucas-Based Cryptosystems

Daniel Bleichenbacher, Wieb Bosma, and Arjen K. Lenstra

Advances in Cryptology — CRYPTO '95, Lecture Notes in Computer Science, Springer-Verlag, vol. 963, pp. 386–396, Aug 1995.

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 proerties their re-inventors were apparently not aware of. In particular, we present a chosen-message forgery for 'LUC', and we show that 'LUCELG' and 'LUCDIF' are vulnerable to subexponential time attacks. This proves that various claims that were made about Lucas-based cryptosystems are incorrect.

BibTeX Citation

@inproceedings{BlBoLe95,
    author       = {Daniel Bleichenbacher and Wieb Bosma and Arjen K. Lenstra},
    title        = {Some Remarks on {L}ucas-Based Cryptosystems},
    editor       = {Don Coppersmith},
    booktitle    = {Advances in Cryptology --- CRYPTO~'95},
    pages        = {386--396},
    series       = {Lecture Notes in Computer Science},
    volume       = {963},
    year         = {1995},
    month        = {8},
    publisher    = {Springer-Verlag},
}