Research On Fast Scalar Multiplication Algorithms On Several Classes Of Algebraic Curves

The elliptic curve cryptography (ECC) is a widely used modern cryptographicsystem. To meet the application requirement, the State Cryptography Administrationreleases the SM2 elliptic curve public-key cryptographic algorithm and the curveparameters in the Bulletin 21, and also it sets that ECSDA should be used in thewireless local area network equipments in the Bulletin 7. In some foreign companies,such as Motorola, Sony and Cisco, have developed a lot of products in the form of ICcards or softwares based on the ECC. The ECC has the following advantages: rapiderprocessing speed, lower band width, less storage and so on. These advantages areespecially applicable for limited resource environments. The speed of computingscalar multiplications has a great impact on the implementation efficiency of the ECC,and so how to improve the efficiency of scalar multiplications has become the focusof the researchers who are interested in cryptography. There are two ways to improvethe efficiency of the scalar multiplication algorithms: one way is to express the scalarin a number system representation of short length, and the other is to speed up thefield operations.This paper mainly studies the fast scalar multiplications on two kinds of specialalgebraic curves. One is Edwards curve. The main advantages of Edwards curve arethat the group operation rules on Edwards curve are simple, and its pointmultiplication and point addition share the same formula. The paper analyses thegroup operations on the Edwards curves, and points out that its group operationalefficiency is higher than others forms of elliptic curve. The main attributions in thispaper are as follows:(1) By converting the scalar into a four-decimal representation and using thepoint tripling formula, we put forward an improved algorithm for the scalarmultiplication algorithm on Edwards curves. Through the theoretical analysis and thecomparison of computation cost, the improved algorithm is more efficient than theformer algorithm, and also it saves about 20% memory space less than formeralgorithm.(2) By using the binary and ternary method to express the scalar, and also byusing the fast algorithms for computing 2nP and 3nP , we put forward a newalgorithm for scalar multiplications. The analytic of the computation cost and theexample show that the computation cost of the improved algorithm is superior to binary method and ternary method in the aspect of computation amounts.Another kind of algebraic curves studied in the paper is the hyperelliptic curveC: v2=upq+au+b. The security of HECC is based on the difficulty of computingthe discrete logarithm on the Jacobian group. The structure and operational rules ofthe Jacobian groups are more complex than that of the rational point groups overelliptic curves or Edwards curve. But compared with other cryptosystems, HECC hasits own advantages, such as stronger single-bit security, and more hyperelliptic curvesthat can be used for HECC. In a paper, a fast algorithm was proposed to computeplD, where p is a prime number, D is a divisor, and l is a positive integer. Inthis paper, we will introduce a double-base chain, that is, a 2a p b ary formexpression, to represent the scalar and then develop two fast algorithms for the scalarmultiplication onC q. Our theoretical analysis and simulation experiments show thatthe new fast scalar algorithms are more efficient than other algorithms in thecomputation cost.