基于模归约的国密算法SM2的快速实现方法及系统

摘要

本发明涉及计算机安全技术领域，本发明公开了基于模归约的国密算法SM2的快速实现方法及系统，包括：获取待运算的国密算法SM2；根据待运算国密算法SM2当前的计算过程，选择对应的运算模块，实现国密算法SM2的快速运算；当计算过程中遇到模加计算过程时，选择模加运算模块；当计算过程中遇到模减计算过程时，选择模减运算模块；当计算过程中遇到素域

说明书

技术领域

本发明涉及计算机安全技术领域，特别是涉及基于模归约的国密算法SM2的快速实现方法及系统。

背景技术

本部分的陈述仅仅是提到了与本发明相关的背景技术，并不必然构成现有技术。

国密算法SM2，包括：数字签名算法、密钥交换协议和公钥加密算法；国密算法SM2目前所使用的椭圆曲线参数是256位椭圆曲线参数，定义在素域上的SM2算法是在模运算的基础上实现的，其中模乘算法为核心算法，决定着SM2的运行效率，模乘运算的快慢直接决定了国密算法SM2的快慢，目前在开源算法库中对SM2的模乘运算主要使用Montgomery算法以及基于预计算的Comb算法。

SM2标准推荐了一条256比特素域上的椭圆曲线，该素数具有稀疏性质，经过核算，256比特具有同样稀疏性质的素数只有两个，另一个是NIST标准

目前各主要的SM2开源算法库在实现中对大数运算库的依赖性较强，以及与NIST标准

在实现本发明的过程中，发明人发现现有技术中存在以下技术问题：

现有SM2算法在计算过程中，数字签名算法在实现签名和验签时效率较低。浪费了大量的计算资源，特别是服务器需要进行大量的签名和验签运算的时候，现有的SM2计算方式，提高了时间复杂度，在芯片上运行时，对芯片的功耗较大，国密SM2算法运算速度慢，影响用户的使用体验。

发明内容

为了解决现有技术的不足，本发明提供了基于模归约的国密算法SM2的快速实现方法及系统；

第一方面，本发明提供了基于模归约的国密算法SM2的快速实现方法；

基于模归约的国密算法SM2的快速实现方法，包括：

获取待运算的国密算法SM2；所述待运算的国密算法SM2，包括：数字签名算法；所述数字签名算法，用于对用户的原始数据进行签名，得到对应的数字签名结果；

根据待运算国密算法SM2当前的计算过程，选择对应的运算模块，实现国密算法SM2的快速运算；

当计算过程中遇到模加计算过程时，选择模加运算模块；

当计算过程中遇到模减计算过程时，选择模减运算模块；

当计算过程中遇到素域

当计算过程中遇到阶

当计算过程中遇到模逆计算过程时，选择模逆运算模块。

第二方面，本发明提供了基于模归约的国密算法SM2的快速实现系统；

基于模归约的国密算法SM2的快速实现系统，包括：

获取模块，其被配置为：获取待运算的国密算法SM2；所述待运算的国密算法SM2，包括：数字签名算法；所述数字签名算法，用于对用户的原始数据进行签名，得到对应的数字签名结果；

快速运算模块，其被配置为：根据待运算国密算法SM2当前的计算过程，选择对应的运算模块，实现国密算法SM2的快速运算；

当计算过程中遇到模加计算过程时，选择模加运算模块；

当计算过程中遇到模减计算过程时，选择模减运算模块；

当计算过程中遇到素域

当计算过程中遇到阶

当计算过程中遇到模逆计算过程时，选择模逆运算模块。

与现有技术相比，本发明的有益效果是：

通过对国密算法SM2的数字签名算法、密钥交换协议或公钥加密算法运行过程中遇到的模加、模减、模乘和模逆过程，采用本发明设计的运算模块进行计算，大大降低了数字签名、密钥交换或公钥加密过程的时间复杂度，能够提升数字签名的速度、密钥交换的速度和公钥加密的速度，在芯片上运行时，对芯片的功耗降低，使得系统性能提升。

本发明针对SM2算法中素域特征的稀疏性质，提出了基于模归约的一种新的模运算实现方法，包括模加运算、模减运算、模乘运算、模逆运算，该算法有利于纯软件实现，也利于汇编及硬件实现，算法的运行效率优于当前已知的开源算法库,同时也为SM2的研究提供了新的方法。

