The Fast Implementation Of ECC Scalar Multiplication Over GF(2~m)

The fast algorithms,software and hardware implementation of scalar multiplication(SM) in elliptic curve cryptography(ECC) over binary extension field GF(2~m) is researched.Innovation are proposed from finite field operation,elliptic point operation and SM methods.The Comb algorithm with windows and serial-parallel multiplier are improved.Fast algorithms of square,module reduction,double-add and SM are proposed.A ECC software and hardware cooperative process system and SM IP core are designed by using SOPC.In this paper,the following improvement and innovation are presented:1 .For the Comb algorithm of multiplication with window,a w-Comb algorithm is proposed due to the size of pre-compute table is reduced toω/2~ω.A algorithm of w-Comb with slide window is also proposed.The size of pre-compute table is reduce to 25%, and the speed is increased by 1.2%～10%(163≤m≤359).2. A serial-parallel multiplier based on w-Comb algorithm is proposed to reduce the compolexity of circuit, by using w-Comb algorithm to compute the parallel partial product.It can complete one multiplication by(?)·(?)+1 clocks.It is flexible to use the LE and registers.3.In the design of reconfiguration ECC hardware system,a parallelable multiplier is proposed to make use of free hardware resource when the field is changed.lt can parallelly compute two multiplication to accelerate SM when the field length is less than half of maximum and can be applied to the serial-parallel multiplier.4.A fast algorithm and hardware architecture of square is proposed to instead of multiplication when the reduction polynomial is arbitrary.5.A new fast algorithm based on fixed trinomial or pentanomial(FTOP) algorithm is proposed for the module reduction .By dynamically counting the index and offset of grouping words,the disadvantage of FTOP that only available for fixed reduction polynomial gets over.The proposed algorithm is faster than the one-time-one-bit algorithm when reduction polynomial has less terms of 123(m＜719), maximum 89%, average about 30%.6.On the basis of analysis and indication,the principle and method to reduce inverse of SM in the affine coordinates is presented.7.By using one inverse,a fast algorithm of double-add operation is proposed .The amount of field operation is reduced by 5.6%～25%,and even more 25%～36.7% by using two multiplier.8.By using the double-add operation,new efficient NAF add-subtration algorithm and Montgomery algorithm are proposed to suit the fast implementatioin of SM.9.A IP core of SM is designed by using FPGA.A ECC software and hardware co-process system is also designed based on SOPC. It is flexible,expandable and versatile.