一種基于圖形處理器的高吞吐量SM2數字簽名計算方案

朱 輝 黃煜坤 王楓為 楊曉鵬 李 暉

(西安電子科技大學網絡與信息安全學院 西安 710126)

1 引言

數字簽名技術是實現網絡安全的重要機制之一，它常用于通信雙方的身份認證和保證數據的不可抵賴性。隨著云計算、電子商務等技術的發展和認證信息細?；潭鹊奶岣?，數字簽名技術的使用也越來越頻繁。SM2數字簽名方案是基于橢圓曲線密碼學(Elliptic Curve Cryptography, ECC)的非對稱密碼方案，由國家密碼管理局(State Cryptography Administration of China, SCA)于2010年出臺[1]，并在2018年成為國際標準[2]。相較于其他公鑰密碼方案，橢圓曲線密碼方案最大的優勢是能在使用較短長度密鑰的同時提供較高的安全性。隨著人們安全需求的不斷提高，SM2這種基于ECC的密碼方案將會有著優秀且廣泛的應用前景。

然而，由于SM2數字簽名算法中存在復雜且計算量大的橢圓曲線運算，頻繁海量地簽名和驗簽操作會給服務器帶來極大的計算處理壓力[3]，造成服務質量下降甚至系統崩潰等問題。因此，研究高效的SM2簽名與驗簽計算方法不僅能降低服務商計算成本，而且能夠提升用戶體驗，近年來SM2算法的各類應用研究得到了研究人員的廣泛關注，但在對其的優化實現方面的研究工作公開資料較少。圍繞上述問題，針對服務商同時處理大量用戶簽名、驗簽請求的場景，本文設計并實現了一種圖形處理器(Graphics Processing Unit, GPU)平臺下的高吞吐量SM2數字簽名計算方案。

當前，降低簽名、驗簽計算成本通常從兩個層次出發：(1)選擇計算能力強同時價格相對低廉的計算平臺以降低硬件成本。(2)結合平臺特性優化密碼算法降低計算開銷。

在計算平臺選擇和優化實現方面。Koppermann等人[4]在現場可編程邏輯門陣列(Field Programmable Gate Array, FPGA)平臺上以92 μs的時延實現了基于ECC的X25519協議。Huang等人[5]使用高級矢量擴展(Advanced Vector eXtensions 2,AVX2)指令集并行化橢圓曲線點加運算，分別以24 μ s 和98 μs的時延實現了SM2簽名、驗簽算法。上述文獻的研究都側重于降低算法的時延，由于計算平臺本身的特點，他們的實現在吞吐量方面的表現并不突出。隨著人工智能領域的發展，通用GPU的計算性能在近幾年得到了飛速增長，而且在并行計算領域，GPU更是有著巨大的優勢[6]。Pan 等人[7]使用型號為GTX780Ti的GPU加速橢圓曲線運算，實現了簽名吞吐量達到8.71×106次/s的數字簽名服務器，同時展現了GPU并行計算密碼算法的巨大潛力。而且相比于專用的密碼機，成熟且可靠的生產鏈使得GPU在算力上擁有更高的性價比。因此在高并發場景下，GPU相比其他密碼計算設備有著更大的優勢。

