Implementation Research Of Koblitz Elliptic Curve Cryptosystem

With the rapid development of computer technology, network and especially the universal used of Internet, human society has being in profound reform what are from industrial economy to information economy. Information has becoming the multiplier of current world economy and social development, and the important mark of evaluation of comprehensive national strength. Recently, various application system based on network increase continue to emerge, such as e-government and e-commerce. However, information security has become one of the best important problems. Cryptograph technique became the main resolving means, and its importance is well received. Therefore, its theory research and application research has becoming the important research field in computer science.Modern cryptograph has become science since Shannon published the paper of "Communication Theory of Secrecy Systems" in 1949. A cryptosystem is classified private-key cryptosystem and public-key cryptosystem. Because of the asymmetric structure of public-key cryptosystem, it can not only apply to the data encryption, but also can apply to the personal recognition, digital signature, key exchange schemes and electronic payments. So, it has induced people's attention since 1976 when Diffie and Hellman brought forward the conception of public-key cryptosystem.Recently, most public-key schemes, which are well received, are based on a difficulty problem of mathematics. According to the problem they based on, these schemes can be classified as RSA-type schemes which are constructed on the integer factorization problem, ElGamal-type schemes which are based on the difficulty of the discrete logarithm problem, and elliptic curve cryptography(ECC) which is constructed on elliptic curve discrete logarithms problem. Compared with other public-key cryptography, ECC has the advantage of short key. This is because no sub-exponential-time method to solve discrete logarithms over elliptic curves has been found yet. In general, in order to get high security, we should use at least 1024 bits and 2048 bits in the future of RSA cryptography, and it can be equaled by a 160 bits elliptic curve cryptography. Just because of short key in ECC, it is extensively be concerned by most cryptography researchers, and it has strong challenged the application of RSA and Elgamal. And more, its standard has been completed, such as ANSI X9.62 and ANSIX9.63 which are developed by the National Institute of Standards and Technology(NIST), IEEE-P1363 which is developed by IEEE. It is usually said that ECC will become mature in the future and its application will go to various aspects in information security.Its implementation is the important topic in the researching of ECC. It has been classified three levels. The first one is scalar multiplication which is focused on how to convert scalar multiplication to addition of points. The second one is group operation which is discussed how to convert the addition of points and doubling points to finite field operations on a coordinate system. Another is finite field operation including addition, multiplication, squaring, and inverse. Because inverse operation can convert it to multiplication and squaring, the most operation of finite field are multiplication and square. In conclusion, the key to improve ECC efficiency is these three operations.There are three finite field of prime finite field, binary finite field and extension finite field which to apply to construct ECC and the common finite field is binary finite field. Therefore, it has high practical value that research binary field deeply. Finite field multiplication is classified according to the choice of basis for representing elements of the finite field; two common choices are polynomial basis and normal basis. Currently, it seems that normal basis representation(especially optimal normal basis) offers the best performance in hardware, while in software polynomial basis representation is more efficient. There has not been much study related to implementing normal basis multiplication in software, in contrast with the amount of work related to polynomial basis.Currently, many researchers contribute to the implementation of ECC represented by binary finite field. Over binary finite field, the elliptic curves have the form: y²+xy=x³+a₂x²+a₆ and the form: y²+y=x³+a₄x+a₆, the former is a non-supersingular elliptic curve and it is suit to structure the cryptosystem. In the former, when a2 is 0 or 1,and a6 is l,the elliptic curve is so-called Koblitz curve. When implement the scalar multiplication of Koblitz curve represented by normal basis, we may use Frobenius map integer k to TNAF representation of it, and then using it to compute scalar multiplication. There has no doubling points operation. Therefore, the key to improve scalar multiplication is how to reduce the length of TNAF of k.This article has deeply researched the implementation of elliptic curve cryptosystem, and mainly discussed the fast generation of Lambda of normal basis representation, and finite field multiplication algorithm and scalar multiplication of Koblitz curve.Firstly, this article has discussed the theory, and deeply analyzing the generation algorithm of Lambda, and given the generation algorithm of TypeⅠand TypeⅡLambda. After analyzing the process of TypeⅡLambda, An improved algorithm has put forward. It has improved the efficient of generation of Lambda by 50%.Secondly, this article has discussed finite field multiplication, and given its general formula in optimal normal basis. Then, we have researched the Rosing algorithm and Ning-Yin algorithm, and put forward an improved algorithm and three pre-computation methods. Finally, we have tested all above algorithms. According to our analysis and experimentation, the new improved algorithm improves in its efficiency with about 20% by comparison with Ning-Yin algorithm.And then, the article has analyzed the properties of Koblitz curve, and discussed the influence of optional normal basis on scalar multiplication, and also discussed the NAF algorithm and TNAF algorithm. It implements an improved algorithm of TNAF algorithm, and improves the performance of ECC by 50%.Finally, the article has applied to ECDSA. It has been proved the feasibility of above improved algorithm and implementation. On the whole, it can improve the efficiency with 68% compared with Rosing's implementation. The research fruits in this paper have referenced value and engineering practical value in applications of elliptic curve cryptosystem.