本发明用Golang语言进行编程验证，所有代码均为自主开发，未调用任何开源及大数运算库，通过验证，在同类编程语言下，SM2签名运行效率优于已知开源算法库约一倍以上，验签效率大于

附图说明

构成本发明的一部分的说明书附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。

图1为实施例一的算法3：高256位归约算法（模p）；

图2为实施例一的算法5：模乘算法（阶N）。

具体实施方式

应该指出，以下详细说明都是示例性的，旨在对本发明提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本发明所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。

本实施例所有数据的获取都在符合法律法规和用户同意的基础上，对数据的合法应用。

实施例一

本实施例提供了基于模归约的国密算法SM2的快速实现方法；

基于模归约的国密算法SM2的快速实现方法，包括：

S101：获取待运算的国密算法SM2；所述待运算的国密算法SM2，包括：数字签名算法、密钥交换协议或公钥加密算法；

S102：根据待运算国密算法SM2当前的计算过程，选择对应的运算模块，实现国密算法SM2的快速运算；

当计算过程中遇到模加计算过程时，选择模加运算模块；

当计算过程中遇到模减计算过程时，选择模减运算模块；

当计算过程中遇到素域

当计算过程中遇到阶

当计算过程中遇到模逆计算过程时，选择模逆运算模块。

应理解地，所述数字签名算法，用于对用户的原始数据进行签名，得到对应的数字签名结果；所述数字签名算法用于数字签名和验证，满足多种密码应用中的身份认证和数据完整性、真实性的安全需求；

所述密钥交换协议，用于满足通信双方经过两次或可选三次信息传递过程，计算获取一个由双方共同决定的共享秘密密钥（会话密钥）。

所述公钥加密算法，用于消息加解密，消息发送者可以利用接收者的公钥对消息进行加密，接收者用对应的私钥进行解密，获取消息。

进一步地，所述数字签名算法，具体过程包括：

第1步：置

第2步：计算

第3步：产生随机数

第4步：计算椭圆曲线点

第5步：计算

第6步：计算

判断

第7步：确定数字签名

进一步地，所述当计算过程中遇到模加计算过程时，选择模加运算模块；具体包括：

S102a1：输入素数

S102a2：对待执行加法运算的加数

S102a3：令

S102a4：计算

S102a5：判断是否有溢出，如果有进位溢出则

S102a6：判断

S102a7：输出

进一步地，所述当计算过程中遇到模减计算过程时，选择模减运算模块；具体包括：

S102b1：输入素数

S102b2：对待执行减法运算的被减数

S102b3：令：

S102b4：计算

S102b6：判断

S102b7：输出

进一步地，所述当计算过程中遇到素域

S102c1：输入素数

S102c2：计算：

S102c3：计算高256位的归约值

S102c4计算：

S102c5：对

S102c6：计算：

S102c7：输出

进一步地，所述S102c3：计算高256位的归约值

S102c31：输入：

S102c32：

S102c33：

S102c34：

S102c35：

S102c36：

S102c37：

S102c38：

其中，

进一步地，所述当计算过程中遇到阶

S102d1：输入素数

预计算值

S102d2：计算：

S102d3：

S102d4：

S102d41：

和

进一步地，所述当计算过程中遇到模逆计算过程时，选择模逆运算模块；具体包括：

S102e1：输入素数

S102e2：计算

S102e3：赋初始值：

S102e4：判断

S102e41：判断

S102e42：判断

S102e43：判断

如果

返回S102e4；

S102e5：如果

S102e6：计算

S102e7：输出

SM2曲线定义在素域

该素数具有稀疏性质，本发明针对这一稀疏性质提出了基于模

基于素域的SM2算法所涉及的大数运算长度为256比特，其中包括模加、模减、模乘运算。所有数据定义为数组，数组长度与CPU的工作环境相关，假设CPU工作的环境为

数学上这个表示对应于整数

在本发明中，无特殊强调则

对于

算法1：模加算法；

输入：素数

输出：

1.

2.令

计算

3.如果有进位溢出则

4.如果

5. 输出

说明：

1.在SM2中，根据

显然加法的次数限定在

2.多个值相加的归约算法可以用于椭圆曲线点加和倍点的运算中，并有效减小计算复杂度，例如

模减算法与模加算法类似，执行减法时需要判断是否借位，并进行加

这里的

算法2：模减算法；

输入：素数

输出：

1.

2.令

计算

3.如果有借位溢出则

4.如果

5.输出

注：多个值的模减运算对于减小椭圆曲线点加及倍点运算的复杂度有重要作用，例如点加运算中计算输出点的