在結合平臺特性進行密碼算法優化方面，基于ECC的簽名與驗簽計算主要涉及模乘、模加、模減、模逆、橢圓曲線多倍點運算和橢圓曲線點的加法運算(如圖1所示)，其中模逆和橢圓曲線多倍點運算分別為有限域和橢圓曲線群中開銷最大的運算，它們的計算效率將很大程度上影響簽名、驗簽的性能表現。(1)在當前對橢圓曲線多倍點運算的快速計算方法中，基于大數非相鄰形式的(Non-Adjacent Form, NAF)算法[8]可以大大減少計算量，但該算法中包含依賴輸入值的分支判斷，使其容易遭受到側信道攻擊[9,10]，并且其算法結構的復雜度較高，因而其并不適合在GPU這種分支預測能力弱的計算設備上運行。相反，一些計算量稍大但結構簡單的算法在GPU上的運行表現更好，如二進制展開法。Pan 等人[7]利用橢圓曲線基點G在系統中保持不變的特性，構建了大小為64 MB的預計算表輔助固定點乘的計算，大大減少了固定點乘的計算量，且非常適合GPU這類內存空間充裕的設備，但該方法不適合應用于未知點乘運算。(2)當前模逆運算主要采用基于擴展歐幾里得算法和費馬小定理兩種方法實現，出于計算開銷方面考量，大多數傾向采用擴展歐幾里得算法計算模逆。然而，盡管基于費馬小定理的模逆算法開銷較大，但由于其運行過程與輸入值無關，因此Huang等人[5]和Zhou等人[11]基于該算法構造出抵抗側信道攻擊的方案。Pan等人[7]指出，由于擴展歐幾里得算法會產生嚴重線程束分化現象，GPU并不是一個計算模逆的理想平臺，于是利用同時模逆(simultaneous inversion)算法在CPU上計算模逆，但這種方案需要CPU與GPU間通信交互，且大幅增加了任務調度的復雜度，在實際部署過程中難以優化出理想的效果。

圖1 SM2數字簽名算法運算層次圖

本文針對GPU平臺特性，對SM2算法中的關鍵運算進行優化改進，顯著提升了SM2簽名與驗簽算法的吞吐量，主要貢獻點如下：

(1) 構建了基于底層指令優化的模加、減、乘運算模塊。通過使用GPU底層指令構建高效的模加、減運算，優化了模乘約減算法的計算過程，并設計預計算表減少了模乘約減運算所需的模減次數。

(2) 提出了結合GPU特性的高效模逆計算方法?？紤]GPU 乘法計算能力強但分支預測能力弱的特性，利用加法鏈加速基于費馬小定理的模逆計算方法，同時縮短了SM2推薦素數的加法鏈，極大提升模逆處理速度。

(3) 提出了面向未知點乘運算的優化機制。利用倍點運算比點加運算開銷更低的特性進行預計算表構造，不僅減少了未知點乘運算預計算環節的計算量，并且消除了主循環計算環節的條件判斷，并利用重復倍點算法提高了主循環計算環節的計算效率。

(4) GPU平臺實測證明所提的SM2算法優化方案可以極大地提升簽名與驗簽算法的吞吐量。在RTX 3090 GPU卡上，其簽名和驗簽吞吐量分別達到7.609×107次/s和3.46×106次/s，顯著優于已有公開成果。

2 預備知識

2.1 SM2數字簽名算法

SM2數字簽名算法[1]分為密鑰生成、簽名和驗簽算法。密鑰生成算法用于生成用戶的公私鑰對(dA,PA) ， 其中私鑰dA為范圍在[ 1,n ?2]的大整數，用于產生對數據的簽名，公鑰PA= [dA]G是橢圓曲線上的點，用于驗證簽名。

SM2簽名算法輸入摘要e和私鑰dA，輸出簽名(r,s) ， 其中輸入的摘要e=h(m)為 簽名消息m的雜湊值，且雜湊函數h(m)需要使用SCA批準的密碼雜湊算法，如SM3密碼雜湊算法[12]。具體計算過程如下。其中G,n的定義可參見2.2節：

2.2 SM2方案推薦橢圓曲線參數及定義

SM2方案推薦的橢圓曲線由素數域FP上的Weierstrass方程所定義，如式(1)所示

其中，p是大于3的素數，a,b ∈FP，且滿足(4a3+27b2)modp ?=0。橢圓曲線上的點按照點加運算規則構成阿貝爾群。橢圓曲線上的多倍點運算定義為同一個點的多次點加，如式(2)所示

此外，SM2方案推薦使用的256位橢圓曲線參數[13]還包括偽梅森素數PSCA-256[14]、橢圓曲線的基點G、基點G的階n和 系數a,b。其中，素數PSCA-256可表示為PSCA-256=2256?2224?296+264?1。文獻[15]給出了針對此素數的快速模約算法，如表1算法所示。

表1 針對素數SCA-256的快速模約算法

2.3 Jacobi加重射影坐標系下的點加運算

