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上橢圓曲線常用的表示形式有兩種：仿射坐標表示和射影坐標表示?；贔p域上點加、倍點在不同坐標系下的運算量，給出表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<pR，產生zR-1mod p，那么蒙哥馬利模乘，令T=AB，其中0≤A，B<n，則設：

　　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<pR且zR-1mod p；

　　輸入：奇整數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<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。

　　應用3.2節中的算法找到且n≤k≤2n，若k<Wt，則：

　　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.