Research Of Fast Scalar Multiplication Algorithms On Elliptic Curve

Elliptic curve cryptosystems (ECC), which was independently brought forward by Miller and Koblitz in 1985, has been the hot topic accounting for its advantages such as faster computation, less storage, narrower bandwidth, especially suitable for smart cards and wireless applications etc. The basic and most time-consuming computation in elliptic curve cryptosystems is the scalar multiplication, that is, compute an elliptic curve point kP from a given integer k over a finite field and a given point P on elliptic curve. The efficiency of the operation dominates the execution time of ECC.There are two levels in computingkP : one is upper operation, such as add or double operations of elliptic curve points, the other is bottom field operation which contains multiplications, squarings or additions of elements of finite field. Accordingly there are two ways to research the scalar multiplication: upper operation is subdivided into two points, which are seeking efficient representation of the scalar k and parallelization of the scalar multiplication, while over bottom field operation is to seek fast algorithms to achieve add and double operations. Basing on the results derived from the former researchers, we have done the research as follows:(1) By applying direct computation dP + Q to Comb algorithm, we improve the efficiency of the Comb algorithm on elliptic curve over prime field at evaluation stage, where computing 2 P +Q only needs 11 multiplications and 7 squarings. Because making use of the efficient operation 2 P +Q, Comb algorithm makes an improvement in its efficiency. When digit length l is 160,192 and 224, by analyzing runtime of the improved algorithm, we conclude that the improved algorithm at evaluation stage increases about 79% in efficiency compared with the Comb algorithm when w =4and w =8.(2) By applying point halving to Comb algorithm, we provpose a new Comb scalar multiplication algorithm to improve efficiency of the algorithm on elliptic curve over finite fieldF2 . At precomputation and evaluation stage, the new algorithm takes advantage of efficient point halving to replace point doubling respectively. Analyzing runtime of the new algorithm, we conclude that efficiency of the new algorithm increases about 68%～74% in efficiency at precomputation stage , about 19%～24% at evaluation stage , and about 58%～63% as a whole compared with the traditional algorithm when width of window w =4.(3) By applying Interleaving to Window TNAF Algrithm, we propose a new new scalar multiplication algorithm. The algorithm has no precomputation, just exerts interleaving at the evaluation stage. Because of high performance of Frobenius map and the use of interleaving, efficiency of the new algorithm is higher than traditional window algorithm. When digit length l is 160,192 and 224, by analyzing runtime of the new algorithm, we conclude that the new algorithm increases about 60%～75% in efficiency compared with the traditional NAF Window algorithm, and increases about 70%～79% compared with the Comb algorithm when w =4and w =8.