ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Some Remarks on {L}ucas-Based Cryptosystems

Daniel Bleichenbacher and Wieb Bosma and Arjen K. Lenstra

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.