关于国密算法SM2的模乘优化方法OA北大核心CSTPCD

In order to achieve high efficiency of elliptic curve based cryptographic algorithms,the underlying fields of several standard elliptic curves are chosen to have generalized Mersenne primes as their characteristics.For example,the NIST curve P-256 and the China national standard cryp-tographic algorithm SM2.Those primes in special form can significantly reduce the cost to compute modulo multiplication,which is the most expensive basic arithmetic operation.For P-256,by using the ideas of Solinas,Brown et al.designed a fast modular reduction algorithm that calculates an algebraic sum involving 9 intermediate variables,each variable is a vector of words.For the case of SM2,this problem has also been investigated by some research works,however,the situation seems not that simple.The best results in this topic require 14 intermediate variables(vectors of words).This paper focuses on the fast modulo multiplication operation on the SM2 prime field.More specifically,two optimization methods are proposed.In the first optimization,the Solinas method is refined for the case of SM2,and the number of required intermediate variables(vectors of words)is reduced to 13.In the second optimization,the calculation formula is further optimized and appropriate transformations to eliminate variables.The resulting method requires only 11 intermediate variables(vectors of words).