在Jacobi加重射影坐標系(下文簡稱Jacobi坐標系)下進行點加運算可減少模逆帶來的計算開銷。若Z?=0 ， 令X=xZ2,Y=yZ3則可將2.2節中式(1)的仿射坐標系表示轉化為Jacobi坐標系表示，如式(3)所示

橢圓曲線點的加法運算根據兩輸入點是否相同分為點加運算和倍點運算，這兩種運算有著不同的計算方式。Jacobi坐標下橢圓曲線點的加法運算的底層算法可參見文獻[16]。

2.4 CUDA編程

Nvidia的統一計算設備架構(Compute Unified Device Architecture, CUDA)提供了并行線程執行模型(Parallel Thread eXecution, PTX)和指令集架構(Instruction Set Architecture, ISA)[17]。PTX ISA指令集(下文簡稱PTX指令集)包含帶進位的加、減和移位等運算，可以利用這些指令構建底層大數運算來減少不必要的運算開銷。本文所使用的指令及其含義如表2所示。其中指令 add , a ddc,sub 和s ubc等可指定是否使用條件代碼(Condition Code, CC)寄存器，該寄存器包含一個進位標志位CC.CF(Carry Flag bit)。在指令中指定使用條件代碼寄存器會將計算產生的進位或借位寫入CC.CF中。例如，指令 add.cc(c,a,b) 計算c=a+b并將產生的進位寫入到C C.C F 中，而指令 add(c,a,b)只計算c=a+b。 指令s hf所執行的是漏斗移位(funnel shift)操作[17]，該操作需連接兩個操作數后進行移位，并在左移的情況下取結果的最高32 bit，在右移的情況下取結果的最低32 bit。

表2 PTX ISA指令及其含義

3 有限域基礎運算的構建與優化

本節將介紹面向GPU的有限域基礎運算構建及其優化方法，包括如何使用底層指令構建高效的大整數移位、模加、減、乘運算，以及結合GPU的特性優化實現模逆運算。

3.1 大整數移位運算優化

漏斗移位指令s hf從底層整合了連接和移位操作，這使得傳播的比特位被自然地移動到下一個字中，因此，使用該指令可高效地實現大整數的移位。圖2給出了一個包含5個字的大整數a(a0,a1,...,a4) bit左移得到c(c0,c1,...,c4)的運算示例，該運算從大整數的低位字開始分別計算各個字的漏斗移位結果和最高位字的普通移位結果。同理，大整數的右移運算可以從數的高位字開始計算各個數的漏斗移位結果和最低位字的普通移位結果。

圖2 大整數左移運算示意圖

3.2 模加、減運算優化

模加、減運算可分解為加、減運算和模約運算，本文將以加法運算為例介紹如何使用PTX指令集處理進位傳播問題，并在最后歸納模約運算的實現過程。

CUDA的PTX指令集對進位處理的支持使得大整數的加減運算可被高效地實現。圖3為包含5個字的大整數加法運算示意圖。當計算大整數最低位字時，無需考慮進位的計算，因此使用不考慮進位的a dd指 令，但需要使用. cc將計算產生的進位寫入CC.CF中。在后續的 a ddc.cc加法指令中，進位將通過CC.CF寄存器傳播到下一個字中。需要注意的是，CUDA沒有提供對CC寄存器的設置、清除和測試操作[17]。因此，需要額外使用一次 addc或subc指令來得到最終的進位，同時可以利用最終的進位來完成剩下的模約操作。同理，減法運算也可以使用s ub和 s ubc指令來實現。[0,p)條件，因此，a?b運 算的取值范圍在(?p,p)之間且最多需要一次加法使結果歸約到[0,p)之間，即c=a ?b或c=a ?b+p。與模加運算不同的是，模減運算只需在a?b產生借位時進行一次加法運算即可將結果歸約至[0,p)之間。

圖3 加法運算示意圖

3.3 模乘運算優化

本文將模乘運算分解為乘法運算和模約運算，并分別討論乘法和模約運算的優化方法。

