Binary Division Attack for Elliptic Curve Discrete Logarithm Problem

Authors

  • Boris S. Verkhovsky Computer Science Department, New Jersey Institute of Technology, Newark
  • Yuriy S. Polyakov Computer Science Department, New Jersey Institute of Technology, Newark

DOI:

https://doi.org/10.14738/tnc.24.293

Keywords:

Elliptic Curve Cryptography, Discrete Logarithm Problem, Security Attack, Point Halving, Cryptoanalysis, Public-Key Cryptography

Abstract

Elliptic curve cryptography (ECC) is an approach to public key cryptography (PKC) that is based on algebraic operations with elliptic curves defined over finite fields. Security of elliptic curve cryptography is based on the hardness of the elliptic curve discrete logarithm problem (ECDLP). Although there is no theoretical proof that ECDLP is intractable, no general-purpose sub-exponential running time algorithm has been found for solving the ECDLP if the elliptic curve parameters are chosen properly. In this study, we develop a new security attack based on the binary division of elliptic curve points over prime fields that may be used to solve the ECDLP when the order q of elliptic curve satisfies the congruence q = 2 (mod 4). To perform the binary division, we devise a novel algorithm of point halving on elliptic curves defined over prime fields that applies to the cases when q = 1 (mod 2) and q = 2 (mod 4). The binary division attack has exponential worst-case asymptotic time complexity but in certain practical cases can be used to solve the ECDLP in a relatively efficient way. We therefore make a recommendation to avoid the case of q = 2 (mod 4) in elliptic curve cryptosystems.

Author Biographies

Boris S. Verkhovsky, Computer Science Department, New Jersey Institute of Technology, Newark

Professor of Computer Science

Yuriy S. Polyakov, Computer Science Department, New Jersey Institute of Technology, Newark

Yuriy Polyakov, PhD, has more than 15 years of corporate experience in information technology/computer science and more than 10 years of scientific research experience in applied mathematics, physics, computer science, and engineering. He architected and developed novel corporate IT solutions in the areas of business analytics, security, data architecture, expert systems, managed services, medical software systems, and systems integration. Yuriy led multiple R&D projects in applied computer science, such as the development of a computer-aided osteoporosis diagnosis tool, integrated NOC-based managed services solution, and nanometrological software package for atomic force microscopy setups.

He is an author of 37 publications in refereed journals (more than 70 publications in total). Developed a novel statistical physics method for the analysis of natural time and spatial series and successfully applied it to complex problems in neuroscience, geophysics, nanotechnology, astrophysics, and mechanical engineering. Formulated several mathematical models based on partial differential and integrodifferential equations for various processes in chemical and environmental engineering. Developed numerical, analytical, and approximate methods for nonlinear partial differential and integrodifferential equations/systems arising in engineering problems. Developed algorithms for continuous optimization problems. Invented several novel concepts and processes in environmental engineering and sustainability.

Yuriy prepared his first journal paper at the age of 17 (first-year university student). Defended the habilitation thesis for the Doctor of Sciences in Physics and Mathematics in Russia at the age of 27 (nationwide youngest D.Sc. in this field at the time, with the average defending age of 45-50). Reviewer for 14 scholarly journals. Recipient of Moscow Mayor's Young Scientist award. He serves on the Editorial Board of International Journal of Communications, Network and System Sciences. Yuriy currently works as Senior Software Engineer/R&D Director at Presidio Networked Solutions Inc. and Senior Research Scientist at USPolyResearch.

Education

  • D.Sc. (Dr. Habil.), Physics & Mathematics, Karpov Institute of Physical Chemistry, Russia, 2007
  • Ph.D., Chemical & Environmental Engineering, Moscow State University of Environmental Engineering, Russia, 2004
  • M.Sc., Computer Science, New Jersey Institute of Technology, 2003
  • B.Sc., Computer Information Systems, Excelsior College, 2002 

Awards & Honors

 

  • Editorial Board of International Journal of Communications, Network and System Sciences, 2011-presen 
  • Higher Attestation Commission of the Russian Federation (HACRF) Outstanding Habilitation Thesis Award, 2008
  •  Novel membrane filtration process developed in a paper for Journal of Membrane Science is recognized as a new research trend in the field (Membrane Technology, 2007, Issue 1)
  •  Moscow Mayor's Young Scientist Award, 2005
  •  The National Dean's List, 2002-2003
  •  Summa Cum Laude, Excelsior College, 2002

References

. D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, New York: Springer, 2004.

. R. Gallant, R. Lambert, and S. Vanstone, "Improving the parallelized Pollard lambda search on binary anomalous curves", Math. Comput., vol. 69, pp. 1699–1705, 1999.

. P. van Oorschot and M. Wiener, "Parallel collision search with cryptanalytic applications", J. Cryptol., vol. 12, pp. 1–28, 1999.

. M. Wiener and R. Zuccherato, "Faster attacks on elliptic curve cryptosystems”, in Selected Areas in Cryptography’98, Berlin: Springer-Verlag, LNCS 1556, 1998, pp. 190–200.

. F. Zhang and P. Wang, "Speeding up elliptic curve discrete logarithm computations with point halving”, Des. Codes Cryptogr., vol. 67, pp. 197–208, 2013.

. NIST, Digital Signature Standard, FIPS Publication 186-2, February 2000.

. A. V. Bessalov, "A method of solution of the problem of taking the discrete logarithm on an elliptic curve by division of points by two”, Cybern. Syst. Anal., vol. 37, no. 6, pp. 820–823, 2001.

. E. Knudsen, "Elliptic scalar multiplication using point halving", in Advances in Cryptology-ASIACRYPT’99, Lecture Notes in Computer Science 1716, 1999, pp. 135–149.

. R. Schroeppel, "Elliptic curve point halving wins big”, in 2nd Midwest Arithmetical Geometry in Cryptography Workshop, Urbana, 2000.

. D. Hankerson, K. Karabina, and A. Menezes, "Analyzing the Galbraith-Lin-Scott point multiplication method for elliptic curves over binary fields”, IEEE Trans. Comput., vol. 58, no. 10, pp. 1411-1420, 2009.

. K. Wong et al., "Fast elliptic scalar multiplication using new double-base chain and point halving”, Appl. Math. Comput,, vol. 183, pp. 1000–1007, 2006.

. R. Schoof, "Counting points on elliptic curves over finite fields”, Journal de Theorie des Nombres de Bordeaux, vol. 7, pp. 219-254, 1995.

Downloads

Published

2014-09-01

How to Cite

Verkhovsky, B. S., & Polyakov, Y. S. (2014). Binary Division Attack for Elliptic Curve Discrete Logarithm Problem. Discoveries in Agriculture and Food Sciences, 2(4), 1–15. https://doi.org/10.14738/tnc.24.293

Issue

Vol. 2 No. 4 (2014): Transactions on Networks and Communications

Section

Articles