Researches On The Fast Algorithm For The Scalar Multiplication In The Elliptic Curve Cryptosystems

The Elliptic Curve Cryptosystems(ECC), based on the standard Elliptic Curve Discrete Logarithm Problem(ECDLP), was proposed by N Koblitz and V Miller in 1985. Elliptic curve is an intersection of the three subjects: algebra theory, algebra geometry and parse algebra. It has lots of particularly characters, to apply it to the engineering field such as cipher technology then bring a new subject ECC has attracts many cipher scholars interesting at the beginning, and became a hotspot of the public key cryptosystems.ECC has been studied for more than ten years since it had been proposed, and many results have been made by the cipher scholars. ECC has the most shortest key intensity, and the ECDLP is considered as the most difficult question. So ECC is consistently considered as the future public key cryptosystems instead of the RSA cryptosystems. In order to reach the extent of applicability, there are still many questions have to been resolved. For instance, the question of the efficiency implementation of elliptic curve cryptosystems, and the question of the random security selection of the elliptic curves, and the question of the application of the elliptic curve cryptosystems, etc.In this dissertation the elliptic curve cryptosystems and fast scalar multiplication algorithms are investigated. The methods to speed up the scalar multiplication computation are mainly discussed in two ways: one is the number system, another is parallel algorithm. It is consists of six chapters. In chapter one, some introductive materials are presented, including the motivations and the developments of the elliptic curve cryptosystems, the intentions of the research work, the main contents of the paper and the list of the results. In chapter two, the fast implementation problems of the elliptic curve cryptosystems are studied. In this chapter, the problems are firstly reduced to the computations of the scalar multiplication of the elliptic curves. Then all thealgorithms for the fast computations of the scalar multiplication of the elliptic curves are summarized. In chapter three, at the angle of number system, we proposed the fast algorithm for scalar multiplication based on DBNS, SDBNS, and SubSDBNS. In chapter four and five, we studied the parallel algorithm for scalar multiplication. In chapter four the parallel window method is proposed, in chapter five a new parallel method NSP is proposed. Both two algorithms are implementation on the Drawn-2000, and the results are been analysised.