1. MMC
  2. All Volumes and Issues
  3. Volume 11, Number 4, 2024
  4. An attack on ELG-LUC3-ECC cryptosystem using Hastad's and Julta's theorem

An attack on ELG-LUC3-ECC cryptosystem using Hastad's and Julta's theorem

MMC.
2024;
Volume 11, Number 4
: pp. 1135–1140
https://doi.org/10.23939/mmc2024.04.1135
Received: July 21, 2024
Accepted: November 25, 2024

Wong T. J., Koo L. F., Sathar M. H. A., Rasedee A. F. N., Sarbini I. N.  An attack on ELG-LUC3-ECC cryptosystem using Hastad's and Julta's theorem.  Mathematical Modeling and Computing. Vol. 11, No. 4, pp. 1135–1140 (2024)

Authors:
  1. T. J. Wong
  2. L. F. Koo
  3. M. H. A. Sathar
  4. A. F. N. Rasedee
  5. I. N. Sarbini
1
Universiti Putra Malaysia, Bintulu Campus; Baotou Teachers' College of Inner Mongolia Science & Technology University
2
Universiti Putra Malaysia, Bintulu Campus
3
Universiti Putra Malaysia
4
Universiti Sains Islam Malaysia
5
Universiti Malaysia Sarawak

In this study, an attack on the El-Gamal encryption scheme ELG-LUC3-ECC is proposed, which is based on a third-order Lucas sequence over an elliptic curve finite field, using Hastad's and Julta's theorems.  Hastad's theorem was used to solve the problem of multivariate modular equations system, whereas Julta's theorem was used to find the solutions of multivariable modular equation.  As a result, the minimum amount of plaintext required for a successful attack may be determined.  Thus, similar attacks can be prevented if the quantity of plaintext remains within the appropriate range.

cubic
El-Gamal
Hastad's theorem
Julta's theorem
Lucas sequence
  1. Diffie W., Hellman M.  New Directions in Cryptography.  IEEE Transaction on Information Theory.  22 (6), 644–654 (1976).
  2. Elgamal T.  A Public Key Cryptosystem and A Signature Scheme Based on Discrete Logarithms.  IEEE Transaction on Information Theory.  31 (4), 469–472 (1985).
  3. Smith P. J., Skinner C.  A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms.  Advances in Cryptology – ASIACRYPT'94.  355–364 (1994).
  4. Wong T. J., Said M. R. M., Othman M., Koo L. F.  A Lucas based cryptosystem analog to the ElGamal cryptosystem and elliptic curve cryptosystem.  AIP Conference Proceedings.  1635 (1), 256–259 (2014).
  5. Sarbini I. N., Wong T. J., Koo L. F., Othman M., Said M. R. M., Yiu P. H.  Garbage-man-in-the-middle (type 2) attack on the Lucas based El-Gamal cryptosystem in the elliptic curve group over finite field.  6th International Cryptology and Information Security Conference.  35–41 (2018).
  6. Sarbini I. N., Wong T. J., Koo L. F., Naning F. H., Yiu P. H.  An Analysis for Chosen Plaintext Attack in Elliptic Curve Cryptosystem Based on Second Order Lucas Sequence.  International Journal of Scientific and Technology Research.  8 (11), 1193–1196 (2019).
  7. Koo L. F., Wong T. J., Naning F. H., Yiu P. H., Sathar M. H. A., Rasedee A. F. N.  Security Analysis on Elliptic Curve Cryptosystem Based on Second Order Lucas Sequence using Faults Based Attack.  Advances in Mathematics: Scientific Journal.  9 (12), 10845–10854 (2020).
  8. Said M. R. M., Loxton J.  A cubic analogue of the RSA cryptosystem.  Bulletin of Australia Mathematical Society.  68 (1), 21–38 (2003).
  9. Miller V.  Use of Elliptic Curves in Cryptography.  Advances in Cryptology – CRYPTO'85 Proceedings.  85, 417–426 (1985).
  10. Koblitz N.  Elliptic curve cryptosystems. Mathematics of Computation.  48 (177), 203–209 (1987).
  11. Wong T. J., Koo L. F., Naning F. H., Rasedee A. F. N., Magiman M. M., Sathar M. H. A.  A Cubic El-Gamal Encryption Scheme Based On Lucas Sequence And Elliptic Curve.  Advances in Mathematics: Scientific Journal.  10 (11), 3439–3447 (2021).
  12. Hastad J.  On using RSA with low exponent in a public key network.  Advances in Cryptology – CRYPTO'85 Proceedings.  403–408 (1986).
  13. Joye M.  Security Analysis of RSA-type Cryptosystems.  PhD Thesis, Universite Catholique de Louvain, Belgium (1997).
  14. Coppersmith D.  Finding a Small Root of a Univariate Modular Equation.  Advances in Cryptology – EUROCRYPT'96.  155–165 (1996).
  15. Julta C. S.  On finding small solutions of modular multivariate polynomial equations.  Advances in Cryptology – EUROCRYPT'98.  158–170 (1998).
  16. Dickson L. E.  The analytic representation of substitutuions on a power of a prime nnumber of letters with a discussion of the linear group.  The Annals of Mathematics.  11 (1/6), 65–120 (1896).
  17. Lidl R.  Theory and application of Dickson Polynomial.  Topics in Polynomials of One and Several Variables and Their Applications.  371–395 (1993).