0 引言

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

1 SM2算法简介

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

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

　　y2=x3+ax+b(1)

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

　　Fp上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。基于Fp域上点加、倍点在不同坐标系下的运算量，给出表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的约数，则有：

　　ax+py=1(2)

　　ax≡1(mod p)(3)

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

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

　　输入：素数p和a；

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

　　u←a v←p

　　s1←1 s2←0

　　while(u>1)&(v>1) {

　　if(u[0]==0) u←u/2

　　if(s1[0]==0) s1=s1/2；

　　else s1=(s1+p)/2；

　　if(v[0]==0) v←v/2

　　if(s2[0]==0) s2=s2/2；

　　else s2=(s2+p)/2

　　if(u≥v) u←u-v；

　　else v←v-u；

　　s2=s2-s1

　　2.2 费马小定理模幂法

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

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

　　将求逆运算转化为模幂运算，继而分解为模乘。因为非对称算法也需要大量的模乘运算，故而一般的密码芯片都使用硬件公钥引擎来实现模乘功能，在计算模逆时可以复用模乘器。一次求逆的过程等于一次p-2为幂指数的模幂，当p为256位时，平均概率下一次模逆等于374次模乘，运算量很大。其运算时间见表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蒙哥马利模乘，令T=AB，其中0≤A，B

　　Mont(A，B)(TR-1)mod n≡(ABR-1)mod n(3)

　　实现过程大致分为3步：

　　(1)T←AB；

　　(3)If(U>n)

　　Return U-n

　　Else

　　Return U

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

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

3.2 具体算法设计

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

　　输入：奇整数z

　　输入：奇整数p>2，a∈[1，p-1]，n=[lbp]。

　　u←a，v←p，x1←1，x2←0，k←0

　　当v>0时，重复执行下列步骤：

　　(1)if v是偶数，则v←v/2，x1←2x1；

　　(2)else if u是偶数，则u←u/2，x2←2x2；

　　(3)else if v≥u，则v←(v-u)/2，x2←x2+x1，x1←2x1；

　　(4)else u←(u-v)/2，x1←x2+x1，x2←2x2。

　　k←k+1。

　　当以上步骤执行完后：

　　若u≠1，则return（“无逆”）；

　　若x1>p，则x1←x1-p；

　　返回(x1，k)。

　　对于不可逆的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。令，而gcd(a，p)=1。

　　应用3.2节中的算法找到且n≤k≤2n，若k

　　x←Mont(x，R2)=a-12kmod p

　　k←k+Wt（现在k>Wt）

　　x←Mont(x，R2)=a-12kmod p

　　x←Mont(x，22Wt-k)=a-1Rmod p

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所示。

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

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

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

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

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

5 结论

　　本文结合SM2算法公钥引擎本身的特点，在使用已有资源、不增加新的面积成本的基础上，设计了易于硬件实现的、长度可伸缩的模逆加速器，并设计出其硬件结构和数据存储方案。其速度达到实现256 bit模拟运算9.91 @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-re-visited[C].IEEE Transactions on Computers，2000，49(7)：763-766.