SM2公钥算法中大数除法的设计与硬件实现

◆陈思捷 邸红叶 张金霞



SM2公钥算法中大数除法的设计与硬件实现

◆陈思捷 邸红叶 张金霞

(中国电子科技集团公司第十五研究所后勤信息化事业部 北京 100083)

模运算作为SM2椭圆曲线公钥密码算法的一种基本运算，其前提是除法运算，因此大数除法运算速率及硬件实现是影响公钥密码算法性能的一个关键因素。本文对大数除法进行了深入研究，提出了一种取位拼接将除法转换为减法的设计思想，并给出了该算法在SM2公钥密码算法协处理器中的硬件实现。

SM2；大数除法；公钥密码；椭圆曲线；模运算

0 引言

随着电子通讯技术的发展，网络信息的安全存储、安全传输、安全处理的重要性越来越显著。作为密码学中的重要手段，公钥密码体系能够有效地解决公共信道上的身份认证、数据私密性、不可否认性等问题，其中，椭圆曲线密码[1]由于在安全性、计算量、处理速度、存储空间等方面的诸多优势，已经成为继RSA[2]密码算法后被高度重视的公钥密码算法。国际上的相关标准化组织已经开始对其进行标准化工作，国内也将SM2椭圆曲线公钥密码算法[3]作为密码行业标准。在信息安全领域，SM2公钥密码算法既可以用于数据加解密，又可以用于数字签名认证，具有广泛应用市场。

为了提高运算速度，业内通常采用协处理器的方式加速运算。在SM2公钥密码算法协处理器的硬件实现过程中，模运算广泛存在，而大数除法是其前提。然而，大数除法在硬件实现上较为困难且运算速度较低，成为影响公钥密码算法效率提升的关键因素。因此，对大数除法进行合理设计，在硬件上提高其运算效率具有重大意义[4-9]。本文将对大数除法的算法进行分析，给出一种行之有效的大数除法器的实现方法。

1 算法原理

1.1预备知识

（1）点乘中的除法运算

此运算称为点乘[11]运算，可以通过多次调用点加得到运算结果。

可以看出在坐标转换过程中需要调用大数除法。

（2）模乘中的除法运算

（3）模逆中的除法运算

1.2本文算法原理

然而对于二进制数据，各位非0即1，因此在除法运算中也是非0即1，我们可以直接将除法运算简化为减法运算[14]，而不再需要中间的判断取位商过程。

算法流程如下：

START

②区间判断，

ENDFOR

END

START

END

1.3优化流程

START

②区间判断，

ENDFOR

END

在SM2椭圆曲线公钥密码算法中，大数除法主要用于模逆、坐标转换、模乘等运算，除数多为较大的素数，因此增加对除数的判断可以大幅缩减大数除法运算周期，提高SM2运算效率。

2 大数除法硬件实现

SM2椭圆曲线公钥密码算法使用素数域256位椭圆曲线，我们以256位大数除法、32位协处理器为例进行详细说明，若被除数有效位宽为256，除数有效位宽为152，即：

图1 区间划分流程

结合上述大数除法模块的硬件实现方法及256位大数除法举例，可知：

3 大数除法在SM2协处理器中的实现及应用分析

图2 SM2协处理器对大数除法器的控制

从1.1节预备知识中我们可以看到，大数除法在SM2椭圆曲线公钥密码算法的具体应用中还存在两种特殊情况：32位除法及大数幂除法。

3.1 32位除法

32位除法原理同大数除法相同，区别在于除了在第一个周期从RAM中读取数据之外，其余都是利用内部32位寄存器直接实现操作流程，无需浪费多个周期从RAM中读数据、写数据等，节省计算周期。

3.2幂除法

幂除法的原理和大数除法相同，区别在于幂除法的被除数是可以确定的几个数据，是由数据位宽规格来选择的，该被除数可以不进行存储。这样在较耗费存储空间的SM2椭圆曲线公钥密码算法协处理器运算中，通过合理规划，节省硬件开销空间。

由于这两种特殊状况的存在，在大数除法硬件实现中，可以通过增加端口控制信号，对普通大数除法、32位除法、幂除法进行不同处理，而不是统一按照普通大数除法的流程进行处理。32位除法与普通大数除法相比，可以节省从RAM读写数据所用周期；幂除法与普通大数除法相比，对于存储空间的使用更加合理。

4 结束语

本文设计了一种可用于公钥密码算法中的通用大数除法器并讨论了其在SM2椭圆曲线公钥密码算法中的硬件实现及应用。该大数除法器可以扩展至1024位的大数除法运算，通过优化流程、合理设计，可以有效缩减大数除法运算周期，合理分配存储空间，提高SM2椭圆曲线公钥密码算法的运算效率。

[1]KoblizeN.ElliptlicCurveCryptosystem[J].Mathematicsof Computation, 1987.

[2]Rivest R L, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-key Cryptosystem [J]. Communication of the ACM, 1978.

[3]GM/T 0003.1-2012, SM2椭圆曲线公钥密码算法[S].

[4]刘墨德.Newton迭代法及其改进[J].三明学院学报， 2007.

[5]章昭辉，王晓蒲，霍剑青.公钥密码体制中快速模算法的研究[J].计算机工程与应用, 2002.

[6]童元满，戴奎，王志英.基于SD数据表示的大数除法VLSI高速实现[J].计算机工程与科学，2006.

[7]刑卫，宋东平.大数相除的快速算法[J].密码与信息，1996.

[8]王刘成，林永才，姜文刚.快速高精度除法算法的FPGA实现[J].计算机工程，2011.

[9]李占才，王许书，涂序彦. RSA快速硬件实现研究[M]. 计算机研究与发展，2001.

[10]张焕国译.D.Hankerson.椭圆曲线密码学导论[M].电子工业出版社，2005.

[11]王庆先.有限域运算和椭圆曲线数乘运算研究[D].成都:电子科技大学，2006.

[12]陈逢林, 苏厚勤.Montgomery算法的改进及其在RSA中的运用[J].计算机应用于软件, 2006.

[13]王建.椭圆曲线加密体制的双有限域算法及其硬件实现[D].北京:北京大学，2008.

[14]David A. P, John L.H.郑伟民译.计算机组成与设计:硬件/软件接口[M].机械工业出版社，2007.