| Elliptic curve cryptosystems (ECC) is a novel public key cryptosystem brought out in 1985. Compared with RSA, 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 it is going to be the primary standard for application in the not long future.Accounting for its many advantages, such as faster computation, less storage, narrower bandwidth, especially suitable for smart cards and wireless applications eta, the basic and most time-consuming computation in elliptic curve cryptosystems is the scalar multiplication, that is, compute an elliptic curve point kP from a given integer k over a finite field and a given point P on elliptic curve.With regard to the implementation of ECC, the key factor is the computation of scalar multiplication quickly became the research focus of many cryptology experts and many fairly good results had been obtained. Based on the previous work, we have done the research as follows:(1) In scalar recoding aspect, the digit length and hamming weight of scalar determine the efficiency of scalar multiplication on elliptic curves. This paper designs a recoding algorithm which scans the sequence of the scalar only once, employs four intermediate variables at most as well as comparisons and evaluations on digits. The algorithm is more efficient and more convenient to application of scalar multiplication on hardware. The result is proved to possess the character of the canonical representation. When the algorithm is applied to compute gP+hQ in digital signatures, the result is unique, optimal and has the least joint weight.(2) In scalar multiplication based on DBNS aspect, a new number field system– double base number system (DBNS) is employed in denoting scalar k. In field fast algorithm aspect, a fast algorithm of direct computing 3kP is proposed in way of trading reversions for multiplications. The new double base scalar multiplication algorithm is integrated with fast algorithms of direct computing 2kP,2P±Q,3P±Q and 3kP. The efficiency of new algorithm is superior to algorithm given by Dimitrov and traditional scalar multiplication.Scalar multiplication based on double base number system was improved on elliptic curve defined in binary field. Firstly a fast algorithm of direct computing 3kP in field was deduced. The algorithm needed one field inversion and the break-point faster than several triplication was 1 field inversion equal to 5 field multiplication. New double base number recoding based on 1/2 as well as 3 and integrated high-speed direct computing 3kP as well as halving algorithm. Scalar multiplication that based on the recoding employed only point addition, halving algorithm, triplication and direct computing 3kP. So the complexity depressed and the efficiency improved about 70% than Dimitrov algorithm and about 10% than Wong method on the elliptic curve recommended by NIST.(3) In fixed point scalar multiplication aspect, firstly, to improve efficiency of scalar multiplication, a run-length addition chain of scalar was proposed. New scalar multiplication integrated with algorithms of direct computing 2Q+P, 2nR+S in field, sliding window algorithm and run-length algorithm. The addition chain length, storage and pre-computing is smaller. Its efficiency enhances about 53% than binary method, about 47.5% than NAF method, about 46.2% than run-length algorithm and about 42.2%.Secondly, we improve on traditional sliding window algorithm: firstly store nonzero window value and exponent of nonzero window's power with pretreatment track; secondly propose a new scalar multiplication algorithm by combining algorithm direct computing 2kR+S in field and pre-compute table. The new algorithm trades several memories for the improvement in evaluation stage. This paper still analyzes that the efficiency of new algorithm in mixed coordinate enhances about 40.6% comparing with traditional sliding window algorithm in affine coordinate when w = 4.Thirdly, we optimize the Lim-Lee algorithm with NAF method, pre-compute table and Yen-Laih method in three stages separately. The new fixed-point scalar multiplication algorithm dynamic scans the matrix to get nonzero windows with length limited in w in the evaluation stage, integrates with 2kP field fast algorithm and extended pre-compute table to improve compute efficiency. When digit length is 160, the efficiency of new algorithm improves about 22.7% than Lim-Lee algorithm, about 23% when 192 and 23.3% when 224.(4) In scalar multiplication based on Frobenius map aspect, we study fast scalar multiplication on Koblitz curve. A super operation algorithm based on Frobenius map is proposed, Comb algorithm. The algorithm stores some points corresponding to a sequence at a fixed length, and employs this pre-compute table at evaluation stage sufficiently. Because of high performance of Frobenius map, the point addition number needed by algorithm in this paper is 1/5~1/4 times of that by traditional algorithm. In addition, the efficiency of the algorithm is faster about 67% than traditional Comb algorithms with arbitrary length of row in any coordinate at least.This paper studies fast scalar multiplication on Koblitz curve. An operation algorithm based on Frobenius map is proposed, window algorithm. The algorithm stores some points corresponding to a sequence at a fixed window length firstly, and then employs this pre-compute table at evaluation stage sufficiently. Because of high performance of Frobenius map, the point addition number needed by the algorithm in this paper is about 1/5~1/4 of that by traditional window algorithm. In addition, the algorithm is faster about 66% at least than traditional window with arbitrary window length. |
PDF Full Text Request