SM9 中高次冪運算的快速實現(xiàn)方法

王江濤，樊 榮，黃 哲

（中國船舶集團有限公司第七二二研究所，武漢 430205）

0 概述

近年來，基于橢圓曲線上配對的密碼體制引起了人們的極大興趣，由于雙線性對獨特的性質(zhì)，可以構(gòu)造許多其他加密算法無法完成的加密協(xié)議，因此出現(xiàn)了大量基于雙線性對的研究成果，其中有許多新的的協(xié)議，包括一輪三方密鑰交換［1］、基于身份的加密［2］、基于身份的簽名［3］、短簽名方案［4］等。

我國國家密碼管理局于2016 年正式發(fā)布基配對的SM9 標識密碼算法［5］，于2018 年被納入國際標準，該算法以用戶的身份信息作為公鑰，簡化了可信第三方認證中心（Certificate Authority，CA）的秘鑰管理環(huán)節(jié)，從而解決了由高頻認證引發(fā)的信息堵塞問題，非常適合海量用戶之間的安全通信，在云計算、物聯(lián)網(wǎng)等海量用戶的新興領(lǐng)域中［6］，SM9 密碼算法具有明顯的優(yōu)勢。

基于配對的密碼協(xié)議只有在高安全級別上以高效計算雙線性配對的情況下才能實現(xiàn)。得益于MILLER 等［7］提出的在橢圓曲線上以除子的標量乘來計算有理函數(shù)的迭代算法，實現(xiàn)以線性復(fù)雜度的開銷去計算雙線性對，并用于計算weil 對（對稱雙線性對）的目的。文獻［8］給出計算更簡便的Tate 對（非對稱雙線性對）。文獻［9-11］在Tate 對的基礎(chǔ)上通過構(gòu)造特殊結(jié)構(gòu)的雙線性Eta 對、Ate 對和Atei 對來優(yōu)化雙線性對的計算量。文獻［12］定義了R-ate對，通過兩個特定線性對的比值，減少Miller 算法中的循環(huán)次數(shù)。文獻［13-15］優(yōu)化了BN 曲線上R-ate對的計算，主要針對其中的Miller 循環(huán)和最終冪運算，對Miller 循環(huán)中的同構(gòu)映射進行分析，將循環(huán)中的點加，倍點和線性函數(shù)的運算從十二次擴域降低為二次擴域.文獻［16-17］將最終冪運算進行冪次分解，用基域的組合多項式來表示運算困難的大冪次項，并利用有限域和擴域上Frobenius 映射進行加速，文獻［18］使用Comb 固定基［19］對SM9 中簽名部分的高次冪進行優(yōu)化。

密碼算法的底層運算有大量大數(shù)計算，文獻［20］提出蒙哥馬利算法，將大數(shù)的模乘改為3 個大數(shù)乘法，這也使得對稱加密的底層運算可以實現(xiàn)，文獻［21］針對R-ate 對提出混合模乘（Hybrid Modular Multiplication，HMM），其核心思想是將基域的數(shù)表示為特征數(shù)的多項式形式，引入了多項式情況下的蒙哥馬利算法，將對于大數(shù)的模乘轉(zhuǎn)化到特征數(shù)上的模乘，但由于SM9 中特征數(shù)的權(quán)重比文獻中使用的權(quán)重大，所以使用該算法并不合適作為SM9 的底層運算。文獻［22］提出基于字的蒙哥馬利乘（MWR2MM），將乘數(shù)均轉(zhuǎn)化為短整數(shù)乘法，更有利于硬件實現(xiàn)。文獻［23］提出迭代字蒙哥馬利乘（IDDMM），將模也轉(zhuǎn)化為短整數(shù)，在基于MWR2MM基礎(chǔ)上增加了基礎(chǔ)乘法的位寬。文獻［24］提出基于蒙哥馬利的求逆運算，使蒙哥馬利域的大數(shù)在求逆后，不用再進行兩次轉(zhuǎn)入域操作。

