Binary Division Attack for Elliptic Curve Discrete Logarithm Problem
Boris S. Verkhovsky, Yuriy Polyakov · Transactions on Networks and Communications · 2014
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.