0 引言

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

1 SM2算法簡介

　　隨著密碼技術(shù)和計算技術(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算法是基于橢圓曲線上點群離散對數(shù)難題,，在國際ECC算法的基礎(chǔ)上進(jìn)行改進(jìn)的,，主要是算法的加密過程以及密文的結(jié)構(gòu)。同時,，SM2算法給出了一種明文到橢圓曲線上的點的轉(zhuǎn)換方式的定義,。對于橢圓曲線的選擇，標(biāo)準(zhǔn)中推薦用素數(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)表示,?；贔p域上點加、倍點在不同坐標(biāo)系下的運算量,，給出表2所示的統(tǒng)計結(jié)果,。

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

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

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

2 有限域模逆運算

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

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

　　2.1 歐幾里德求逆法

　　歐幾里德定理：

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

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

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

　　ax+py=1(2)

　　ax≡1(mod p)(3)

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

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

　　輸入：素數(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 費馬小定理模冪法

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

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

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

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

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

　　3.1 蒙哥馬利(Montgomery)概述

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

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

　　蒙哥馬利運算是對一個輸入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)

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

　　(1)T←AB,；

　　(3)If(U>n)

　　Return U-n

　　Else

　　Return U

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

　　從蒙哥馬利乘法求(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è)計

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

　　輸入：奇整數(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è)計

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

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

　　已有資源：蒙哥馬利模乘器使用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,，則進(jìn)行一輪需要寫u的運算,，至少需要4個cycle。設(shè)計模擬器結(jié)構(gòu)如圖2所示,。

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

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

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

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

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

5 結(jié)論

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

　　參考文獻(xiàn)

　　[1] 牛永川.SM2橢圓曲線公鑰密碼算法的快速實現(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模逆算法及其硬件實現(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.