SM2算法模逆加速器的设计

常 江，李险峰

（北京中电华大电子设计有限责任公司，北京100102）

SM2算法模逆加速器的设计

常 江，李险峰

（北京中电华大电子设计有限责任公司，北京100102）

SM2公钥密码在智能卡领域有广泛的应用，其运算中难以避免模逆运算，而模逆算法因为其具有幂指数级别的运算复杂度，成为制约SM2算法性能的一个重要瓶颈。以SM2算法公钥引擎为基础，巧妙地利用了已有的蒙哥马利乘法器结构，设计出了一种长度可伸缩的快速模逆算法。并复用已有模乘资源，给出了节省存储空间、不增加面积成本的硬件实现结构以及数据存储方案。其速度性能远远优于传统的费马小定理算法和扩展欧几里德算法，对比同类蒙哥马利模逆算法也有良好的性能。

模逆；SM2；蒙哥马利模乘；公钥密码；智能卡

0　引言

公钥密码又称为非对称密码，因其可解决数字签名问题，在智能卡领域有广泛的应用。近年来主要使用的公钥密码如SM2、ECC、RSA等算法中，都难以避免模逆运算。而模逆算法因为其具有幂指数级别的运算性能，成为了制约公钥算法性能的一个瓶颈。寻找性能优良、资源占用小的模逆算法，成为优化公钥算法的一个重要途径。

1　SM2算法简介

随着密码技术和计算技术的发展，目前常用的1024位RSA算法面临严重的安全威胁，国家密码管理局于2010年12月17日发布了SM2椭圆曲线公钥密码算法，并要求对现有基于RSA算法的电子认证系统、密钥管理系统、应用系统进行升级改造。SM2算法在安全性、性能上都具有优势，参见表1算法攻破时间[1]。

表1　公钥算法强度对比表

SM2算法是基于椭圆曲线上点群离散对数难题，在国际ECC算法的基础上进行改进的，主要是算法的加密过程以及密文的结构。同时，SM2算法给出了一种明文到椭圆曲线上的点的转换方式的定义。对于椭圆曲线的选择，标准中推荐用素数域 256位的椭圆曲线，推荐的椭圆曲线方程如下：

在 SM2算法标准中，通过指定 a、b系数，确定了唯一的标准曲线，a=-1，b=0时如图1所示。同时，为了将曲线映射为加密算法，SM2标准中还确定了其他参数，供算法程序使用[2]。

图1　SM2曲线坐标图

Fp上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。基于Fp域上点加、倍点在不同坐标系下的运算量，给出表2所示的统计结果。

表2　点加倍点运算量统计

由表2可知，运算量最小的是仿射坐标，其中点加运算量为3[M]+8[A]+1[I]，倍点运算量为 3[M]+6[A]+1[I]，但是此处的点加、倍点皆包含一次模逆运算，模逆运算的运算量较之模乘和模加都要大许多，故而重复量大的点加和倍点运算要尽量避免，虽然在坐标还原中仍需用到模逆，但总体上可将模逆的次数降到最低。

从表格中比较，不难发现，最优的是“仿射-Jacobi”方案，点加运算量为11[M]+7[A]，倍点运算量为10[M]+ 12[A]。

但是，采用混合坐标，在随机化点运算中，需要3次坐标还原，而坐标还原又需要用到求逆。因此，求逆成为SM2运算中难以避免的大运算量计算，成为SM2算法的严重制约。

2　有限域模逆运算

所谓求逆运算，任意a∈GF(p)，a≠0，寻找a-1∈GF(p)，使得 aa-1≡1(mod p)，则 a-1称为 a的逆元，寻找逆元的过程称为求逆运算。

对于大素数，普遍的求逆方法是基于欧几里德计算或者费马小定理，下面给出这两种经典的 GF(p)上的求逆算法。

2.1欧几里德求逆法

欧几里德定理：

输入：正整数a和b；

可以输出：d=gcd(a，b)，满足ax+by=d的整数x和y。

那么当p为素数且非a的约数，则有：

故而a-1≡x(mod p)。