平方是一種特殊的乘法運算，考慮到其中含有重復的乘法指令(如ai×aj與aj×ai)，這使得平方運算可比通用乘法運算更快地執行[19]，因此我們將乘法運算分為通用乘法和平方運算，并對平方運算做特殊優化處理。如圖4所示，對大整數a=(a4,...,a1,a0) 進行的平方運算可拆分為25次子乘法ai×aj,i,j=0,1,...,4，圖4中黃色方格代表平方運算中重復的子乘法，其結果與灰色方格所代表的子乘法結果相同。因此，平方運算可通過先計算所有灰色方格中子乘法的值，再將結果擴大兩倍(即結果左移1 bit)，最后加上所有藍色方格中子乘法的值來實現。

圖4 平方運算示意圖

由于SM2算法中絕大部分的模乘運算都是在素數域中進行的，而該素數域下存在極其高效的模約算法，本文將使用該算法來優化模乘運算。2.2節中表1算法為針對模數PSCA-256的高層模約算法，其需要14個臨時值計算得到范圍在[ 0,14PSCA-256)的結果Z，最后再將Z約減至范圍[ 0,PSCA-256)內。本文通過使用PTX指令集對高層算法進行優化，以省略高層算法需要的賦值操作并減少該算法使用的臨時變量，接著提出進一步約減算法，通過最多兩次模加減操作即可將結果約減至[ 0,PSCA-256)內，具體說明如下。

令Z=(Z8,...,Z1,Z0)為288 bit大數，包含9個字，用于存儲范圍在[ 0,14PSCA-256)的結果，則表1算法中步驟s1+s2的底層指令可表示為式(4)–式(9)

同理，可使用PTX指令集完成剩下的加減操作得到結果Z ∈[0,14PSCA-256)，而對結果Z的進一步約減可通過重復減去PSCA-256來實現。值得注意的是PSCA-256的大小非常接近2256， 因此根據Z8的值推斷重復減去PSCA-256的次數。并且根據式(10)構 建 表T[14]={0,t,2t,...,13t}，其 中，t=2256?PSCA-256，可將n次 減去PSCA-256的重復減法轉化為一次加nt的加法，而式(10)中減去2256n的操作可通過忽略最高位字實現。

因此，對結果Z的進一步約減算法如表3所示。其中， ADD(X,Y,Z) 和S UB(X,Y,Z)分別為大整數加減函數，其功能分別為計算大整數之間的加法X=Y+Z和減法X=Y ?Z，并返回最終的進位或借位。表3算法的核心思想是根據PSCA-256的大小非常接近 2256的性質，將式(10)中的n近似地看作Z8來 確定n的 值，但由于PSCA-256與 2256之間存在誤差，所以若加法計算產生了進位則需要再減去PSCA-256。

表3 進一步約減算法

3.4 模逆運算優化

模逆運算是橢圓曲線素數域中開銷最大的運算，同時也是制約SM2算法運行效率的瓶頸之一。考慮到GPU擁有強大的乘法計算能力但分支預測能力較弱，且線程束分化現象會嚴重降低GPU處理效率，因此本文選擇基于費馬小定理來對GPU環境下的模逆運算進行實現和優化。

為了減少模逆運算帶來的計算開銷，本文選擇在Jacobi坐標系下計算橢圓曲線點加。通過分析SM2算法可以發現，簽名過程中需要進行兩次模逆運算，分別是Jacobi-仿射坐標轉換過程所需的模逆運算和簽名算法步驟4所要求的模逆運算，同時驗簽過程只需進行一次坐標轉換的求逆。而簽名算法步驟4中的dA是簽名方已知的私鑰，這意味著(1+dA)模n的逆可以被提前計算好從而省去本次模逆運算。因此整個簽名、驗簽算法都只需要進行一次坐標轉換的模逆計算，即素數域下的模逆。在使用費馬小定理計算模逆時，運算冪次為p?2，如式(11)所示

素數PSCA-256在整個SM2簽名系統中固定不變，因此，我們可以提前計算好素數PSCA-256的加法鏈，并利用加法鏈來減少模冪運算過程中的模乘次數。 Zhou 等人[11]采用此方法，通過255次模平方運算(S)和15次模乘運算(M)完成了模逆的計算。本文進一步縮短素數PSCA-256的加法鏈，使模逆的計算開銷降至255S+14M，模逆的具體計算過程如表4所示。

