On the distribution of scalar k for elliptic scalar multiplication
Ruma Kareem K. Ajeena, Hailiza Kamarulhaili · AIP conference proceedings · 2015
In this study, we introduce the probability distribution of the elliptic curve scalar multiplication through finding the probability distribution of the secret key, namely, the scalar k of the scalar multiplication kP of a point P which has a large prime order n lying on elliptic curve group E(Fp) over a finite prime field Fp. To determine this distribution of k, we use the integer sub-decomposition (ISD) approach that inspired from Gallant, Lambert and Vanstone (GLV) idea. In ISD approach, the distribution of the values of scalars k lie outside the range ±n on the interval [1, n − 1]. This distribution determines the successful rate to compute a scalar multiplication kP, on ISD approach, in comparison with the original GLV method. The conception of the ISD approach depends on the sub- decomposition of the scalar k to compute the scalar multiplication kP which uses efficiently computable endomorphisms Ψ1 and Ψ2 of elliptic curve E over Fp. The ISD sub-decomposition can be defined by kP=k11P+k12ψ1(P)+k21P+k22ψ2(P), with max{|k11|,|k12|} and max{|k21|,|k22|}≤Cn, for some explicit constant C > 0. Furthermore, this study compares between the GLV and ISD approaches on the basis of the probability distribution of the scalar k in the interval [1, n − 1], where n is a large prime number.