故而欧几里德算法可以用来求逆，但是因为欧几里德的辗转相除需要用到除法，可以用二进制的移位来代替除法[3]，即得到以下算法：

输入：素数p和a；

输出：a-1mod p，过程如下：

2.2费马小定理模幂法

费马小定理：若p是一个素数，对任给的整数a都有 ap-1≡1(mod p)。

根据此定理，有：a·ap-2≡1(mod p)，可以得出 a-1≡ap-2(mod p)。

将求逆运算转化为模幂运算，继而分解为模乘。因为非对称算法也需要大量的模乘运算，故而一般的密码芯片都使用硬件公钥引擎来实现模乘功能，在计算模逆时可以复用模乘器。一次求逆的过程等于一次p-2为幂指数的模幂，当p为 256位时，平均概率下一次模逆等于374次模乘，运算量很大。其运算时间见表3。

表3　模逆运算实现性能对比表

而一次 256 bit SM2运算在 117 MHz下也不过用6.46 ms，最快的纯硬件欧几里德3次 256 bit模逆也占用了0.75 ms，比例达到11.6%。

3　与Montgomery模乘算法相结合的模逆算法

3.1蒙哥马利(Montgomery)概述

可以由上章看出，模逆的运算量很大，制约了SM2的运算性能，本文将结合SM2运算本身的特点，来寻找一种更为高速且节省资源的算法。

非对称算法如RSA、ECC/SM2公钥密码体制，这两种密码算法的核心运算都是模幂运算，模幂的核心运算是大数模乘。大数模乘的算法，在1985年由Montgomery提出了一种算法，目前被认为是最为适合硬件结构的模乘算法：

蒙哥马利运算是对一个输入z

实现过程大致分为3步：

其核心思想是将乘积与模数一同计算。

从蒙哥马利乘法求(ABR-1)mod n的思想出发，当寻找 a-1mod p比较困难时，转而求 a-1Rmod p，若是该算法可以更高效，则最后再进行一次蒙哥马利模乘 a-1R·1· R-1mod p即可还原为 a-1Rmod p[4]。

3.2具体算法设计

用蒙哥马利的思想来设计求逆的步骤：

对于不可逆的a，蒙哥马利逆 a-12nmod p可以根据输出(x，k)用k-n重复去除的方式得到：

若x是偶数，则x←x/2，否则x←(x+p)/2。

3.3算法论证

除了gcd(u，v)=gcd(a，p)之外，不变式ax1≡u2k(mod p)，ax2≡-v2k(mod p)也成立。若gcd(a，p)=1，则在步骤(2)的最后一次迭代后 u=1并且 x1≡a-12k(mod p)，直至最后一次迭代前，条件 p=vx1+ux2，x1≥1，v≥1，0≤u≤a都成立，因此 x1，v∈[1，p]，而在最后一次迭代时，x1←2x1≤2p；若gcd(a，p)=1，则必须有x1<2p且步骤(4)确保x1

步骤(2)的每一次迭代都把乘积 uv减少一半，而和u+v最多约减一半，初始时 u+v=a+p且 uv=ap，在最后一次迭代前 u=v=1。因此，(a+p)/2≤2k-1≤ap，致使 2n-2< 2k-1<22n且 n≤k≤2n。

在蒙哥马利模乘中，为了提高效率，选用R=2Wt≥2n。令˜=aRmod p，而gcd(a，p)=1。

4　加速模逆器的设计

由上节算法可知，经过了算法之后，只需要经过至多3个模乘和一次加法，就可以得到所需要的模逆值，对于该算法进行硬件设计，主要的动作分为存储器的读写、移位和加法，尽可能地使用现有的运算资源来完成。

从算法分析，参与运算的是 4个大数 u，v，x1，x2，若选取SM2运算为256位，则这4个大数皆为256位，存储和读取都需要耗费时间和存储单元。制约运算速度的关键是存储器的读写时间，则思路是在不过多增加存储单元的基础上，尽可能使用寄存器。