本文利用十二次擴域的分圓子群的性質(zhì)，使用快速平方算法，該算法相較于傳統(tǒng)平方算法需要的基域乘法數(shù)量降低了1/2。該平方算法應(yīng)用在SM9的高次冪運算上，包括R-ate 最終冪和簽名算法中，最終冪中的高次冪采用反復(fù)平方-乘法算法和NAF算法，簽名算法中高次冪采用Comb 固定基算法。底層的大數(shù)模乘采用文獻［20］中的蒙哥馬利運算，相較于IDDMM，更有利于本文架構(gòu)實現(xiàn)，硬件使用Xilinx Artix-7 系列的XC7A50T，架構(gòu)選用基于專用指令集處理器（Application Specific Instru-ction Set Processor，ASIP）的微碼編程，在控制硬件資源開銷的同時降低時鐘周期，從而提高性能。

1 基礎(chǔ)算法

1.1 BN 曲線上的R-ate 對

文獻［25］提出一種在素域Fp上構(gòu)造配對友好的常曲線的方式，BN 曲線定義了橢圓曲線［26-28］方程χ(Fq)：y2=x3+b，對應(yīng)嵌入度k為12，素域的特征p、群的階r、Frobenius 跡tr由參數(shù)t定義為式（1）所示：

其中：t?Z 是一個任意的整數(shù)，使得p及r均為素數(shù)。

SM9 使用了定義在BN 曲線上的R-ate 對，雙線性對中定義了3 個階為N的循環(huán)群，分別是加群G1、G2和乘群GT，G1的生成原是P1，G2的生成原是P2，G1表示χ(Fp)[r]∩Ker(πp-[1])，G2表示χ(Fp)[r]∩ Ker(πp-[p])，χ(Fq)[r]為橢圓曲線上的r扭轉(zhuǎn)點，核Ker(πp-[p])為{P|πp(P)-[p]P=O}，O 定義為橢圓曲線中的無窮遠點，在群G1、G2、GT中存在映射G2×G1→GT滿足雙線性、可計算性和非退化性，對應(yīng)映射關(guān)系如式（2）所示：

其中：Q?G2,P?G1；fr,Q為Miller函數(shù)；πp表示Frobenius 映射πp(x,y)=(xp,yp)；lR,Q(P)為橢圓曲線上過R,Q的直線方程在P點處的值。R-ate 雙線性對的計算可由算法1 實現(xiàn)。

算法1BN 曲線上的R-ate 對

算法1 中的計算可以分解為圖1 中基域的加減乘和求逆運算，其中較為復(fù)雜的運算為第2 步Miller循環(huán)和第6 步的最終冪運算，最終可以轉(zhuǎn)化為基域的加減乘和求逆運算。

圖1 R-ate 算法的實現(xiàn)Fig.1 Implementation of R-ate algorithm

1.2 NAF 算法

采用NAF 算法對標量k進行編碼，是指將使用1，0 表示二進制序列k=(sm-1,…，si,…，s1,s0)bin，其中si?{0,1}，變換為用1、0 和-1 表示的形式。即標量k的NAF 編碼為k=(km,…，ki,…，k1,k0)NAF，其中ki?{-1,0,1}，且首位km≠0，具體表示如式（3）所示：

標量k的NAF 編碼算法描述如算法2 所示。

算法2標量k的NAF 編碼算法

令lNAF(k)表示標量k采用NAF 編碼方法的編碼長度，則有，下面給出實用的NAF 編碼性質(zhì)：

1）長度最多比二進制形式編碼的長度多1；

2）非零元素平均個數(shù)為m 3；

3）非零元素-1，1 不會相鄰。

在反復(fù)平方-乘法運算中，可以使用性質(zhì)2）減少乘法數(shù)量。

1.3 Comb 固定基

SM9 簽名運算中高次冪可以預(yù)存點，通過查找表運算高次冪gr，將冪指數(shù)通過基于Comb 固定基的方式進行查表計算。指數(shù)r可以表示成式（4）中兩種形式，其中

當指數(shù)運算時，所有Ri位置相同的比特可以同時處理，將需要預(yù)先存儲的元素表示為，其中m按位展開為[m7,m6,m5,m4,m3,m2,m1,m0]?[0,255]，所以共需要預(yù)存256 個十二次擴域元素，算法實現(xiàn)先按照圖2 對r進行比特重組，將以Ri表示變?yōu)橐詀i表示，再使用算法3 進行計算。

