Cryptographic Attack on Lucas Based Cryptosystems Using Chinese Remainder Theorem

Lenstra’s attack uses Chinese remainder theorem as a tool and requires a faulty signature to be successful. This paper reports on the security responses of fourth and sixth order Lucas based (LUC_4,6) cryptosystem under the Lenstra’s attack as compared to the other two Lucas based cryptosystems such as LUC and LUC₃ cryptosystems. All the Lucas based cryptosystems were exposed mathematically to the Lenstra’s attack using Chinese Remainder Theorem and Dickson polynomial. Result shows that the possibility for successful Lenstra’s attack is less against LUC_4,6 cryptosystem than LUC₃ and LUC cryptosystems. Current study concludes that LUC_4,6 cryptosystem is more secure than LUC and LUC₃ cryptosystems in sustaining against Lenstra’s attack.

Authors:

• Tze Jin Wong
• Lee Feng Koo
• Pang Hung Yiu

Keywords:

• Lucas sequence
• Dickson Polynomial
• faulty signature
• corresponding signature
• congruence.

References:

[1] D. Bleichenbacher, W. Bosma, and A. K. Lenstra, “Some remarks on Lucas-Based Cryptosystems”, Lecture Notes in Computer Science 963:386-396, 1995.
[2] W. Diffie, and M. Hellman, “New directions in cryptography”, IEEE Transaction on Information Theory 22: 644-654, 1976.
[3] M. Joye, “Security Analysis of RSA-type Cryptosystems”. PhD Thesis, Universite Catholique de Louvain, Belgium, 1997.
[4] M. Joye, “On the importance of securing your bins: The garbage-man-in-the-middle attack”, Proceeding of the 4th ACM Coference on Computer and Communications Security, ACM press, 135-141, 1997.
[5] R. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communication of the ACM 21: 120-126, 1978.
[6] M. R. M. Said, “Application of Recurrence Relations to Cryptography”. PhD Thesis, Macquarie University, Australia, 1997.
[7] M. R. M. Said and L. John, “A Cubic Analogue of the RSA Cryptosystem”, Bulletin of the Australia Mathematical Society 68: 21-38, 2003.
[8] P. J. Smith and M. J. J. Lennon, “LUC: A New Public Key System”, Proceedings of the Ninth IFIP International Symposium on Computer Security: 103-117, 1993.
[9] H. C. Williams, “On a Generalization of the Lucas Functions”, Acta Arithmetica 20: 33-51, 1972.
[10] T. J. Wong, “A RSA-type Cryptosytem Based on Quartic Polynomials”, PhD Thesis, Universiti Putra Malaysia, Malaysia, 2011.
[11] T. J. Wong, M. R. M. Said, K. A. M. Atan, and B. Ural, “The Quartic Analog to the RSA Cryptosystem”, Malaysian Journal of Mathematical Sciences 1(1), 63-81, 2007.
[12] T. J. Wong, M. R. M. Said, M. Othman, and K.A.M. Atan, “Garbage-Man-In-The-Middle Attack on the LUC4 Cryptosystem”, International Journal of Cryptology Research 1(1), 33-41, 2009.
[13] T. J. Wong, M. R. M. Said, M. Othman, and K.A.M. Atan, “GCD Attack on the LUC4 Cryptosystem”, International Journal of Cryptology Research 1(2), 179-189, 2009.
[14] T. J. Wong, H. Kamarulhali, and M. R. M. Said, “On the Hastad's Attack to LUC4,6 Cryptosystem and compared with Other RSA-Type Cryptosystem”. Malaysian Journal of Mathematical Science 7(S), 1-17, 2013.