Fast Implementation Of Public Key Cryptographic Algorithm SM2Based On Elliptic Curves

Fast implementation of Elliptic Curve Cryptography (ECC for short) has been a hot topic all the time, because of its importance in practice-based on it we can construct diverse cryptographic schemes such as data encryptions, key exchanges, and digital signatures. In this paper we study several algo-rithm problems in the fast implementation of ECC on binary extension field F2m, together with one of their applications, the software implementation of the newly proposed public-key cryptosystem SM2. The main contents are as follows:1. We analyze the basic operations like multiplication, square, modular reduction, modular multiplication and inversion on F2m which are commonly used and then put forward more appropriate methods to improve the speed. Specifically, for polynomial modular multiplication, two classical methods are compared:one is to perform the multiplication and the modular reduction at the same time; the other is to compute the two operations in serial. What’s more, during the computation of multiplication, we test both the Comb win-dow method and Karatsuba method, while modular reduction is accomplished by using reductions of modulo a trinomial. Our result shows that modular multiplication using the Comb window method and the reduction of modulo a trinomial is the most efficient. For squaring operation, a look-up table method can be exploited to achieve much faster speed compared to the ordinary mul-tiplication. And we also examine the polynomial inversion usually done by Euclidean algorithm. Its time complexity can be reduced by making use of our new algorithm when computing the inverse of many field elements.2. We discuss how to choose the coordinate system. ECC can be repre-sented by affine coordinates, standard projective coordinates, Jacobian projec-tive coordinates and Lopez&Dahab projective coordinates over binary fields, and optimization can be got by making different choices for concrete curves. And our conclusion here for SM2is that point addition and doubling are the fastest in Lopez&Dahab projective coordinates.3. We introduce three implementation methods for scalar multiplication, which are binary algorithm, NAF algorithm and WNAF algorithm, respec-tively. Among them WNAF algorithm based on signed binary representation is the fastest. When the window size is four, our implementation performs as fast as calling the functions in Miracl, one of the most classic and widely used library in cryptography, for parameter m=193or m=256.4. We implement Digital Signature Algorithm, Key Exchange Protocol and Public Key Encryption Algorithm in the SM2cryptosystem as the confir-mation of our conclusions above. And the experimental results are presented in last of our paper.