Research Of Secure And Fast Scalar Multiplication Algorithms On ECC

Among the various public key cryptographic algorithms, the elliptic curve cryptography has received gread attention due to its advantages such as single bit security, fast calculation speed and rich cuve resources. As the most basic and time consuming operation in ECC, scalar multiplication dominates the performance of the whole system.In this paper, we will make research on efficiency and security of scalar multiplication, In terms of efficiency, there are two main ideas. One is reencoding the scalar to reduce the hamming weight of scalar by searching optimized multibase chain. The other is in bottom field, transforming the representation of points to get the point addition and doubling formula with high efficiency and computing the formula in parallel. While confer to security, the method is equalization, which adjusts the scalar multiplication algorithm, so that point operation such as addition, doubling and trpling 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) As a generalization of double base chains, multi-base number system were very suitable for efficient computation of scalar multiplications of elliptic curves because of shorter representation length and less Hamming weight. We considered settings with different computing cost of point operations and introduced an optimized tree-based method for searching multi-base chains. Experimental results show that compared with NAF, greedy algorithm and tree based computing double base chain method, applying the multi-base representation returned by our proposed algorithms, the scalar computing costs reduced by22%,12.9%,10.6%respectively on prime elliptic curves and20.2%,11.5%,9.7%on binary elliptic curves.(2) We present new formulas of point doubling, addition and tripling on Jacobi Quartics Curve in projective redundancy coordinates. On system of chip,we add one multiplication moduler, and parallized the formula of point doubling, addition and tripling. Algorithm is practical and high efficiency, by which the whole performance point multiplication can be greatly improved, and parallel degree is as high as90%. The efficiency of new paralleled formula increased41%-49%. The novel and active attempt in the realization of formulation can further play a positive role in the development of technology application.(3) Simple power analysis, especially the early-terminating multiplication attack, which is poposed in2010, is the most devastating attack to the security of elliptic curve scalar multiplication and can retrieve the secret key in some degree. To avoid this attack, a fast and secure parallel scalar multiplication algorithm based on side channel atomic M-N-A-S-N-A-N-A is put forward. Compared with the previous methods, the new algorithm is more efficient. For192bit scalar using NAF recoding, the efficiency of the new algorithm is increased by about4.4%～56%if S/M=0.8or4.4%-61%if S/M=0.6.