A Study of General Attacks on Elliptic Curve Discrete Logarithm Problem over Prime Field and Binary Field

Authors: Tun Myat Aung, Ni Ni Hla

Abstract:

This paper begins by describing basic properties of finite field and elliptic curve cryptography over prime field and binary field. Then we discuss the discrete logarithm problem for elliptic curves and its properties. We study the general common attacks on elliptic curve discrete logarithm problem such as the Baby Step, Giant Step method, Pollard’s rho method and Pohlig-Hellman method, and describe in detail experiments of these attacks over prime field and binary field. The paper finishes by describing expected running time of the attacks and suggesting strong elliptic curves that are not susceptible to these attacks.c

Keywords: Discrete logarithm problem, general attacks, elliptic curves, strong curves, prime field, binary field, attack experiments.

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

References:

[1] Anoop MS. Elliptic Curve Cryptography, http://www.infosecwriters.com/Papers/Anoopms_ECC.pdf.
[2] Behrouz A. Forouzan, Cryptography and Network Security, McGraw-Hill press, International Edition, 2008.
[3] Darrel Hankerson, Alfred Menezes, Scott Vanstone. Guide to Elliptic Curve Cryptography, Springer press, 2004.
[4] E. Karthikeyan. Survey of Elliptic Curve Scalar Multiplication Algorithms, Int. J. Advanced Networking and Applications, Volume 04, Issue 02, 2012.
[5] Hung-Zih Liao, Yuan-Yuan Shen. On the Elliptic Curve Digital Signature Algorithm, Tunghai Science Volume 8, July, 2006.
[6] Kenneth H. Rosen. Discrete Mathematics and its Applications, Global Edition, 2008.
[7] Lawrence C. Washington. Elliptic curves. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2003. Number theory and cryptography.
[8] Matthew Musson. Attacking the Elliptic Curve Discrete Logarithm Problem, Master Thesis of Science (Mathematics and Statistics) Acadia University, 2006.
[9] Ni Ni Hla, Tun Myat Aung. Implementation of Finite Field Arithmetic Operations for Large Prime and Binary Fields using java BigInteger class, International Journal of Engineering Research and Technology (IJERT), Volume 6, Issue 08, August – 2017
[10] Recommended Elliptic Curves for Federal Government Use, NIST, 1999.
[11] Rudolf Lidl and Harald Niederreiter, Introduction to Finite Field Arithmetic and their Applications, Cambridge University Press, 1986.
[12] Tun Myat Aung, Ni Ni Hla. Implementation of Elliptic Curve Arithmetic Operations for Prime Field and Binary Field using java BigInteger class, International Journal of Engineering Research and Technology (IJERT), Volume 6, Issue 08, August - 2017.