圖2 冪指數(shù)r 的比特重組Fig.2 Bit recombination of power exponent r

算法3基于Comb 基的高次冪運算

使用Comb 算法優(yōu)化前，如果預(yù)存每個比特位上的平方值，也需要預(yù)存256 個十二次擴域元素，運算開銷為128 次GT域上的乘法。優(yōu)化后，在使用相同存儲開銷的情況下，運算開銷減少為GT域上31 次乘法運算和31 次平方運算。

1.4 SM9 簽名算法

密鑰生成中心（Key Generate Center，KGC）產(chǎn)生隨機數(shù)ks?[1,N-1]，計 算G2元素Ppub-s=[ks]P2并作為簽名主公鑰，計算G1元素dSA=[t2]P1作為簽名密鑰，t2通過哈希計算用戶標識ID 得到。

令待簽名的信息為M，KGC 生成(Ppub-s,dSA)密鑰對，簽名后得到數(shù)字簽名為(h,s)，簽名流程為：

1）計算GT中的元素g=e(P1，Ppub-s)；

2）產(chǎn)生隨機數(shù)r?[1,N-1]；

3）計算群GT中的元素w=gr；

4）計算整數(shù)h=H2(M||w,N)；

5）計算整數(shù)l=(r-h)modN；

6）計算群G1中的元素S=[l]dsA；

7）消息的簽名值為(h,S)。

在簽名算法中，當KGC 下發(fā)了Ppub-s后，由于P1也是固定變量，因此簽名中g(shù)可以提前預(yù)計算并存儲起來，不用每次簽名都要重新計算，所以簽名的效率往往是驗簽效率的數(shù)倍。

2 基于分圓子群的快速平方算法

2.1 擴域平方算法

SM9 中選取的是式（5）的1-2-4-12 塔式擴張［29］，對應(yīng)的不可約多項式分別為x2-α(α=-2)，x2-u(u=，其計算式如下：

在擴域Fq4中將a表示為a1+a0v，其中a1、a0均表示二次擴域元素。使用算法4 計算4 次擴域元素的平方，相較于直接用Karatsuba 算法計算，平方算法需要將基域的乘法從9 次降低為6 次。

算法4上的平方運算

在擴域Fq12中α表示為a+bw+cw2，其中a、b、c為擴域Fq4元素，應(yīng)用塔式擴張的乘法運算規(guī)則將平方項α2表示為式（6）：

u、v、w分別為二次、四次和十二次擴域元素，關(guān)系為-2=u2=v4=w12，采用算法5 使運算開銷從3 個四次擴域的平方和乘法降低為3 個平方和2 個乘法，即需要36 個基域乘法。

算法5上的平方運算

2.2 快速平方算法

算法1 中R-ate 對的計算包括Miller 循環(huán)和最終冪運算，由式（7）中分圓多項式的定義可知，在最終冪中部分表示為其中：Φ4(p)=p2+1；Φ12(p)=p4-p2+1。由費馬小定理可知，F(xiàn)p12的元素f對應(yīng)有fp12-1=1，根據(jù)式（8）給出的分 圓子群 的定義，令α=f(p6-1) (p2+1)，可 得到α?GΦ12(p)。

根據(jù)Frobenius 映射原則，將α在GΦ12(p)群中滿足的性質(zhì)αp4+1=αp2展開，可得到式（9）：

其中：fr表示Frobenius 常數(shù)，值為；aˉ表示擴域元素a的共軛。將式（9）展開并約減w3-v和Φ12(fr)=，得到式（10）：

式（10）中提供了式（6）中乘項ab、bc、ac另一種等效求解方式，如式（11）所示：

算法6 為GΦ12(p)上的平方運算。

算法6GΦ12(p)上的平方運算

將十二次擴域群上的平方算法5 和十二次分圓子群的平方算法6 進行對比，由于共軛運算不會增加額外的加減法，因此前者需要36 個基域乘法和40 個基域加減法，后者需要18 個基域乘法和36 個基域加減法。底層運算的效率主要受制于基于蒙哥馬利算法的大數(shù)模乘運算，使用快速平方算法可以減少接近50%的模乘運算。本文使屬于分圓子群的十二次擴域元素采用快速平方算法，該算法使用的底層大數(shù)運算也是基于蒙哥馬利的模乘和大數(shù)加減運算，并不會造成額外的資源開銷。

2.3 基域乘法數(shù)量分析

在R-ate 對中高次冪ft的運算中，冪指數(shù)t為SM9 中的參數(shù)t，對應(yīng)值為0x600000000058F98A，漢明重量為13，數(shù)據(jù)位寬為63。由于底數(shù)f是變化的，因此采用反復(fù)平方-乘法算法，共需要12 個十二次擴域乘法和63 個平方運算，對指數(shù)t使用NAF 后可以將其漢明重量降低為11，數(shù)據(jù)位寬變?yōu)?4（NAF 會增加1 位數(shù)據(jù)位寬），在十二次分圓子群中f(-1)可以轉(zhuǎn)化為共軛fˉ計算，因此優(yōu)化后，僅需要10 個擴域乘法及64 個在第2 節(jié)引入的在分圓子群上的快速平方。