表4 針對素數P SCA-256的快速模逆算法

4 橢圓曲線多倍點運算的優化

本文將窗口法拆分為預計算環節和主循環環節，如表5所示，分別優化兩個環節的計算過程。在預計算環節，需計算Pi=[i]P,i ∈{0,1,...,2w ?1}，我們利用倍點運算比點加運算開銷更小的特性，在預計算時多使用倍點運算來減少計算開銷，即通過先計算所有奇數倍的點，之后使用倍點運算求出剩下的點。值得注意的是，預計算表的P0設置為無窮遠點，這雖然會占用一定的存儲空間，但可在主循環中省去對kj是否等于0的條件判斷，從而減少線程束分化現象對計算效率的影響。在主循環環節，使用文獻[20]中的重復倍點(repeated doubling)算法計算[ 2w]Q，該算法比多次使用倍點運算更加高效。此外，預計算表的大小也需適當選取，若預計算表過小，則加速效果不明顯，若預計算表過大，則建表時間長且占用的緩存空間大，會降低整體的吞吐量。經過實驗測試驗證，表內存儲16個點最為合適，即w=4。

表5 優化的窗口未知點乘法

5 實驗分析

目前，學術界通常以吞吐量和時延作為主要評價指標來衡量GPU上算法的性能表現[21,22]，其中，吞吐量代表計算設備每秒能夠進行計算操作的次數，時延用于衡量計算請求處理時間的長短。本文以吞吐量為評價指標分別測試所提的未知點乘算法和模逆算法的性能表現，并與其他方案作對比；最后測試簽名、驗簽算法的吞吐量和時延，以評估本文所提SM2數字簽名計算優化方案的整體性能。GPU測試平臺為RTX 3090，軟件開發環境為CUDA 11.1，操作系統為Ubuntu 18.04。

在GPU中，線程以線程塊的形式被組織，線程塊大小表示其中包含線程的數量。GPU上運行線程的總數為線程塊大小與線程塊數量的乘積。當GPU上運行線程數較少時，GPU處于低負載狀態下運行。同理，當GPU上運行線程數足夠多時，GPU處于高負載狀態下運行，此時GPU的計算能力可得到充分發揮。由于GPU的計算資源是固定的，當GPU處于高負載狀態下時，線程塊大小決定了每個線程所能分配到的計算資源，從而影響算法的運行效果。因此，合理配置線程塊大小是達到算法最優運行效果不可或缺的一步。為探究線程塊大小的最優配置，設置線程塊大小size為64,128, 256, 512，分別測試不同算法在GPU高負載運行時的吞吐量結果。實驗結果如表6所示，本文所提快速模逆算法、基于擴展歐幾里得的模逆算法、快速未知點乘算法、SM2簽名和驗簽算法分別在線程塊大小為64, 512, 512, 128和128時達到最高吞吐量。

表6 GPU高負載運行時不同算法的吞吐量結果

根據上述實驗結果，分別設置線程塊大小為64與512，測試本文基于費馬小定理優化實現的模逆運算與基于擴展歐幾里得的模逆運算的性能表現。經過測試發現，本文基于費馬小定理優化實現的模逆運算吞吐量可達到1.33×108次/s，而基于擴展歐幾里得算法的模逆運算吞吐量最高只有3.21×106次/s。而且無論GPU負載如何，本文所提快速模逆算法吞吐量遠大于基于擴展歐幾里得的模逆算法，測試結果如圖5所示。這說明盡管擴展歐幾里得算法的計算開銷更小，但其復雜的邏輯結構導致其極不適合在GPU這種分支預測能力弱的設備上運行。而計算開銷更大的基于費馬小定理的模逆算法，由于其算法結構簡單且只含有GPU擅長的模乘計算，導致該算法在GPU上的性能表現極其優秀。更重要的是，由于本文對底層模乘算法進行了優化，并且通過加法鏈優化了模冪的計算過程，也使得模逆運算效率大大提升。

