0 引言

　　公鑰密碼又稱為非對稱密碼，因其可解決數(shù)字簽名問題，在智能卡領(lǐng)域有廣泛的應(yīng)用。近年來主要使用的公鑰密碼如SM2、ECC、RSA等算法中，都難以避免模逆運(yùn)算。而模逆算法因?yàn)槠渚哂袃缰笖?shù)級別的運(yùn)算性能，成為了制約公鑰算法性能的一個瓶頸。尋找性能優(yōu)良、資源占用小的模逆算法，成為優(yōu)化公鑰算法的一個重要途徑。

1 SM2算法簡介

　　隨著密碼技術(shù)和計(jì)算技術(shù)的發(fā)展，目前常用的1024位RSA算法面臨嚴(yán)重的安全威脅，國家密碼管理局于2010年12月17日發(fā)布了SM2橢圓曲線公鑰密碼算法，并要求對現(xiàn)有基于RSA算法的電子認(rèn)證系統(tǒng)、密鑰管理系統(tǒng)、應(yīng)用系統(tǒng)進(jìn)行升級改造。SM2算法在安全性、性能上都具有優(yōu)勢，參見表1算法攻破時間[1]。

　　SM2算法是基于橢圓曲線上點(diǎn)群離散對數(shù)難題，在國際ECC算法的基礎(chǔ)上進(jìn)行改進(jìn)的，主要是算法的加密過程以及密文的結(jié)構(gòu)。同時，SM2算法給出了一種明文到橢圓曲線上的點(diǎn)的轉(zhuǎn)換方式的定義。對于橢圓曲線的選擇，標(biāo)準(zhǔn)中推薦用素?cái)?shù)域256位的橢圓曲線，推薦的橢圓曲線方程如下：

　　y2=x3+ax+b(1)

　　在SM2算法標(biāo)準(zhǔn)中，通過指定a、b系數(shù)，確定了唯一的標(biāo)準(zhǔn)曲線，a=-1，b=0時如圖1所示。同時，為了將曲線映射為加密算法，SM2標(biāo)準(zhǔn)中還確定了其他參數(shù)，供算法程序使用[2]。

　　Fp上橢圓曲線常用的表示形式有兩種：仿射坐標(biāo)表示和射影坐標(biāo)表示。基于Fp域上點(diǎn)加、倍點(diǎn)在不同坐標(biāo)系下的運(yùn)算量，給出表2所示的統(tǒng)計(jì)結(jié)果。

　　由表2可知，運(yùn)算量最小的是仿射坐標(biāo)，其中點(diǎn)加運(yùn)算量為3[M]+8[A]+1[I]，倍點(diǎn)運(yùn)算量為3[M]+6[A]+1[I]，但是此處的點(diǎn)加、倍點(diǎn)皆包含一次模逆運(yùn)算，模逆運(yùn)算的運(yùn)算量較之模乘和模加都要大許多，故而重復(fù)量大的點(diǎn)加和倍點(diǎn)運(yùn)算要盡量避免，雖然在坐標(biāo)還原中仍需用到模逆，但總體上可將模逆的次數(shù)降到最低。

　　從表格中比較，不難發(fā)現(xiàn)，最優(yōu)的是“仿射-Jacobi”方案，點(diǎn)加運(yùn)算量為11[M]+7[A]，倍點(diǎn)運(yùn)算量為10[M]+12[A]。

　　但是，采用混合坐標(biāo)，在隨機(jī)化點(diǎn)運(yùn)算中，需要3次坐標(biāo)還原，而坐標(biāo)還原又需要用到求逆。因此，求逆成為SM2運(yùn)算中難以避免的大運(yùn)算量計(jì)算，成為SM2算法的嚴(yán)重制約。

2 有限域模逆運(yùn)算

　　所謂求逆運(yùn)算，任意a∈GF(p)，a≠0，尋找a-1∈GF(p)，使得aa-1≡1(mod p)，則a-1稱為a的逆元，尋找逆元的過程稱為求逆運(yùn)算。

　　對于大素?cái)?shù)，普遍的求逆方法是基于歐幾里德計(jì)算或者費(fèi)馬小定理，下面給出這兩種經(jīng)典的GF(p)上的求逆算法。

