國密SM9 算法R-ate 對計算的優化設計*

王明東，何衛國，李 軍，梅 瑞

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引言

基于標識的密碼系統（Identity-Based Cryptograph，IBC）是在傳統的PKI 基礎上發展而來的，將用戶的唯一標識（如手機號、郵箱地址）用作公鑰，從而幫助用戶不再頻繁申請和交換證書，極大地降低了證書和密鑰管理的復雜性。國密SM9 標識密碼算法[1]于2016 年發布為國家密碼行業標準（GM/T 0044-2016）。在標識密碼系統中，用戶的私鑰由密鑰生成中心（Key Generation Center，KGC）根據主密鑰和用戶標識計算得出，用戶的身份標識用以生成用戶的公、私密鑰對，不需要通過第三方保證其公鑰的真實性，主要用于數字簽名、數據加密、密鑰交換以及身份認證等[2]。相比于傳統密碼體系，SM9 密碼系統的最大優勢是無證書、易使用、易管理，在5G 時代物聯網等領域的數據安全應用擁有得天獨厚的優勢。但是，基于雙線性對運算的SM9標識密碼算法，相較于SM2、RSA 等公鑰算法，算法復雜度較高且占用了較多硬件資源，制約著SM9算法在輕量級設備以及密碼卡、服務器端等的高速實現。因此，SM9 算法的高性能研究與設計是目前SM9 算法實際應用面臨的較大挑戰。

1 SM9 算法參數及R-ate 雙線性對

SM9 算法推薦參數采用BN 曲線，曲線方程為E:y2=x3+b，其中b=5，嵌入次數k=12?；蛱卣鱭，曲線階r，通過參數t來確定：

Fq12域上元素采用1-2-4-12 的塔式擴張，擴張方式如下所示：

雙線性對運算推薦采用BN曲線下的R-ate對，算法描述如下。

2 算法優化性設計

R-ate 雙線性對為SM9 簽名、加解密等算法的核心運算，整體采用Miller 算法結構，πq、πq2為Frobenius 自同態，gT,Q、gT,T為直線函數運算。算法1 中計算f=f(q12-1)/r是雙線性對性能的瓶頸。若12次塔式擴張域模冪運算對指數直接采用傳統二進制掃描方法進行運算，指數(q12-1)/r的比特長度為256×11=2 816，計算復雜度大，效率偏低，采用Fq12域上的直接模冪運算方式不可取。經研究分析，可采用如下指數分解以及模冪與模逆優化等加速設計手段，有效提高算法效率。

2.1 指數分解

2.2 模逆運算優化

對于式（6）中的第一部分m=f(q6-1)，因為f∈Fq12，根據共軛運算和有限域元素的唯一性性質，有其中為f的共軛運算。

因此，第1 部分可簡化為：

所以，f經過(q6-1)次模冪運算后，求逆運算可直接優化為簡單的共軛運算，無需采用費馬定理或歐幾里得算法進行復雜的求逆運算，即式（6）中的hard part 中的模逆運算等價于共軛運算。

2.3 q 次模冪運算

SM9 算法推薦參數的Fq2、Fq4、Fq12塔式擴張域上的q次冪運算有如下快捷計算方式[3-4]。

算法2：Fq2域上q次冪運算

其中，fr為Frobenius 常數，fr=u(q-1)/6，可預計算存儲。

算法4：Fq12域上q次冪運算

其 中，fr為Frobenius 常 數，fr=u(q-1)/6，fr、fr2可預計算存儲。

因此，第二部分s=m(q2+1)=(mq)q·m采用Fq12域上q次冪優化性計算，可直接轉化為簡單的共軛運和模乘運算。

2.4 hard part

模冪的hard part 為第3 部分，f=s(q4-q2+1)/r。經研究分析，可采用如下優化運算：

3 性能評估及驗證

3.1 性能評估

對R-ate 雙線性對以及f=f(q12-1)/r涉及的模乘運算以及模加運算進行評估，統計結果如表1 所示，M、A 分別代表Fq域上的模乘與模加運算，塔式擴張域的模乘運算采用Karatsuba[5-6]算法。

從表1 的統計結果看到，本文的優化方案f(q12-1)/r的運算量為6 063 次模乘以及30 513 次模加運算，性能較傳統方法提升近37 倍，R-ate 雙線性對運算優化為111 321 次模乘以及474 787 次模加，性能整體較傳統方法提升近3 倍。

表1 R-ate 雙線性對運算性能評估表

3.2 仿真驗證

如圖1 所示，采用verilog 硬件描述語言對論文的優化算法正確性進行仿真驗證。仿真環境實現了完整的1-2-4-12 塔式擴張域上的模加、模減、模乘、模逆、標量乘、直線函數以及R-ate 雙線性對等運算，其中res12 為R-ate 雙線性對仿真運算結果，與國密標準的參考樣本數據一致，從而驗證了本論文優化算法的正確性。

圖1 R-ate 雙線性對仿真驗證結果

4 結語

本文對R-ate 對中的f(q12-1)/r模冪運算進行優化設計，對模冪指數采用指數分解、模逆運算轉換為簡單的共軛運算、q 次模冪快速算法設計以及hard part 的快速模冪運算，完成了R-ate 的快速實現。相較于傳統實現方式，顯著提升了算法性能，為R-ate 雙線性對的軟硬件高性能設計提供了算法支撐，同時用verilog 硬件描述語言仿真驗證了本論文優化算法的正確性，證明其是一種可行的優化算法。