Binary Division Attack for Elliptic Curve Discrete Logarithm Problem
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.
. 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.
Authors wishing to include figures, tables, or text passages that have already been published elsewhere are required to obtain permission from the copyright owner(s) for both the print and online format and to include evidence that such permission has been granted when submitting their papers. Any material received without such evidence will be assumed to originate from the authors.
All authors of manuscripts accepted for publication in the journal Transactions on Networks and Communications are required to license the Scholar Publishing to publish the manuscript. Each author should sign one of the following forms, as appropriate:
License to publish; to be used by most authors. This grants the publisher a license of copyright. Download forms (MS Word formats) - (doc)
Publication agreement — Crown copyright; to be used by authors who are public servants in a Commonwealth country, such as Canada, U.K., Australia. Download forms (Adobe or MS Word formats) - (doc)
License to publish — U.S. official; to be used by authors who are officials of the U.S. government. Download forms (Adobe or MS Word formats) – (doc)
The preferred method to submit a completed, signed copyright form is to upload it within the task assigned to you in the Manuscript submission system, after the submission of your manuscript. Alternatively, you can submit it by email email@example.com