Research Of Fast Scalar Multiplication Algorithms On Elliptic Curve

Elliptic Curve Cryptography (ECC) is an outstanding public key cryptosystem. It has well-known advantages and can be widely used in resource-constrained devices, such as smart cards, wireless networking and embedded systems. The basic operation of ECC systems is kP, where k is an integer and P is an elliptic curve point. This operation is called scalar multiplication, which dominates the execution time of elliptic curve cryptographic. Therefore, it becomes the focus of intensive research of many cryptographers.In this paper, we will make research on scalar multiplication from efficiency and security. In terms of efficiency, there are two mainly ideas. One is in bottom field, transforming the representation of points to get the point addition and doubling formula with high efficiency. The other is re-encoding the scalar to reduce the hamming weight of scalar. While confer to security, it also has two mainly research ideas. The first is randomly-oriented approach, includes key randomize, point randomize etc, protecting attackers from capturing the energy curve. Another is equalization, which adjusts the scalar multiplication algorithm, so that point addition and doubling follow the same steps to make consumed energy show a balanced manner.Based on the above research ideas, the work of the paper are as follows:(1) The scalar multiplication algorithm resisting side-channel attacks is studied in this paper. According to the formulas of point addition and doubling on Jacobi Quartics Curve in projective coordination, a new atomic block A-M-N-S-N-A-A is proposed. In addition, an optimized side-channel atomic scalar multiplication algorithm is put forward. Compared with the previous methods, the new algorithm is more efficient. For192bits scalar using NAF recoding, the efficiency of the new algorithm is increased by about6.7%～23%if S/M=0.8,12.7%～33.2%if S/M=0.6.(2) To improve the efficiency of scalar multiplication, Edwards curve is studied and then point addition and doubling formulas only depending on y-coordinate are introduced. To make the algorithm suitable for parallel environment, the scalar k with binary representation id divided. Then a parallel scalar multiplication algorithm against simple power analysis is given. Compared with the fixed-window algorithm and the signed sliding window algorithm, besides no additional storage and pre-computation, the efficiency is improved about17.3%,33.3%. While with the same security and having no additional storage and pre-computation, the improvement for the new algorithm is31.1%against Montgomery method.(3) In scalar re-encoding research, multi-based number system (MBNS) and its application in scalar multiplication is introduced. The multi-scalar multiplication algorithm Sliding MBNS, I-MBNS based on MBNS is proposed and analyzed in this paper. Over binary fields, according to our calculations the improvement of Sliding MBNS for192-bit is11%against Shamir’s trick and10%against interleaving with w-NAF. I-MBNS is giving more impressive improvements,13%against Shamir’s trick and5%against I-NAF. When confer to prime fields, it is noticeable that sliding MBNS does not give us any improvement compared to any other algorithms in consideration. While I-MBNS gets the improvement about5%.