在簽名中高次冪gr運算中，冪指數(shù)r為256 bit位寬的隨機數(shù)，由于底數(shù)g是固定的，因此可以預(yù)存一些計算值，采用基于Comb 固定基計算，預(yù)存256 個十二次擴域的點，根據(jù)查找表計算結(jié)果需要31 個擴域平方和31 個擴域乘法。相比采用反復(fù)平方-乘法算法，對應(yīng)計算結(jié)果需要256 個擴域平方和128 個擴域乘法，即采用NAF（經(jīng)過R-ate 對計算后，仍保留分圓子群的性質(zhì)，即模逆計算可以轉(zhuǎn)化為共軛計算）降低也需要約80 個擴域乘法，如果無法使用查找表的場合，可用后者進行優(yōu)化。表1 所示為采用快速平方算法前后的乘法數(shù)量對比。

表1 高次冪基域乘法數(shù)量對比 Table 1 Comparison of multiplication of higher power base fields

3 ASIP 結(jié)構(gòu)設(shè)計

由于SM9 邏輯較為復(fù)雜，將其拆分成基域的運算需要復(fù)雜的控制信號，因此硬件架構(gòu)采用ASIP，其核心思想是針對某一特定目標的應(yīng)用領(lǐng)域定制一套專用指令集，然后開發(fā)出與該指令集相對的體系結(jié)構(gòu)，最終根據(jù)該體系結(jié)構(gòu)高效地構(gòu)造復(fù)雜算法的專用微處理器結(jié)構(gòu)，它具備通用處理器（General Purpose Processor，GPP）的可編程性和專用集成電路（Application Specific Integrated Circuit，ASIC）的 高速處理特性。

從硬件角度來看，F(xiàn)PGA 具有片內(nèi)資源豐富、可重新配置、可實現(xiàn)大規(guī)模電路等特點，而且基于重用電路性質(zhì)可以縮小設(shè)計周期和提高資源利用率，因此FPGA 可以用作ASIP 的載體，在基礎(chǔ)電路固定的情況下，ASIP 可以通過編程的方式實現(xiàn)相應(yīng)的復(fù)雜算法，同時也具備了可擴展移植的特點。在ASIP 的設(shè)計中，選擇合適的體系架構(gòu)是關(guān)鍵性問題，目前較為主流的體系架構(gòu)為精簡指令集計算機（Reduced Instruction Set Computer，RISC）結(jié)構(gòu)和復(fù)雜指令集計算機（Complex Instruction Set Computer，CSIC）結(jié)構(gòu)，相比于CSIC，RISC 采用固定長度的編碼長度，簡化了指令系統(tǒng)，減少了指令譯碼的線路規(guī)模。

