常 江，李險峰

（北京中電華大電子設(shè)計有限責(zé)任公司，北京100102）

SM2算法模逆加速器的設(shè)計

常 江，李險峰

（北京中電華大電子設(shè)計有限責(zé)任公司，北京100102）

SM2公鑰密碼在智能卡領(lǐng)域有廣泛的應(yīng)用，其運算中難以避免模逆運算，而模逆算法因為其具有冪指數(shù)級別的運算復(fù)雜度，成為制約SM2算法性能的一個重要瓶頸。以SM2算法公鑰引擎為基礎(chǔ)，巧妙地利用了已有的蒙哥馬利乘法器結(jié)構(gòu)，設(shè)計出了一種長度可伸縮的快速模逆算法。并復(fù)用已有模乘資源，給出了節(jié)省存儲空間、不增加面積成本的硬件實現(xiàn)結(jié)構(gòu)以及數(shù)據(jù)存儲方案。其速度性能遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的費馬小定理算法和擴展歐幾里德算法，對比同類蒙哥馬利模逆算法也有良好的性能。

模逆；SM2；蒙哥馬利模乘；公鑰密碼；智能卡

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)進行升級改造。SM2算法在安全性、性能上都具有優(yōu)勢，參見表1算法攻破時間[1]。

表1　公鑰算法強度對比表

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

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

圖1　SM2曲線坐標(biāo)圖

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

表2　點加倍點運算量統(tǒng)計

由表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)，在隨機化點運算中，需要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ù)，則有：

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

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

輸入：素數(shù)p和a；

輸出：a-1mod p，過程如下：

2.2費馬小定理模冪法

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

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

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

表3　模逆運算實現(xiàn)性能對比表

而一次 256 bit SM2運算在 117 MHz下也不過用6.46 ms，最快的純硬件歐幾里德3次 256 bit模逆也占用了0.75 ms，比例達到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

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

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

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

3.2具體算法設(shè)計

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

對于不可逆的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

步驟(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。令?=aRmod p，而gcd(a，p)=1。

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

由上節(jié)算法可知，經(jīng)過了算法之后，只需要經(jīng)過至多3個模乘和一次加法，就可以得到所需要的模逆值，對于該算法進行硬件設(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，則進行一輪需要寫u的運算，至少需要4個cycle。設(shè)計模擬器結(jié)構(gòu)如圖2所示。

圖2　模逆器結(jié)構(gòu)圖

對于算法中的4步進行性能分析，見表4。

表4　模逆運算步驟分析

表5　模逆運算實現(xiàn)性能對比表

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

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

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

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

5　結(jié)論

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

The design of SM2 modular inverse algorithm accelerator

Chang Jiang，Li Xianfeng
(CEC Huada Electronic Design Co.，Ltd，Beijing 100102，China)

Shangyong Mima 2(SM2)public key cryptography has been widely applied in the making of smart card.Modular inverse is an inevitable part of this technology.Due to the complexity degree of exponential,modular inverse is the most challenging barrier in improving the function of SM2 algorism.Utilizing the SM2 algorism public key engine as the basis,by applying the existing Montgomery structure,we successfully realize the design of a length-adjustable and high-speed modular inverse algorism.Additionally,by re-utilizing the existing modular multiplication resource,this design realizes the hardware configuration and data storage plan with more storage space spared but no increase in the cost of area.Compared to the traditional Fermat theory and Extended-Euclidean，this design is excelling in its computing speed.Compared to Montgomery algorism in the same category,the quality of its function is also excellent.

modular inverse；SM2;Montgomery algorism；public key cryptography；smart card

TP309

A

0258-7998(2015)02-0131-04

10.16157/j.issn.0258-7998.2015.02.032

（2014-10-27）

常江（1986-），女，碩士，中級工程師，主要研究方向：集成電路設(shè)計、公鑰算法的技術(shù)研究與設(shè)計實現(xiàn)。

李險峰（1975-），男，碩士，工程師，主要研究方向：集成電路低功耗設(shè)計、公鑰算法安全技術(shù)研究與設(shè)計實現(xiàn)。