SM9 中高次冪運算的快速實現方法

王江濤，樊 榮，黃 哲

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

0 概述

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

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

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

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

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

1 基礎算法

1.1 BN 曲線上的R-ate 對

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

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

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

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

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

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

圖1 R-ate 算法的實現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 編碼性質：

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

2）非零元素平均個數為m 3；

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

在反復平方-乘法運算中，可以使用性質2）減少乘法數量。

1.3 Comb 固定基

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

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

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

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

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

1.4 SM9 簽名算法

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

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

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

2）產生隨機數r?[1,N-1]；

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

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

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

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

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

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

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

2.1 擴域平方算法

SM9 中選取的是式（5）的1-2-4-12 塔式擴張［29］，對應的不可約多項式分別為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元素，應用塔式擴張的乘法運算規則將平方項α2表示為式（6）：

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

算法5上的平方運算

2.2 快速平方算法

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

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

其中：fr表示Frobenius 常數，值為；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 個基域加減法。底層運算的效率主要受制于基于蒙哥馬利算法的大數模乘運算，使用快速平方算法可以減少接近50%的模乘運算。本文使屬于分圓子群的十二次擴域元素采用快速平方算法，該算法使用的底層大數運算也是基于蒙哥馬利的模乘和大數加減運算，并不會造成額外的資源開銷。

2.3 基域乘法數量分析

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

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

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

3 ASIP 結構設計

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

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

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

表2 指令格式 Table 2 Instruction format

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

本文設計的ASIP 整體結構框如圖3 所示。

圖3 ASIP 的整體結構Fig.3 Overall structure of ASIP

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

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

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

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

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

5）控制和狀態寄存器Csr 用于促進Core 和ALU之間的數據傳遞。

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

4 實驗結果與分析

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

4.1 硬件資源分析

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

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

4.2 時鐘周期分析

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

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

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

5 結束語

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