本文采用自定義的32 bit RISC 指令，指令格式如表2 所示，表中第1 行數(shù)據(jù)代表比特位，指令集的設(shè)計遵循精簡、高效、可重用的原則，如普通加減法和模加減法在選用不同模式時使用相同的電路結(jié)構(gòu)，在所有格式中，指令集架構(gòu)（Instruction Set Architecture，ISA）將源寄存器（RegS）、目的寄存器（RegD）、源控制和狀態(tài)寄存器（Control and Status Register，CSR）、CsrS 以及目的CSR（CsrD）固定在同樣位置，若使用立即數(shù)能保證編碼位置的嚴格對齊，從而降低譯碼模塊的復(fù)雜度。

表2 指令格式 Table 2 Instruction format

基礎(chǔ)通用指令主要用作控制程序指針，包括Nop指令、Call指令、Return指令、Goto指令，后 面3 條指令可實現(xiàn)較為復(fù)雜的邏輯控制，Type-I 類型指令主要用于實現(xiàn)對RegFile 寄存器的讀寫操作，包含RegCsrEachSet 指令實現(xiàn)CSR 與寄存器的雙向同時賦值或基于寄存器賦值的延伸使用方式，RegSetWith 指令以及GetPointToReg 指令實現(xiàn)寄存器間數(shù)據(jù)的賦值操作以及RegInc 指令實現(xiàn)寄存器中數(shù)據(jù)的自加一運算。Type-II 類型指令包括指令CSRSetWithImm，用于將相應(yīng)的CSR 賦值為基數(shù)的值。Type-III 主要包含指令BcRegERqImm，該指令實現(xiàn)有條件跳轉(zhuǎn)，也是構(gòu)建循環(huán)的必須指令。

本文設(shè)計的ASIP 整體結(jié)構(gòu)框如圖3 所示。

圖3 ASIP 的整體結(jié)構(gòu)Fig.3 Overall structure of ASIP

硬件層實現(xiàn)了有限域算數(shù)單元擴充的通用處理器，因此確保了平臺的靈活性和通用性，對應(yīng)模塊的功能如下：

1）算法核單元Core 通過程序定序器（Program Sequence）處理程序存儲器（Program Rom）中的二進制指令，相應(yīng)指令解析流程為指令獲取IF、指令解碼DE 以及指令執(zhí)行EXE，解析后執(zhí)行相應(yīng)的控制和數(shù)據(jù)傳遞功能，并提供下一條指令在程序存儲器中的地址。

2）算數(shù)運算單元ALU 中包括基于蒙哥馬利和Karatsuba 算法完成基域的乘法和求逆，由于大量的基域加減法和乘法在執(zhí)行時間上重合，因此加減法單元被設(shè)計在Core 中，從而可以進行并行處理以減少總時鐘周期。

3）組件單元中包括取預(yù)存值的模塊Ng、降低漢明重量的NAF 模塊以及計算高次冪的Comb 基模塊等，ALU 和組件均由控制模塊給出執(zhí)行信號，并占用相同的數(shù)據(jù)總線。

4）通用寄存器組（General Purpose Register Set，GPRS）為ALU 提供操作數(shù)、暫存運算結(jié)果以及初始化時預(yù)存常參量的功能。

5）控制和狀態(tài)寄存器Csr 用于促進Core 和ALU之間的數(shù)據(jù)傳遞。

邏輯層匯編編譯器將基于RISC 指令集編寫的匯編文件編譯成典型FPGA ROM 宏單元的程序內(nèi)容配置文件，匯編文件的編寫需考慮到乘法和其他操作的并行性，編譯器由Python 編寫，具有完整的錯誤檢查功能，利于軟件程序的自檢。

4 實驗結(jié)果與分析

為驗證快速平方算法并對其資源開銷和運算性能進行評估，本文使用SpinalHDL 語言實現(xiàn)，基于Xlinx Artix-7 FPGA（XC7A50T-1FTG256C）進行實際測試，并分析硬件實現(xiàn)性能和資源開銷。

4.1 硬件資源分析

