The Problems About Fault Attacks On HECDLP Over A Finite Field

Since there are some coefficients in the Weierstrass equations of the ellip-tic curves which are independent with the scalar multiplication on the group consisting of the rational points of the curves [4], a series of relative attack methods are proposed. Biehl et al.[4] proposed the first fault-based attack on the elliptic curve cryptography. And then Ciet and Joye [7] provided a method to recover the secret key by applying the same principle of invalid curves with fixing the input fault point. Karabina and Ustaoglu [8] showed the invalid-curve attack can be extended to protocols which are based on hy-perelliptic curves with genus2if hte public key is not appropriate. Since the y-coordinate is independent with the scalar multiplication, Domminguze-Oviedo et al.[9] demonstrated a fault-based attack algorithm that apply to the Montgomery ladder algorithm on curves over the binary field. Recently, M. Q. Wang, H. Y. Xue, and T. Zhan [29],[30] presented efficient invalid-curve attacks according to the representations of divisors in the Jacobian group of a hyperelliptic curve with genus2over a finite field by injecting a1-bit fault in the input divisor. In their attack models the location of the fault bit is known, but it is difficult for adversaries to know the location of the injected fault directly in practice.In this paper, we presume that the location of the injected fault bit is unknown. By injecting1-bit fault into an input divisor randomly, we provide two invalid-curve attacks on Discrete Logarithm Problem of the hyperelliptic curves over finite fields with genus2, according to the two representations of an element in the Jacobian group of a hyperelliptic curves. According to our attack models, we propose two algorithms to construct the two invalid-curve attacks based on the resulted divisor by the algorithm F2a[20], since our attacks are based on the fact that the hyperelliptic curve scalar multi-plication(HECSM) algorithm F2a [20]is independent on the coefficients of the curve a0,a0. And then the order of Jacobian group on the invalid-curve is a smooth integer which implies that the prime factors of the order n of the faulted divisor in the new Jacobian group are less then ω. Hence, we can use Silver-Pohlig-Hellmans algorithm [25] to recover the partial private key k mod n. Meanwhile, the theoretical probability of obtaining a ω-valid fault is1/ρ(log n/log ω). The result of the experiment demonstrates the efficiency of our attack methods.