已有资源：蒙哥马利模乘器使用64-bit的双口RAM、两个128 bit的加法器、一个128 bit的减法器。加法器用来计算x1+x2，将两个加法器的输入端都作为存储器，可以存储x1和 x2，将 u存储入RAM，v写入一个256 bit的寄存器。RAM一个 cycle的最大读位宽是128 bit，那么读一次u需要2个cycle，写一次u也需要2个cycle，则进行一轮需要写u的运算，至少需要4个cycle。设计模拟器结构如图2所示。

图2　模逆器结构图

对于算法中的4步进行性能分析，见表4。

表4　模逆运算步骤分析

表5　模逆运算实现性能对比表

4步被选择的概率相等，则做一次模逆的平均速度为(1+4+2+4)×384/4+3次模乘=1 056+3×36=1 164(cycle)。

对比欧几里德扩展求逆和费马小定理求逆法的性能，结果见表5。

可见，利用已有的蒙哥马利模乘资源，在256的位宽下，相比纯硬件实现扩展欧几里德，可以将速度提高24.2倍，相比纯硬件实现费马，可以将速度提高42.4倍。

对需要3次模逆的256 bitSM2运算，3次模逆仅需要29.73 μs，比最高性能的纯硬件扩展欧几里德节省了0.720 ms，对一次签名需要时间是 6.46 ms，优化率达到11.1%，是相当可观的。

5　结论

本文结合SM2算法公钥引擎本身的特点，在使用已有资源、不增加新的面积成本的基础上，设计了易于硬件实现的、长度可伸缩的模逆加速器，并设计出其硬件结构和数据存储方案。其速度达到实现256 bit模拟运算9.91 μs@117 MHz，比文献[1]的结果 15.22 μs@117 MHz[5]还要快35%。其算法大大优于传统的费马小定理和扩展欧几里得模逆方法，又巧妙得利用了已有的蒙哥马利乘法器结构，硬件设计利用加法器的存储输入口，节省了硬件面积，成为适合非对称算法引擎的模逆设计，对于SM2算法、RSA密钥生成的速度均有较大的提升，其中SM2算法性能可提高 11.1%，显示出本文所做的工作具有重要的理论意义和实现价值。

[1]牛永川.SM2椭圆曲线公钥密码算法的快速实现研究[D].山东：山东大学数学学院，2013.

[2]国家密码管理局.SM2椭圆曲线公钥密码算法[EB/OL]. (2010-12-17).[2014-10-27].http://www.oscca.gcv.cn/News/201012/News_1197.htm.

[3]HANKERSON D，MENEZES A，VANSTONE S.Guide to elliptic curve cryptography[M].北京：电子工业出版社，2005.

[4]陈琳.基于有符号数字系统的Montgomery模逆算法及其硬件实现[J].电子学报，2012，40(3)：489-494.

[5]SAVAS E，KOC C K.The Montgomery modular inverse-revisited[C].IEEE Transactions on Computers，2000，49(7)：763-766.

The design of SM2 modular inverse algorithm accelerator

Chang Jiang，Li Xianfeng
(CEC Huada Electronic Design Co.，Ltd，Beijing 100102，China)

Shangyong Mima 2(SM2)public key cryptography has been widely applied in the making of smart card.Modular inverse is an inevitable part of this technology.Due to the complexity degree of exponential,modular inverse is the most challenging barrier in improving the function of SM2 algorism.Utilizing the SM2 algorism public key engine as the basis,by applying the existing Montgomery structure,we successfully realize the design of a length-adjustable and high-speed modular inverse algorism.Additionally,by re-utilizing the existing modular multiplication resource,this design realizes the hardware configuration and data storage plan with more storage space spared but no increase in the cost of area.Compared to the traditional Fermat theory and Extended-Euclidean，this design is excelling in its computing speed.Compared to Montgomery algorism in the same category,the quality of its function is also excellent.

modular inverse；SM2;Montgomery algorism；public key cryptography；smart card

TP309

A

0258-7998(2015)02-0131-04

10.16157/j.issn.0258-7998.2015.02.032

（2014-10-27）

常江（1986-），女，硕士，中级工程师，主要研究方向：集成电路设计、公钥算法的技术研究与设计实现。

李险峰（1975-），男，硕士，工程师，主要研究方向：集成电路低功耗设计、公钥算法安全技术研究与设计实现。