Optimization Of ECC Computation Algorithms And Their Application In SM2 Implementation

Elliptic Curve Cryptography?ECC? is an approach to public key cryptography.Because of its higher security with shorter key and less computational cost,ECC addressed much attention.Recently,the SM2 algorithm,an ECC-based algorithm,is independently designed by China.As a key part of Chinese National Security Algorithm system,SM2 is essential to China's cybersecurity.This thesis proposes a computational efficient solution to ECC algorithms,aiming at improving SM2 implementation.The main work includes four parts as follows.?1?The thesis reviews the domestic and foreign standards of ECC and then focus on analyzing the computational complexity of SM2 and ECDSA/ECIES.The analysis shows that the point computation on the elliptic curve and the large integer computation on the prime field lead most computations.Therefore,the thesis first focuses on the point-multiplication of arbitrary integer k and arbitrary point P,of arbitrary integer k and fixed base point G,and the multipoint multiplication such as kP+lQ.Then,the thesis studies the Montgomery modular multiplication and modular inverse algorithm.?2?The running time of SM2 signature/encryption algorithm and ECDSA/ECIES is measured based on OpenSSL,an widely used open source encryption library.Test results show that SM2 signature speed is one-seventh of ECDSA?p256v1? and SM2 verification speed is one-fourth of ECDSA?p256v1?.?3?In order to improve the computational efficiency of SM2,the thesis designs and implements the point multiplication algorithm for SM2 curve,the fast reduction algorithm for SM2 prime,the fast Montgomery modular multiplication algorithm for SM2 prime,and the Montgomery modular inverse algorithm.In addition,the SM2 computation algorithm is further improved by considering the implementation platform and code:using pre-computation technology in the implementation of base point calculation algorithm;pre-calculation of the calculation intermediate quantity?1+d_A?^-1in the SM2signature algorithm implementation;using SIMD technology in code writing.?4?A test system for SM2 is developed by using C/C++,which confirms the validation of the large integer computation program,SM2 digital signature program and SM2 data encryption program.In addition,the speed tests of the SM2 signature and encryption programs are conducted,respectively.The results show that the running time of the proposed SM2 signature and encryption programs is about 20% and 25% lower than that of existing implementation.