关于国密算法SM2的模乘优化方法  

On Optimization of Modulo Multiplication Methods for SM2

作　　者：于子钦 许光午 YU Zi-Qin;XU Guang-Wu(Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,Shandong University,Qingdao 266237,China;School of Cyber Science and Technology,Shandong University,Qingdao 266237,China;Shandong Institute of Blockchain,Jinan 250101,China;Quan Cheng Laboratory,Jinan 250103,China)

机构地区：[1]山东大学密码技术与信息安全教育部重点实验室,青岛266237 [2]山东大学网络空间安全学院,青岛266237 [3]山东区块链研究院,济南250101 [4]泉城实验室,济南250103

出　　处：《密码学报（中英文）》2024年第3期649-661,共13页Journal of Cryptologic Research

基　　金：国家重点研发计划(2022YFB2701700);国家自然科学基金(12271306)。

摘　　要：为了提高运算效率,密码学中一些标准的椭圆曲线所在的基域特征常为广义Mersenne素数,如NIST曲线P-256和国密SM2.在基本算术运算中,这样特殊的素数使得影响最大的模乘运算变得非常高效.对于P-256,Brown等利用Solinas方法设计的快速模约减算法可以归结成计算9个由字的向量组成的中间变量的代数和.对于SM2也有一些相关研究,但情况似乎没有那么简单.目前这方面最好的结果需要14个(字的向量组成的)中间变量.本文的目的是推进SM2素域上的快速模乘运算,以期得到接近NIST P-256的模约减算法.具体地,本文提出了两个优化方法.在第一个结果中,就SM2素数的情形加细了Solinas和Brown等人的处理方法,所需的(字的向量的)中间变量个数降低到13.在第二个结果中,采用一种新的处理技巧,通过对运算公式进行适当变换来消去变量以进一步优化,得到的方法只需11个(字的向量的)中间变量.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).

关 键 词：SM2椭圆曲线 快速模乘 广义Mersenne素数 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]