圖5 模逆運算吞吐量測試結果

在未知點乘運算性能測試方面，為了評估本文所提算法的實際性能表現，本文選取Pan等人[7]提出的未知點乘優化算法，并在相同計算環境下與其做性能對比測試。設置線程塊大小為512，分別測試本文與Pan等人[7]提出的未知點乘優化算法在不同GPU負載下的吞吐量表現情況，測試結果如圖6所示。從實驗結果來看，本文所提未知點乘優化算法在GPU高、低負載下吞吐量都超過了文獻[7]提出的算法，可達到7.04×106次/s。

圖6 未知點乘運算吞吐量測試結果

最后，設置線程塊大小為128，測試本文所提的SM2簽名、驗簽計算方案整體性能表現。圖7、圖8分別顯示了簽名、驗簽算法的吞吐量和時延在不同線程塊數量下的表現情況。從實驗結果可以看出，算法吞吐量隨著GPU運行線程數量的增長而增長，最終吞吐量趨于穩定，算法時延隨著GPU運行線程數量的增長而增大。其中，簽名和驗簽算法吞吐量分別可達到7.609× 107次/s和3.46× 106次/s，此時的算法時延分別為26.9 ms和150.4 ms。此外，本文提出的優化方案分別在3.1 ms和6.9 ms的低時延狀態下也能達到2.04× 107次 /s和1.85× 106次/s的吞吐量。

圖7 簽名算法吞吐量和時延測試結果

圖8 驗簽算法吞吐量和時延測試結果

為了評估本文所提簽名、驗簽優化方案的性能表現，本文與GPU平臺上已有的ECC優化成果進行了對比(如表7所示)。由于各個研究成果所使用的GPU設備不同，本文給出了GPU的整數/浮點性能作為GPU性能參考。從表7可以看出，本文使用GPU性能大約為Pan等人[7]的3.3倍，所實現簽名、驗簽算法吞吐量大約為其8.7倍和3.7倍，其中簽名運算性能提升尤為突出，這是主要是因為采用預計算表對固定點乘加速后，模逆運算成為影響簽名效率的最大瓶頸。而本文選擇了基于費馬小定理的模逆算法，避免了線程束分化現象，并細致優化底層模乘運算，使模逆運算效率得到極大提升，從而提高簽名性能。此外，考慮到本文優化的SM2算法開銷略大于Pan等人[7]優化的ECDSA算法，因此，可以得出結論，本文的SM2算法優化效果優于Pan等人[7]，和其他優化方案[21–23]相比，本文優化效果也處于領先地位。

表7 GPU平臺各個ECC優化方案性能對比

此外，本文還在普通家用GPU設備T1000上進行了同樣的測試，以驗證在不同計算能力的GPU設備上能否得到相同的實驗結論。表8為普通家用GPU設備T1000上各個算法的運行情況。從表中可以看出，在T1000設備上，簽名、驗簽算法吞吐量分別達到6.34×106次/s和3.45×105次/s。同時，可以看出本文所提模逆優化算法在T1000上性能同樣遠超擴展歐幾里得算法，且提出的未知點乘優化算法吞吐量在T1000上的吞吐量也超過了文獻[7]提出的算法。因此，本文所提各個優化算法能夠適應不同的GPU設備，具有良好的通用性。

表8 T1000上各個算法的性能表現

6 結束語

本文選擇了GPU作為SM2算法的優化平臺，提出了一種基于GPU加速的高吞吐量SM2數字簽名計算方案。通過使用GPU底層指令構建了高效的基礎運算，為上層運算提供效率上的支持；同時，結合GPU乘法計算能力強的特性，基于費馬小定理優化實現了高效的模逆計算模塊，提升模逆處理速度；而且利用倍點運算比點加運算開銷更低的特性，構造預計算表，提高計算效率；最后在GPU上實際實現了所提SM2簽名和驗簽的計算方案。實驗結果表明，所提計算方案在RTX3090單卡上可以達到7.609×107次/s的簽名吞吐量和3.46×106次/s的驗簽吞吐量。