Computation of Private Key Based on Divide-By-Prime for Luc Cryptosystems

Problem statement: One of the public key cryptosystem is Luc cryptosystems. This system used Lucas Function for encryption and decryption process. Lucas Function is a special form of second-order linear recurrence relation. An encyption process is used to encrypt an original message to ciphertext by using public key. A decryption process is the process to decrypt a ciphertext into original message using private key. The existing algorithm on computing private key computation involved some redundant computations. Approach: In this study, an efficient algorithm to compute private key for Luc cryptosystem is developed. The Extended Euclidean Algorithm will be enhanced by implementing Divide-By-Prime in its computations. The comparison is focused on the computation time by the existing and new algorithms. The more efficient algorithm means the better computation time. The shorter computation time the better algorithm. Results: A new algorithm shows better computation time. In all experiments, the computation time by new algorithm is always better than the existing algorithm. Conclusion: The new computation algorithm that based on Divide-By-Prime provided better efficiency of decryption process compared to the existing algorithm.