為評估硬件資源所需的開銷，本文將實現(xiàn)SM9算法的ASIP 以167 MHz 的時鐘頻率進行綜合。本文底層通用運算模塊的硬件實現(xiàn)上重點在于充分利用ASIP 的可編程性，最占用資源的模塊為蒙哥馬利模乘Mul 和模逆Inv 模塊。模乘器的實現(xiàn)并未采用狀態(tài)機，而是采用全流水的形式，在擴域乘法上，連續(xù)乘法結(jié)果的輸出可以極大降低時鐘周期。模逆器可以選擇用微碼實現(xiàn)，從而省去接近13.6%的硬件資源開銷，本文考慮到該密碼算法核的通用性，選擇保留模逆器。算法核單元Core 為最需要減低面積的模塊，主要方向為重利用寄存器，最終為放置多組算法核提供了可行性，本文算法的各個模塊硬件綜合資源開銷數(shù)據(jù)如表3 所示。分別使用查找 表（Look-Up-Table）、塊隨機 存儲器（Block Random Access Memory，BRAM）、數(shù)字信號處理器（Digital Signal Process，DSP）作為硬件綜合資源開銷的單位。由表3 可知，本文算法總體資源占用相比于文獻［18］算法，需要的硬件資源LUTS 有所減少。

表3 本文算法各模塊硬件資源開銷 Table 3 Hardware resource cost of each module of algorithm in this paper

4.2 時鐘周期分析

表4 給出了各基本運算的時鐘周期數(shù)，本文為了降低時鐘周期，令底層蒙哥馬利模乘采用全流水的形式，即兩個連續(xù)的乘法運算可以無延時地輸入乘法器，從而可以更好地利用ASIP 的可編程性。大數(shù)的模加減運算在算法核Core 中，由于ASIP 的數(shù)據(jù)交互在Core 和Csr 之間進行，需要將加數(shù)分別從Csr送入Core 再取出結(jié)果，至少需要3 個及以上時鐘周期。本文采用流水加法，可以連續(xù)送入加數(shù)，在取模的同時送入下一組加數(shù)，從而減少到兩個周期。匯編的靈活性使得流水加減法和44 級乘法流水可以交替進行，經(jīng)優(yōu)化運算周期數(shù)表3 為最終優(yōu)化結(jié)果，其中f×g，f2分別為對應(yīng)擴域的乘法，相比于基本十二次擴域元素的平方，分圓子群上的平方運算時鐘周期數(shù)降低了約47.14%。ft，gr為R-ate 對和簽名算法中的高次冪運算，kP為簽名中的點乘運算。

表4 不同基本運算的時鐘周期數(shù)對比 Table 4 Comparison of clock cycles of different basic operations 單位：個

SM9 簽名運算中包含高次冪和G1點乘兩個相對復(fù)雜的運算，表5 所示為不同平臺簽名時間的對比，文獻［30］算法基于Arria10 軟件平臺實現(xiàn)，但并未使用Comb 固定基，性能相對較差，文獻［18］算法基于XC7K325T 硬件平臺，為了節(jié)省高次冪所占用的存儲空間，只預(yù)存4 個擴域值，并令擴域平方和乘法使用相同的結(jié)構(gòu)，簽名時間較長。文獻［31］算法基于i5-4590 CPU，預(yù)存的數(shù)值與本文一致，但未使用快速平方算法和ASIP 硬件架構(gòu)，因此性能較本文也差一些。綜上分析，采用ASIP 的硬件架構(gòu)，在簽名算法中使用快速平方算法對性能有較大提升。

5 結(jié)束語

本文根據(jù)R-ate 對映射出來的擴域元素屬于十二次分圓子群的性質(zhì)，推導(dǎo)出基于該子群的快速平方算法，并將該平方算法應(yīng)用在SM9 簽名和驗簽中，簽名中高次冪減少了20%的基域乘法數(shù)量，驗簽中高次冪減少了42.1%的乘法數(shù)量。本文針對SM9的特性完成了基于ASIP 的硬件設(shè)計，并在Xilinx Artix-7 FPGA 平臺上進行了實際測試。實驗結(jié)果表明，在167 MHz 的時鐘頻率條件下，不增加額外的硬件資源開銷，完成一次SM9 簽名的時間僅為0.244 ms。下一步將嘗試利用IDDMM 算法，優(yōu)化底層大數(shù)算法，在相同性能的情況下減少硬件資源開銷。