Researches On Scalar Multiplication Fast Algorithm In Elliptic Curve

With the rapid development of information technology, information security problems have become increasingly prominent. The cryptographic technique is an effective way to achieve information hiding, integrity verification, authentications. And it is also an ensurance information systems security. Because of its anvantages in better security and shorter key, Elliptic Curve Cryptography (ECC) is especially suitable for storage space, bandwidth, and power consumption constrained environment. ECC has drawn widespread concerns and applications since its proposition, and has become one of the most promising public-key cryptosystem. Calculation speed is one of the most important issues in researches andapplicationes of ECC.How to implement ECC efficiently is one of the research hotspots in recent years. The calculation speed of ECC is determined by the efficiency of scalar multiplication, which is a key to improve the calculation speed. In this paper, scalar multiplication of ECC is analyzed and researched, and improvement of this algorithm is then conducted. The main research contents and results of this paper are as follows:(1) A basic understanding of the weaknesses in the existing algorithms is achieved through researches and analyses of Shamir-NAF scalar multiplication algorithm. Scalar k is expressed in the form of NAF in this method.Scalar k in that form may be1bit longer than the binary representation form based on the nature of NAF. If zeroes can be made more concentrated in NAF form, then calculation efficiency can be improved by sliding technique. An improved Shamir-NAF algorithm is proposed in this paper to solve these problems, the length of k can be reduced by using the improved algorithm. The data show that efficiency can be improved by about22%using the improved algorithm, indicating that the improved algorithm is better than the original algorithm.(2)The algorithm of direct calculation is analyzed, computation will be a great defect when k has long bits, such as k=128bits. A binary represented direct calculation algorithm is proposed to solve this problem. Since the orginal algorithm is processed by the binary representation, the defect brought by long bits of k is solved. And the proposed algorithm is compared with traditional NAF algorithm, the data show that point multiplication efficiency can be improved by about8%by the proposed algorithm.