¡¡Chinese Journal of Computers   Full Text
  TitleA New Algorithm of Elliptic Curve Multi-Scalar Multiplication
  AuthorsLIU Duo DAI Yi-Qi
  Address(Department of Computer Science and Technology, Tsinghua University, Beijing 100084)
  Year2008
  IssueNo.7(1131¡ª1137)
  Abstract &
  Background 		Abstract The main operations of elliptic curve cryptosystem are scalar multiplication and multi-scalar multiplication for a pair of integers. In this paper, a new encoding algorithm, which transforms multiple integers into a new kind of signed binary representation of them, is presented. The new encoding algorithm needs only to handle two adjacent columns, and thus is fast and easy to implement. Using this new kind of joint signed binary expressions, a new elliptic curve multi-scalar multiplication algorithm is proposed. The analysis about its time complexity is given, and the comparisons of traditional methods and the new method are also presented, based on which the authors draw the conclusion that the new multi-scalar multiplication algorithm requires about 7% to 15% less running time than the known ones.
Keywords cryptology; elliptic curve; multi-scalar multiplication; joint signed binary representation
Background Elliptic curve cryptosystem (ECC) was proposed independently in 1985 by Koblitz and Miller. Recently, many efficient algorithms and implementation techniques related to ECC have been proposed.
The basic operation of ECC is scalar multiplication, which uses a given point P and an integer k to compute kP. The multi-scalar multiplication, which computes the point k1P1+k2P2+¡­+kmPm for the given point P1,P2,¡­,Pm and positive integers k1,k2,¡­,km, also plays an important role in ECC, for it can be used in the following three cases.
(1)In some protocols, such as the verify step of ECDSA (elliptic curve digital signature algorithm), multi-scalar multiplication on elliptic curve is required;
(2)In some fast scalar multiplication algorithms, the computation of scalar multiplication is converted to the computation of multi-scalar multiplication;
(3)In some countermeasure designs of scalar multiplication to resist Simple Power Analysis (SPA), an integer is decomposed into multiple integers, and thus scalar multiplication can be securely implemented as multi-scalar multiplication.
The most trivial method of computing the point k1P1+k2P2+¡­+kmPm is as follows: compute the m scalar multiplications k1P1,k2P2,¡­,kmPm respectively, and then sum the m points up. However, the efficiency of this method is low. Thereupon, the trick named as simultaneous scalar multiplication was proposed, based on which some new multi-scalar multiplication were designed. Solinas introduced the Joint Sparse Form (JSF) presentation technique for pair of integers, which is a special kind of joint signed binary presentation, and proposed a new multi-scalar multiplication algorithm for a pair of integers using JSF. An open problem, (the joint sparse form for) Three or More Terms, was also put forward in his work. This paper gives a solution to it by proposing a new encoding algorithm, which transforms multiple integers into a new kind of signed binary representation of them.
On this basis, a new elliptic curve multi-scalar multiplication algorithm is proposed. Its analysis and comparisons to traditional methods are given.