| After it's first proposition, pulic key cryptosystem was widely used to design cryptographical application, such as key agreement, identity authentication, data integrality, digital signature, electronic election, electronic business, electronic government programme, etc. Especially, sustained by CA and certificate, PKI has played a foundational role in the security of a large-scale dynamic network. At this moment, the most popular pulic key cryptosystem in practice is RSA.Elliptic curve cryptosystem (ECC) is a novel public key cryptosystem brought out in 1985. Compared with RSA and, it has a much smaller key length with the same security level. Thus, it is suitable for wireless system and the device with limited storages. It has been adopted by many security standards, such as IPsec, WAPI, WPKI etc, and is going to be the primary standard for application in the not long future.With regard to the implementation of ECC, the key factor is the computation of scalar multiplication kP, where k is a large number and P is a point on the elliptic curve. Scalar multiplication quickly became the research focus of many cryptology experts and many fairly good results had been obtained. Based on the previous work, the production of this paper is listed as below:1. Based on the non-adjacent form (NAF) expression, here we present a new method to express a large positive integer k with the base of any positive integer w other than 2. We call this method the w-NNAF method as the expression is near to the NAF one and with base w. This expression leads to the minimal Hamming weight of all the base w expressions. Based on the proposed expression and some existing methods, an algorithm is developed to compute kP efficiently.2. Based on the RTNAF representation proposed by Solinas[5], we present a triple-bit grouping method for the efficient computation of the scalar multiplication in elliptic curve cryptosystem. By using this method, about m/18 point additions are avoided at the cost of two storage requirements. In the case that extra storage is available, we can further reduced the computational complexity of scalar multiplication by extending the triple-bit grouping method to the general (w+1)-bit grouping one. The reduction in the computational complexity is analyzed in detail.3. A method called RTSNAF, which expresses scalar k with the base Ï„~2 rather than Ï„ in the RTNAF method. The existence and uniqueness of this expression is proven by mathematical analysis. An estimation of the length and the density of the proposed expression is also given, respectively. Finally, the computation cost of kP using this expression is determined by 2m/14 times of point additions. It is better than m/3 of the RTNAF representation.4. With the use of the endomorphismmethods, Frobenius map is utilized to expand the integer k and each coefficient of the expansion is represented as a binary string. In this paper, with the application of joint sparse form (JSF) to the coefficients, some variations of Lee et a/'s methods are proposed to achieve a better performance at a lower storage requirement.7. Lee et al proposed two methods to speed up the computation of scalar multiplication of elliptic curve defined over GF(2m") with a medium size of m in the range 10 |
PDF Full Text Request