Information Security and Cryptography Research Group

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},
}