　　2.1 歐幾里德求逆法

　　歐幾里德定理：

　　輸入：正整數(shù)a和b；

　　可以輸出：d=gcd(a，b)，滿足ax+by=d的整數(shù)x和y。

　　那么當(dāng)p為素?cái)?shù)且非a的約數(shù)，則有：

　　ax+py=1(2)

　　ax≡1(mod p)(3)

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

　　故而歐幾里德算法可以用來求逆，但是因?yàn)闅W幾里德的輾轉(zhuǎn)相除需要用到除法，可以用二進(jìn)制的移位來代替除法[3]，即得到以下算法：

　　輸入：素?cái)?shù)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 費(fèi)馬小定理模冪法

　　費(fèi)馬小定理：若p是一個素?cái)?shù)，對任給的整數(shù)a都有ap-1≡1(mod p)。

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

　　將求逆運(yùn)算轉(zhuǎn)化為模冪運(yùn)算，繼而分解為模乘。因?yàn)榉菍ΨQ算法也需要大量的模乘運(yùn)算，故而一般的密碼芯片都使用硬件公鑰引擎來實(shí)現(xiàn)模乘功能，在計(jì)算模逆時可以復(fù)用模乘器。一次求逆的過程等于一次p-2為冪指數(shù)的模冪，當(dāng)p為256位時，平均概率下一次模逆等于374次模乘，運(yùn)算量很大。其運(yùn)算時間見表3。

　　而一次256 bit SM2運(yùn)算在117 MHz下也不過用6.46 ms，最快的純硬件歐幾里德3次256 bit模逆也占用了0.75 ms，比例達(dá)到11.6%。

3 與Montgomery模乘算法相結(jié)合的模逆算法

　　3.1 蒙哥馬利(Montgomery)概述

　　可以由上章看出，模逆的運(yùn)算量很大，制約了SM2的運(yùn)算性能，本文將結(jié)合SM2運(yùn)算本身的特點(diǎn)，來尋找一種更為高速且節(jié)省資源的算法。

　　非對稱算法如RSA、ECC/SM2公鑰密碼體制，這兩種密碼算法的核心運(yùn)算都是模冪運(yùn)算，模冪的核心運(yùn)算是大數(shù)模乘。大數(shù)模乘的算法，在1985年由Montgomery提出了一種算法，目前被認(rèn)為是最為適合硬件結(jié)構(gòu)的模乘算法：

　　蒙哥馬利運(yùn)算是對一個輸入z<pR，產(chǎn)生zR-1mod p，那么蒙哥馬利模乘，令T=AB，其中0≤A，B<n，則設(shè)：

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

　　實(shí)現(xiàn)過程大致分為3步：

　　(1)T←AB；

　　(3)If(U>n)

　　Return U-n

　　Else

　　Return U

　　其核心思想是將乘積與模數(shù)一同計(jì)算。

　　從蒙哥馬利乘法求(ABR-1)mod n的思想出發(fā)，當(dāng)尋找a-1mod p比較困難時，轉(zhuǎn)而求a-1Rmod p，若是該算法可以更高效，則最后再進(jìn)行一次蒙哥馬利模乘a-1R·1·R-1mod p即可還原為a-1Rmod p[4]。

　　3.2 具體算法設(shè)計(jì)

　　用蒙哥馬利的思想來設(shè)計(jì)求逆的步驟：

　　輸入：奇整數(shù)z<pR且zR-1mod p；

　　輸入：奇整數(shù)p>2，a∈[1，p-1]，n=[lbp]。

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

　　當(dāng)v>0時，重復(fù)執(zhí)行下列步驟：

　　(1)if  v是偶數(shù)，則v←v/2，x1←2x1；

　　(2)else if  u是偶數(shù)，則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。

　　當(dāng)以上步驟執(zhí)行完后：

　　若u≠1，則return（“無逆”）；

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

　　返回(x1，k)。

　　對于不可逆的a，蒙哥馬利逆a-12nmod p可以根據(jù)輸出(x，k)用k-n重復(fù)去除的方式得到：

　　若x是偶數(shù)，則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<p。

