常 江，李險(xiǎn)峰

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

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

常 江，李險(xiǎn)峰

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

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

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

0　引言

公鑰密碼又稱為非對(duì)稱密碼，因其可解決數(shù)字簽名問(wèn)題，在智能卡領(lǐng)域有廣泛的應(yīng)用。近年來(lái)主要使用的公鑰密碼如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ì)，參見(jiàn)表1算法攻破時(shí)間[1]。

表1　公鑰算法強(qiáng)度對(duì)比表

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

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

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

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

表2　點(diǎn)加倍點(diǎn)運(yùn)算量統(tǒng)計(jì)

由表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的逆元，尋找逆元的過(guò)程稱為求逆運(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ù)，則有：

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

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

輸入：素?cái)?shù)p和a；

輸出：a-1mod p，過(guò)程如下：

2.2費(fèi)馬小定理模冪法

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

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

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

表3　模逆運(yùn)算實(shí)現(xiàn)性能對(duì)比表

而一次 256 bit SM2運(yùn)算在 117 MHz下也不過(guò)用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)，來(lái)尋找一種更為高速且節(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

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

其核心思想是將乘積與模數(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ì)

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

對(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

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

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

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

從算法分析，參與運(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ǔ)器的讀寫(xiě)時(shí)間，則思路是在不過(guò)多增加存儲(chǔ)單元的基礎(chǔ)上，盡可能使用寄存器。

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

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

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

表4　模逆運(yùn)算步驟分析

表5　模逆運(yùn)算實(shí)現(xiàn)性能對(duì)比表

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

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

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

對(duì)需要3次模逆的256 bitSM2運(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 μs@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à)值。

[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-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-），女，碩士，中級(jí)工程師，主要研究方向：集成電路設(shè)計(jì)、公鑰算法的技術(shù)研究與設(shè)計(jì)實(shí)現(xiàn)。

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