对于

乘法（平方）算法是计算

在SM2的设计中；

素数

式中2的指数的最大公约数为32，所以选择

对于域中元素

令

结合上述公式，可以得到约减算法：

将

基于以上公式，本发明提出了新颖的高256位归约算法，核心是利用17次加法完成

算法3：高256位归约算法(模

输入：

输出：

1.

2.

3.

4.

5.

6．

7.

附图1详细描述了该归约过程。基于以上算法，我们可以给出模乘运算，如算法4所示：

算法4：模乘运算(模

输入：素数

输出：

1.计算：

2. 调用算法3计算高256位的归约值

3. 计算：

4. 调用算法1对

5. 计算：

注：这里第3步的运算利用移位相加(减)的操作方式进行计算。

在SM2算法中，点群

在SM2协议中，需要多次调用模

Hasse定理表明

其中最高32比特的值为1，因此我们可以利用算法1的思想给出模

算法5：模乘运算(模

输入：素数

输出：

1.计算：

2.

3.

3.1

3.2

3.3

4.输出

说明：

1.第2步为初始化

2.第3.1步对

3.第3.2步乘法计算中只需要计算

由于

模逆运算一般使用扩展欧几里得算法或者费马定理，但由于本发明已经实现了高效的模乘算法，因此结合“部分蒙哥马利求逆算法”(Partial Montgomery inversion)，我们实现了更加高效的模逆运算，如算法6所示：

算法6：基于蒙哥马利方法的模逆运算；

输入：素数

输出：

1.计算

2.

3. While

3.1 While

3.2 While

3.3 If

else

4.If

//2-4步为Partial Montgomery 算法，此时：

5.计算：

6.输出

说明：

1.相比标准二元求逆法，部分蒙哥马利算法中，3.3步中计算

2.第4步结束时：

因此需要第5步消去

3.第1步和第5步的模乘计算，可在移位后调用算法4中的第2-5步进行归约计算，复杂度与整体算法相比可以忽略。但如果没有高效的模乘运算，则该算法并不适用。

4.通过编程测试，与标准的二元求逆法相比，该算法复杂度减少约

模加、模减、模乘、模逆构成椭圆曲线运算的基础，在SM2的点的基本运算中，我们调用以上基础模运算模块，按照SM2椭圆曲线算法标准完成点加与倍点运算。为了与各开源算法库进行同等条件下的比较，按照当前各开源库通用的椭圆曲线标量乘法实现方法，在点乘运算中，对于基点的标量乘法按照窗口为7的预计算点值的方法进行实现；对于非固定点的标量乘法按照窗口为5的

SM2协议实现按照SM2标准算法实现。由于本发明只针对SM2基础模运算，椭圆曲线点的运算及SM2协议实现不属于本发明的内容，因此不再赘述。

基于模归约方法的SM2实现方法对SM2的实现效率进行了有效提升，我们以Golang语言，结合汇编算法进行验证。

验证条件：以签名验签速度为参照，基点标量乘法预计算点值窗口为7(即预计算37*64个点值)，非固定点标量乘法

验证结果：通过测试当前开源代码库，各主要编程语言下SM2签名最快的运算速度为每秒5万次，验签速度为每秒1.3万次。

我们在新的方法下签名运算速度大于每秒12万次，速度增加

实施例二

本实施例提供了基于模归约的国密算法SM2的快速实现系统；

基于模归约的国密算法SM2的快速实现系统，包括：

获取模块，其被配置为：获取待运算的国密算法SM2；所述待运算的国密算法SM2，包括：数字签名算法；所述数字签名算法，用于对用户的原始数据进行签名，得到对应的数字签名结果；

快速运算模块，其被配置为：根据待运算国密算法SM2当前的计算过程，选择对应的运算模块，实现国密算法SM2的快速运算；

当计算过程中遇到模加计算过程时，选择模加运算模块；

当计算过程中遇到模减计算过程时，选择模减运算模块；

当计算过程中遇到素域

当计算过程中遇到阶

当计算过程中遇到模逆计算过程时，选择模逆运算模块。

此处需要说明的是，上述获取模块和快速运算模块对应于实施例一中的步骤S101至S102，上述模块与对应的步骤所实现的示例和应用场景相同，但不限于上述实施例一所公开的内容。

需要说明的是，上述模块作为系统的一部分可以在诸如一组计算机可执行指令的计算机系统中执行。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。