　　步驟(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。

　　應(yīng)用3.2節(jié)中的算法找到且n≤k≤2n，若k<Wt，則：

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

　　k←k+Wt（現(xiàn)在k>Wt）

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

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

4 加速模逆器的設(shè)計(jì)

　　由上節(jié)算法可知，經(jīng)過了算法之后，只需要經(jīng)過至多3個模乘和一次加法，就可以得到所需要的模逆值，對于該算法進(jìn)行硬件設(shè)計(jì)，主要的動作分為存儲器的讀寫、移位和加法，盡可能地使用現(xiàn)有的運(yùn)算資源來完成。

　　從算法分析，參與運(yùn)算的是4個大數(shù)u，v，x1，x2，若選取SM2運(yùn)算為256位，則這4個大數(shù)皆為256位，存儲和讀取都需要耗費(fèi)時間和存儲單元。制約運(yùn)算速度的關(guān)鍵是存儲器的讀寫時間，則思路是在不過多增加存儲單元的基礎(chǔ)上，盡可能使用寄存器。

　　已有資源：蒙哥馬利模乘器使用64-bit的雙口RAM、兩個128 bit的加法器、一個128 bit的減法器。加法器用來計(jì)算x1+x2，將兩個加法器的輸入端都作為存儲器，可以存儲x1和x2，將u存儲入RAM，v寫入一個256 bit的寄存器。RAM一個cycle的最大讀位寬是128 bit，那么讀一次u需要2個cycle，寫一次u也需要2個cycle，則進(jìn)行一輪需要寫u的運(yùn)算，至少需要4個cycle。設(shè)計(jì)模擬器結(jié)構(gòu)如圖2所示。

　　對于算法中的4步進(jìn)行性能分析，見表4。

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

　　對比歐幾里德擴(kuò)展求逆和費(fèi)馬小定理求逆法的性能，結(jié)果見表5。

　　可見，利用已有的蒙哥馬利模乘資源，在256的位寬下，相比純硬件實(shí)現(xiàn)擴(kuò)展歐幾里德，可以將速度提高24.2倍，相比純硬件實(shí)現(xiàn)費(fèi)馬，可以將速度提高42.4倍。

　　對需要3次模逆的256 bit  SM2運(yùn)算，3次模逆僅需要29.73 ?滋s，比最高性能的純硬件擴(kuò)展歐幾里德節(jié)省了0.720 ms，對一次簽名需要時間是6.46 ms，優(yōu)化率達(dá)到11.1%，是相當(dāng)可觀的。

5 結(jié)論

　　本文結(jié)合SM2算法公鑰引擎本身的特點(diǎn)，在使用已有資源、不增加新的面積成本的基礎(chǔ)上，設(shè)計(jì)了易于硬件實(shí)現(xiàn)的、長度可伸縮的模逆加速器，并設(shè)計(jì)出其硬件結(jié)構(gòu)和數(shù)據(jù)存儲方案。其速度達(dá)到實(shí)現(xiàn)256 bit模擬運(yùn)算9.91 @117 MHz，比文獻(xiàn)[1]的結(jié)果15.22 s@117 MHz[5]還要快35%。其算法大大優(yōu)于傳統(tǒng)的費(fèi)馬小定理和擴(kuò)展歐幾里得模逆方法，又巧妙得利用了已有的蒙哥馬利乘法器結(jié)構(gòu)，硬件設(shè)計(jì)利用加法器的存儲輸入口，節(jié)省了硬件面積，成為適合非對稱算法引擎的模逆設(shè)計(jì)，對于SM2算法、RSA密鑰生成的速度均有較大的提升，其中SM2算法性能可提高11.1%，顯示出本文所做的工作具有重要的理論意義和實(shí)現(xiàn)價值。

　　參考文獻(xiàn)

　　[1] 牛永川.SM2橢圓曲線公鑰密碼算法的快速實(shí)現(xiàn)研究[D].山東：山東大學(xué)數(shù)學(xué)學(xué)院，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].北京：電子工業(yè)出版社，2005.

　　[4] 陳琳.基于有符號數(shù)字系統(tǒng)的Montgomery模逆算法及其硬件實(shí)現(xiàn)[J].電子學(xué)報，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.