Study Of Fast Scalar Multiplication Algorithm On Elliptic Curve Against SPA Attack Over F_p

Elliptic curve cryptography has the significant advantages of smaller keys, faster computations and high security,etc, which makes it especially suitable for environments where bandwidth,storage,processing power or power consump-tion are constrained. Now it has moved from the theoretical stage to the practical application stage, and becomes one of the most promising public key Cryptography. It attracts an increasing number of researchers. This paper focuses on the fast algorithm on elliptic curve cryptography over the prime field, mainly including the addition of points,scalar representation and scalar multiplication in itself and pre-computation.Longa proposed an alternative technique [14], namely 2ab= (a+6)2-a2-b2, in which if a2 and b2 are the calculated values, and then only (a+b)2 must be calculated. We can use squaring operation with lower time cost instead of multiplication operation with higher time cost, so some time cost is saved. This method is used in Jacobian coordinates[14]. We can use this method in point addition and doubling formulas in almost all coordinates, especially in Modified Jacobian coordinates. Thereby, to a great extent, time cost of the scalar multiplication algorithm of multiplication calculation is saved. On the one hand, the concept of mixed coordinates and some time costs of point addition and doubling formulas in mixed coordinates were given. But they didn’t give us concrete calculation method. In this paper we present a kind of calculation method about point addition and doubling operation in the mixed coordinates by the example. There exist three formulas which are faster than the speed of calculation in literature[4].In the terms of scalar representation and scalar multiplication, Okeya[23] studied a width-w NAF method, and draw a SPA-resistant scalar multipli-cation algorithm. In terms of pre-computation, Meloni[16] and Longa[15] p-resented a co-Z addition algorithm in Jacobian coordinate and the related pre-computation method. And one will be able to obtain the pre-computation point in affine coordinates by only one inverse operation on the basis of the nu-merical relationship between the points. In this paper, on the basis of the pre-computation method in Jacobian coordinates, we obtain the pre-computation method in Chudnovsky Jacobian coordinates.what’s more, according to the method of Cohen[4], we study how to select the coordinates in order to make computing faster under SPA-resistant attack. And we compare the time cost of scalar computation in affine with Chudnovsky Jacobian coordinates.