The Study Of Fast Algorithm Of Scalar Multiplication On Elliptic Curve

Elliptic Curve Cryptography(ECC) provides the highest security strength per-key-bit of any cryptography known.Compared with other public-key cryptographies,ECC not only has the higher security but also has less computation overheads,shorter key size and narrower bandwidth.Therefore,making an intensive study about public key cryptography has great practical significance.The basic and most time-consuming computation in elliptic curve cryptosystems is the scalar multiplication,and scalar multiplication algorithm is the most important operation in elliptic curve cryptosystem.Improving the speed of scalar multiplication operation on elliptic curve is of great significance to the promotion of elliptic curve cryptosystem.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.We mainly study efficient representation of k.This paper studys scalar multiplication mainly focus on double scalar multiplication algorithms and representation of k with multi-Base.First,we introduce the elliptic curve scalar multiplication algorithms,including binary method,NAF method and window method.And we make an analysis about the classic double scalar multiplication algorithms-Shamir fast algorithm and interlacing NAF method.Based on Shamir fast algorithm,we give a improved algorithm.Compared with Shamir fast algorithm,the improved algorithm can reduce the storage of points by 50% without significant increase of quantity of computation.It is suitable for handheld devices which has few memory.Secondly,we introduce the development and research situation about double-base and multi-base system.And analyzes the existing Ceit's scalar multiplication algorithm with double-base coding and a kind of scalar multiplication algorithm with multi-base coding,and then gives a kind of improved scalar multiplication algorithm with multi-base coding.By quantitative analysis about the three algorithms,we find the improved scheme can minimize the number of inverse calculate.When I/M is 60, the improved algorithm can improve the efficiency by 7%.