An Attack on the Lucas Based El-Gamal Cryptosystem in the Elliptic Curve Group Over Finite Field Using Greater Common Divisor

Authors: Lee Feng Koo, Tze Jin Wong, Pang Hung Yiu, Nik Mohd Asri Nik Long

Abstract:

Greater common divisor (GCD) attack is an attack that relies on the polynomial structure of the cryptosystem. This attack required two plaintexts differ from a fixed number and encrypted under same modulus. This paper reports a security reaction of Lucas Based El-Gamal Cryptosystem in the Elliptic Curve group over finite field under GCD attack. Lucas Based El-Gamal Cryptosystem in the Elliptic Curve group over finite field was exposed mathematically to the GCD attack using GCD and Dickson polynomial. The result shows that the cryptanalyst is able to get the plaintext without decryption by using GCD attack. Thus, the study concluded that it is highly perilous when two plaintexts have a slight difference from a fixed number in the same Elliptic curve group over finite field.

Keywords: Decryption, encryption, elliptic curve, greater common divisor.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.2643937

References:

[1] W. Diffie, and M. Hellman, "New directions in cryptography". IEEE Transaction on Information Theory vol. 22, p644-654, 1976.
[2] T. ElGamal, "A Public Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms". IEEE Transaction on Information Theory vol. 31, p469-472, 1985.
[3] N. Koblitz. "Elliptic curve cryptosystems". Mathematics of Computation 48 (177): p203–209, 1985.
[4] V. Miller. "Use of elliptic curves in cryptography". CRYPTO 85: p417–426, 1985.
[5] P. J. Smith, and C. Skinner, "A Public Key Cryptosystem and A Digital Signature Systems Based on the Lucas Function Analogue to Discrete Logarithms". Pre-proceedings Asia Crypt'94, p298-306, 1994.
[6] P. J. Smith and M. J. J. Lennon. "LUC: A new public key system". Proceedings of the ninth IFIP international Symposium on Computer Security, p103-117, 1993.
[7] M. R. M. Said. "Application of Recurrence Relations to Cryptography". PhD Thesis, Macquarie University, Australia, 1997.
[8] T. J. Wong. “A RSA-type Cryptosystem Based on Quartic Polynomials". PhD Thesis, Universiti Putra Malaysia, Malaysia, 2011.
[9] 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 vol. 1(1), p63-81, 2007.
[10] L. E. Dickson. “The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group.” The Annals of Mathematics 11(1/6): p65–120; 161–183, 1897.
[11] T. J. Wong, M. R. M. Said, M. Othman, and L. F. Koo, “A Lucas based cryptosystem analog to the ElGamal cryptosystem and elliptic curve cryptosystem”. AIP Conference Proceedings vol. 1635, p256-259, 2014.
[12] T. J. Wong, L. F. Koo, and P. H. Yiu. “On the Wiener’s Attack into Lucas Based El- Gamal Cryptosystem in the Elliptic Curve Over Finite Field”. International Journal of Science and Engineering Investigations vol 7(72), p37-39, 2018.
[13] T. J. Wong, L. F. Koo, and P. H. Yiu. “Lucas Based El-Gamal Cryptosystem in the Elliptic CurveGroup over finite field under Lenstra’s Attack”. Asian Journal of Mathematics and Computer Research vol. 23(4), p207-213, 2018.