Elliptic Curve Scalar Multiplication Fast Implementation

Elliptic curve cryptosystems (ECC) has been the hot topic since its come out by Koblitz and Miller in 1985, accounting for its many advantages such as faster computation, less storage, narrower bandwidth, especially suitable for smart cards and wireless applications etal. 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.Gerenrally speaking, there are two strategies to speed up the scalar multiplication: one is to investigate efficient the scalar k's representation, the other is to seek fast algorithms over bottom filed. Based on the results of former researchers, we have done the research as follows:(1) According to the fixed-base comb method's features, apply the direct computations of 2kP and 2P+Q to the comb method's precomputation and evaluation stage respectively. Taking advantage of trading inversions for multiplications, the improved method is able to obtain about 73%~83% improvement in precomputation stage and a range of 38%~43% in evaluation stage over prime field, furthermore, our improved method is resistant to simple power analysis by pretreating the scalar k.(2) Based on the fast underlying field arithmetic of 2kP, 3kP, 2P±Q and 3P±Q, presents a new fast scalar multiplication based on double-base chains. Due to the sparseness of the double base number system and advantages of fast underlying field arithmetic, our proposed method reduces inversions operation of underlying field enormously, enhances scalar multiplication efficiently. Experiments prove that, our method is superior to Dimitrov's algorithm with the same double base chain: it performed 19%-22% improvement with 160- bit secret key, whereas 192-bit 22%-25%, 224-bit 26%-30%, 256-bit about 35% over prime field.(3) Begins with double-base number system, from which we propose a subset that satisfying the absolute valve between the two exponents of 2 and 3 is no more than 1, denoted as Sub-SDBNS, from which we can represent the scalar k in Sub-NCSDBNR by a greedy algorithm similar to k's NCSDBNR. The increase idiosyncracy of the 2-integers in the Sub-SDBNS leads to a great extent time-saving in seek an positive integer's Sub-NCSDBNR, thus efficiently offset the disadvantage of Sub-NCSDBNR numbers'increase, furthermore, the Sub-SDBNS decrease precomputation talbe and storage from n2 to 3n-2. Then taking advantage of direct computation and mixed coordinates, we propose two fast scalar algorithms which distinguished by a precomputation table. The one that contain the precomputation one is suit for fixed-base point scalar multiplication, while the other fits random point as well. Their time and storage cost are discussed at the end of this paper compared with convertional fixed-base window method and Dimitorv's algorithm, besides, experiment results support our algorithm's efficiency firmly.