0 引言

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

1 SM2算法簡(jiǎn)介

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

　　SM2算法是基于橢圓曲線上點(diǎn)群離散對(duì)數(shù)難題，在國(guó)際ECC算法的基礎(chǔ)上進(jìn)行改進(jìn)的,，主要是算法的加密過程以及密文的結(jié)構(gòu),。同時(shí)，SM2算法給出了一種明文到橢圓曲線上的點(diǎn)的轉(zhuǎn)換方式的定義,。對(duì)于橢圓曲線的選擇,，標(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時(shí)如圖1所示。同時(shí),，為了將曲線映射為加密算法,，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)算,。

　　對(duì)于大素?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是一個(gè)素?cái)?shù),，對(duì)任給的整數(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)榉菍?duì)稱算法也需要大量的模乘運(yùn)算,，故而一般的密碼芯片都使用硬件公鑰引擎來實(shí)現(xiàn)模乘功能,，在計(jì)算模逆時(shí)可以復(fù)用模乘器,。一次求逆的過程等于一次p-2為冪指數(shù)的模冪,，當(dāng)p為256位時(shí)，平均概率下一次模逆等于374次模乘,，運(yùn)算量很大,。其運(yùn)算時(shí)間見表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é)省資源的算法,。

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

　　蒙哥馬利運(yùn)算是對(duì)一個(gè)輸入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比較困難時(shí),，轉(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時(shí),，重復(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)。

　　對(duì)于不可逆的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≡u(píng)2k(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],，而在最后一次迭代時(shí),，x1←2x1≤2p,；若gcd(a，p)=1,，則必須有x1<2p且步驟(4)確保x1<p,。

　　步驟(2)的每一次迭代都把乘積uv減少一半，而和u+v最多約減一半,，初始時(shí)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個(gè)模乘和一次加法,，就可以得到所需要的模逆值,，對(duì)于該算法進(jìn)行硬件設(shè)計(jì)，主要的動(dòng)作分為存儲(chǔ)器的讀寫,、移位和加法,，盡可能地使用現(xiàn)有的運(yùn)算資源來完成。

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

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

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

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

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

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

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

5 結(jié)論

　　本文結(jié)合SM2算法公鑰引擎本身的特點(diǎn),，在使用已有資源、不增加新的面積成本的基礎(chǔ)上,，設(shè)計(jì)了易于硬件實(shí)現(xiàn)的,、長(zhǎng)度可伸縮的模逆加速器，并設(shè)計(jì)出其硬件結(jié)構(gòu)和數(shù)據(jù)存儲(chǔ)方案,。其速度達(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ì)利用加法器的存儲(chǔ)輸入口，節(jié)省了硬件面積,，成為適合非對(duì)稱算法引擎的模逆設(shè)計(jì)，對(duì)于SM2算法,、RSA密鑰生成的速度均有較大的提升,，其中SM2算法性能可提高11.1%，顯示出本文所做的工作具有重要的理論意義和實(shí)現(xiàn)價(jià)值,。

　　參考文獻(xiàn)

　　[1] 牛永川.SM2橢圓曲線公鑰密碼算法的快速實(shí)現(xiàn)研究[D].山東：山東大學(xué)數(shù)學(xué)學(xué)院,，2013.

　　[2] 國(guó)家密碼管理局.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] 陳琳.基于有符號(hào)數(shù)字系統(tǒng)的Montgomery模逆算法及其硬件實(shí)現(xiàn)[J].電子學(xué)報(bào)，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.