Construction And Analysis Of Scalar Multiplication Algorithm On Elliptic Curve

As the scalar multiplication is the basic calculation for ECC and the whole computational performance of ECC has heavily depended on the efficiency of the scalar multiplication algorithm, the study of scalar multiplication algorithm is not only of Great theoretical significance, but also has broad market prospective. The main contribution of this dissertation is that:1. Base on factorial expansions, we develop a novel fast multiple scalar multiplication algorithm, namely, signed integer factorial expansion of multi-scalar multiplication algorithm. And by the idea of Fixed-base Windowing Method, the new algorithm conducts the evaluation of multi-scalar multiplication via the technique of scalar multiplication creatively and thus the point multiplication is not required anymore in the algorithm, which relieves the computational burden a lot compared with the traditional algorithms. From the given experimental data , it can be easily seen that when m is equal to 2, the computational efficiency of multiple scalar multiplications has been improved about 47.8%～56.5% on average by our new algorithm than other existed methods.2. Based on the double-base chain representation of scalar using bases 2 and 3, a improve Tate-pairing algorithm which combines the {2,3}-double base chain and the Miller's algorithm is presented. The basic idea of this new Tate-pairing fast algorithm is that by taking advantage of pseudo-multiplication algorithm and polynomial expansion algorithm, the complexity of computation in iterations can be reduced efficiently, and by changing the settings of parameters of the lines on elliptic curve, the performance of bilinear pairing can be improved considerably. It can been easily seen from the experimental results that, the computational efficiency of our new method has been improved by 10.6%～20.3% on average than other existing methods.3. On the basis of (2), we extend the {2,3}-double base chain Tate-pairing fast algorithm to the situation that the multi-base chain representation of scalar using bases 2 ,3 and 5 is considered. It can be found apparently from the experimental data that this new algorithm is faster than any other existing algorithms.4. A new fault attack method corresponding to the elliptic curve double-base scalar multiplication algorithm is presented. The main point of this method is based on the side-channel attack, and the technique of fault-tolerant is implemented to yield to the fault output. Consequently, we can deduce some components of expression by monomial and above false output, then, we can obtain the whole key similarly. This new attack method provides us with some valuable information in security analysis. Furthermore, countermeasures are also given and this method is still available for some elliptic curve scalar multiplication algorithm such as binary method,NAF method etc.