商密算法性能優化研究與實踐

摘要：商用密碼算法的高性能實現是影響網絡安全建設與密碼泛在化應用的重要環節。聚焦SM2、SM3、SM4 算法，體系化、層次化研究不同商密算法的高性能軟件實現優化技術，從理論分析、測試驗證等維度對比分析優化技術并形成應用建議，以應用實踐的方式介紹高性能商密算法的典型場景，為高質量商用密碼發展提供支撐。

內容目錄：

1　商用密碼算法簡介

2　商密算法性能優化技術研究

2.1　SM2 算法性能優化

2.2　SM3 算法性能優化

2.3　SM4 算法性能優化

3　商密算法性能優化分析評估

3.1　SM2 算法性能優化分析評估

3.2　SM3 算法性能優化分析評估

3.3　SM4 算法性能優化分析評估

3.4　評估分析總結

4　商密算法性能優化應用實踐

4.1　面向政務云的高速率 SM2 簽名服務應用

4.2　基于高性能商密算法的隱私計算應用

5　結　語

密碼是網絡空間安全的根本性核心技術。我國將密碼分為核心密碼、普通密碼、商用密碼。商用密碼用于保護不屬于國家秘密的信息，被廣泛應用于政務、金融、能源、交通、水利、通信等行業領域以及大眾消費場景，與關鍵信息基礎設施安全、社會穩定以及經濟發展等息息相關。

我國高度重視商用密碼的發展與應用，先后提出了多項商用密碼算法，并以標準牽引、頂層推廣等方式，有效促進商用密碼在各行業、各領域、各場景的深化應用。一直以來，高效率密碼運算是密碼技術及密碼產品的核心。學術界、工業界均對商用密碼進行性能優化研究與實踐，提升核心競爭能力，保障高質量密碼供給。

本文關注商用密碼算法的高性能軟件實現技術，以體系化技術分析的視角，深入研究 SM2、SM3 及 SM4 等算法的高性能實現方法，從理論分析與仿真評估的維度給出不同優化方法的對比分析結果，得出不同優化技術的應用建議，最后以應用實踐的方式介紹高性能商密算法的典型場景，對高質量密碼供給與應用能力建設有一定參考價值。

商用密碼算法簡介

我國大力發展商用密碼技術與應用，已公開的商用密碼算法包括 SM1、SM2、SM3、SM4、SM7、SM9 及 ZUC（祖沖之）算法。SM2、SM3、SM4 這3 項密碼算法是 PKI 體系最常用的算法，也是使用最為廣泛的商密算法，鑒于此，本文重點研究此3 種算法。

SM2、SM3、SM4 算法均由中國國家密碼管理局發布，并先后成為密碼行業標準、國家標準及國際標準。SM2 算法是我國采用的公鑰密碼算法，其安全性基于橢圓曲線離散對數困難問題，算法主要包括數字簽名、密鑰交換協議和公鑰加密算法3 個部分。在 PKI 體系中，基于 SM2 算法的數字簽名技術在我國電子認證領域已廣泛應用。SM3 算法是我國采用的密碼雜湊函數標準，消息分組長度為512 位，摘要值長度為 256 位。SM3 算法廣泛應用于密碼協議、數字簽名、消息鑒別、完整性認證等領域。SM4 算法是我國采用的分組密碼算法，算法采用非平衡 Feistel 結構，加密算法和密鑰擴展算法迭代輪數均為 32 輪，分組長度和密鑰長度均為 128比特。SM4 算法主要用于數據的機密性保護，在音視頻加密保護、云存儲加密、數據庫加密、安全通道保護、敏感信息保護等領域廣泛使用。

商密算法性能優化技術研究

本節針對 SM2、SM3、SM4 算法特點，基于工業界、學術界已有成果，結合最新技術發展趨勢，分層次、體系化地梳理研究商密算法的高性能軟件實現技術。

2.1　SM2 算法性能優化

SM2 算法是基于橢圓曲線的公鑰密碼算法，算法依賴于橢圓曲線上的點運算，包括點加、倍點、點乘（標量乘）運算，以及有限域上大整數的算術運算，包括有限域上的加法、減法、乘法、乘法逆等。這些運算使得 SM2 具有層次結構，自上而下可以將其分為 4 層，如圖 1 所示。在算法優化中首先關注橢圓曲線點運算，其次是有限域中大數運算，這些算法的計算量大、結構復雜，存在算法效率不高、資源消耗較多等問題，因此國內外眾多學者對橢圓曲線算法、大整數基本運算進行了大量的研究。本節就 SM2 算法的主要優化方法進行了研究總結，總體而言優化方法可以分為橢圓曲線運算優化、大整數運算優化兩大類。

圖 1　SM2 算法層次結構

2.1.1　不同坐標系中點加與倍點運算

橢圓曲線上點坐標的表示方法主要用仿射坐標 (x,y) 和射影坐標 (x,y,z) 表示，這兩種坐標可相互轉換。射影坐標一般分為標準射影坐標、Jacobian加重射影坐標。

仿射坐標中橢圓曲線的表示方程公式為：該群中點的表示方法為 (x,y)。標準射影坐標 (x,y,z) 對應的仿射坐標為將的對應關系代入橢圓曲線中可得標準射影坐標下的方程為：Jacobian 加重射影坐標 (x,y,z) 對應的仿射坐標為將對應關系代入曲線得到在 Jacobian加重射影坐標下的方程為上述坐標中的點加運算、倍點運算（兩個相同點的點加運算）可在相應坐標方程下換算得到。

2.1.2　點乘運算

橢圓曲線點乘為 R=kP，其中 k 為整數，P 為橢圓曲線上的任意點。點乘運算通過點加與倍點運算構成，它是橢圓曲線最核心且非常耗時的運算，其計算速度從整體上決定了橢圓曲線密碼體制的效率。目前點乘運算的研究方法很多，主要為 k 的表達形式與預處理方式。k 的表達形式是將 k 進行不同的表示后，在計算 k 的過程中融入點加與倍點運算得到點乘結果。預處理方式是 P 為固定值，將 P的倍點進行存儲，然后通過查表計算當前倍點值。以下給出了有代表性的研究方法。

（1）二進制方法。二進制表示方法將 k 以二進制的形式展開為通過展開后的二進制串使用霍納法則計算 k。

（2）NAF 展開法。非相鄰型表示（Non Adjacent Form，NAF）是 k 的一種帶符號表示方法，k 的 NAF 表示為且沒有兩個連續的數字是非零的，為 k 的展開序列。

（3）窗口方法。窗口方法的思想是一次掃描w 位（w 為窗口寬度），使點 P 一次完成的計算，從而利用空間提高計算效率。有兩種表現較好的窗口算法。第 1 種為固定窗口算法，將 k 用二進制表示后，用固定長度 w 按照一定的規則劃分，即 k 的表示為其中表示向上取整。此方法可將分組數據重新編碼為規則模式，如使用 booth編碼方法編碼分組數據，從而防止點乘運算通過側信道泄漏信息，提高實現安全性。第 2 種為滑動窗口算法 w-NAF，整數 NAF 表達形式是將每兩位至多出現一個非零值的思想，演化為每 w 位中至多出現一個非零值，整數 k 表示為其中非零時都是奇數，且稱為k 的 w-NAF 表示，記為

（4）雙基鏈方法。雙基鏈算法是基于 Dimitrov提出的一種雙基數系統，將整數 k 用兩個不同的基表示，其最多在 O(logk/loglogk) 的時間復雜度內表示一個數。在雙基鏈系統中，對任意整數k可表示為將整數 k 的雙基鏈表示形式記為D(k)，可通過貪心算法來編碼得到雙基鏈形式。

2.1.3　素數域大整數運算

橢圓曲線上的點運算最終為有限域上的算術運算，有限域算術運算實現效率也影響著整數算法實現的效率。有限域上的運算包括加法、減法、乘法和模逆等基本運算，域上的加法、減法運算與代數運算方法基本相同，不同之處在于其運算結果需要求模，即約減。有限域上的約減、模乘、模逆等計算都非常復雜，耗時多，因此本節對這幾種方法進行研究。

（1）約減。約減是有限域中的基本運算之一，針對約減的優化主要有 Barrett 約減、Montgomery約減、快速約減這 3 類方法。Barrett 約減是一種低成本的求商運算，估算出一個近似值使得其中 n 是一個很小的數，因此最終的結果 r 通過少數的減法計算得出。Montgomery 約減是通過移位代替除法的一種方法，給定整數 X，選取 r 為2的 n 冪，然后計算時右移 n 位完成取模運算。快速約減的思想是當模數為素數時通過多次加法與減法操作代替除法，從而快速求得取模結果。

（2）模乘。本文稱用于的運算為模乘運算，實際上就是將乘法結果取模。模乘是公鑰密碼體制中的基本算法之一，其運行速度對公鑰密碼算法起著重要的作用。很多學者對模乘算法進行優化改進，常見的方法有基于 Barrett 約減的模乘算法、KOA 快速乘法以及 Montgomery 模乘算法。

（3）模逆。對于素數如果存在使得則稱為 a 模 p 的逆元。有限域中逆元計算量比乘法和平方耗時多。常見的素域上求逆的方法有擴展歐幾里得算法、基于二進制的擴展歐幾里得算法、Lehmer 擴展歐幾里得算法等。擴展歐幾里得算法反復使用輾轉相除法，通過輾轉相除中的商反演計算出兩個正整數的最大公約數，即可找到兩個整數 s、t 使得若等式兩邊同時模 p 可得，則 s 為 a 模 p 的逆。整數除法可通過移位操作實現，根據這一思想有了基于二進制的擴展歐幾里得算法。使用歐幾里得算法求逆過程中需多次進行大整數除法運算求商，而大整數的除法運算非常耗時，因此如果只用兩個數的高位計算商時，可提高計算效率。Lehmer 擴展歐幾里得算法的思想是用小整數的除法代替大整數的除法，小整數的擴展歐幾里得算法替代大整數的擴展歐幾里得算法，從而提高計算效率。

2.2　SM3 算法性能優化

如圖 2 所示，SM3 雜湊算法采用 M-D 結構的構造方式，對長度為比特的消息 m 通過填充分組、消息拓展、迭代壓縮的方式生成 256比特的雜湊值。

圖 2　SM3 M-D 結構

文獻 [13] 利用 Intel VTune Amplifier XE 分析了普通實現 SM3 算法的熱點，壓縮函數和消息拓展是最耗時的部分，其耗時分別占總耗時的 65.9% 和24.3%。因此，SM3 算法中的壓縮函數和消息拓展是實現 SM3 算法性能優化的重要方法。此外，隨著硬件技術的發展，X86、ARM 等主流硬件平臺均推出了 SIMD 指令，可以在上述環節嵌套并行指令以進一步提升性能。

2.2.1　消息拓展和壓縮函數優化

SM3 算法性能優化主要是從消息拓展和壓縮函數兩方面展開。消息拓展是將 512 比特的消息分組擴展到 132 個消息字。在優化實現中，將拓展的132 個消息字計算調整到壓縮函數中執行，以減少數據加載和存儲。壓縮函數的優化實現可以通過調整結構和流程、常數計算等方面著手，可歸納為減少壓縮函數循環移位導致的賦值運算次數；對壓縮函數的中間變量生成流程進行優化，去除不必要的賦值，減少中間變量個數；利用預計算和存儲常數，以進一步優化常數運算。

2.2.2　SIMD 并行指令優化

上述技術方案未考慮硬件指令加速的情況。事實上，SIMD 指令可以加速消息拓展的部分實現，圖 3 較為清晰地展示出了如何利用 SIMD 優化 SM3。

圖 3　SIMD 優化的 SM3

每一個是 32 bit 的字，4 個可以填滿 1個 SIMD 寄存器。圖 3 右側就是把消息放進 SIMD寄存器，然后再做消息擴展。和圖 3 左側 1 次計算出一個字相比，右側一次可以計算出 3 個字之所以不是一次計算出 4 個字是因為計算需要用到（灰色部分），但是擴展出來的，也就是說，需要的時候還不存在。在具體的實現中，可以先等計算完成，再用圖 3 左側的方法計算

2.3　SM4 算法性能優化

SM4 是一個分組密碼算法，分組長度和主密鑰長度均為 128 bit。128 bit 主密鑰經過密鑰拓展算法拓展為 32 個 32 bit 輪子密鑰，加 / 解密變換均為 32輪輪函數 F 的迭代。輪函數涉及比特操作以及合成置換 T。T 是由非線性變換 τ 和線性變換 L 構成。上述流程中最為耗時的部分是非線性變換 τ，其核心涉及 S 盒查表操作。目前針對 SM4 算法性能優化的方法也主要集中于 S 盒操作的優化，包括直接查表優化、SIMD 優化、復合域及比特切片等。

2.3.1　查表優化

查表優化實現是 SM4 算法優化實現方法中最早出現、最常見的方法，其核心思想是將密碼算法輪函數中盡可能多的變換操作通過預計算制成表，即通常所說的“查大表”。

2.3.2　SIMD 并行指令優化

并行分為細粒度并行和粗粒度并行 2 種。由于 SM4 算法不適合使用細粒度并行，因此選取粗粒度并行策略實現 SM4。粗粒度是多組消息的并行處理，分組密碼通常是在某種工作模式下加 / 解密大量數據，在特定的工作模式，如在電碼本模式（Electronic Codebook Book，ECB）、計算器模式（Counter，CTR）、Galois 計數器模式（Galois/Counter Mode，GCM）、密碼分組鏈接模式（Cipher Block Chaining，CBC）（解密方向）下，分組密碼可并行處理多組消息。下述為 128 bit 寄存器下的SIMD 并行操作：

（1）查表指令：首先使用 1 ～ 4 個 128 bit 的向量寄存器構成查找表，其次使用另一個 128 bit 寄存器作為索引，將結果存入 128 bit 寄存器中。

（2）SM4 并行查表：SM4 的 S 盒一共有256×8 bit，即需要消耗 16 個向量寄存器存儲查找表，每次查表最多能使用 4 個向量寄存器作為查找表，進行 4 輪的查表。

（3）SM4 數據加載：在一輪 SM4 迭代過程中，需要查表的數據為 32 bit，為了盡可能利用好 128bit 的向量寄存器，將 4 組消息的 32 bit 集中于同一個向量寄存器中。

2.3.3　復合域及比特切片

與傳統基于查找表法的方式相比，該方法采用代數運算的方式，計算較為簡單。S 盒的運算由兩部分構成：線性的仿射變換和非線性的有限域求逆。仿射變換容易實現，因此主要計算難度在于的求逆問題。根據有限域性質，通過同構變換，將的有限域運算變到復合域上進行。在實際流程中，通過比特切片技術，編排待處理數據的存儲結構，然后使用仿射變換與有限域上的求逆來代替 S 盒查表，通過復合域大大降低域運算的復雜度。

商密算法性能優化分析評估

本節對前述商密算法優化技術進行理論分析與仿真評估，給出不同優化方法的對比分析結果，最后從實踐的角度給出應用建議。

3.1　SM2 算法性能優化分析評估

3.1.1　點加與倍點運算

點加與倍點是橢圓曲線的計算基礎，不同坐標系下其計算方法不同導致計算效率也不同。仿射坐標計算點運算需求模逆，計算復雜度高，耗時多，效率低，因此在實際工程實現中通常不考慮該方法。相比來說，Jacobian 加重射影坐標的運算效率最高，因此在工程實現中通常采用 Jacobian 加重射影坐標進行點運算。為了方便使用，工程實現對外點的表示使用仿射坐標，內部計算時存在 Jacobian 加重射影坐標與仿射坐標的相互轉換。

3.1.2　點乘運算

本文研究了點乘運算二進制方法、NAF 展開法、窗口方法以及雙基鏈方法。二進制方法中非零符號的漢明權重未做優化，開銷較大，現已很少使用。NAF 展開法的性能通常會低于窗口方法。雙基鏈方法使用貪心算法，漢明權重很難預估，運行速度不確定因素較大，工程應用較少考慮。本節將重點對比分析窗口方法中的滑動窗口算法 w-NAF、booth編碼與固定窗口結合方法。

SM2 算法素數域長為 256 位，在 256 位數據長度中對不同寬度下基于 w-NAF 與基于 booth 編碼的兩種點乘算法進行性能分析。本節針對兩種不同點的形式（固定點乘與非固定點乘）分別進行了比較分析，結果見表 1，其中，PA 和 PD 分別代表一次點加和倍點運算，M 代表一次乘法運算。

表 1 w-NAF 與 booth 編碼的點乘性能分析

對固定點采用預計算存儲方式實現點乘運算時，隨著寬度增加，兩種方法的計算量都在減少、存儲量增加。寬度相同時基于 w-NAF 方法的計算開銷比基于 booth 方法的計算開銷高很多，存儲開銷少很多。為提高計算效率，基于 booth 編碼的方法效率會更高。選擇寬度時，如不考慮存儲開銷則寬度越大效率越高，但實際應用中，存儲資源是有限的，應綜合考慮計算與存儲開銷，因此選擇寬度為 7 的基于 booth 編碼的算法較為適用。

當點不固定時，兩種算法在寬度為 5 處計算開銷都最低。當兩種計算開銷最低時，基于 w-NAF的點乘性能稍優于基于 booth 編碼的點乘性能。SM2 算法中兩種點乘方式的使用頻率基本相等，綜合分析 SM2 算法采用基于 booth 編碼方式實現的效率會更高，并且安全性更好。

3.1.3　素數域大整數運算

在約減運算方面，Barrett 約減及 Montgomery 約減性能大致相當。快速約減算法不需要除法，性能是最好的，推薦使用。在模乘運算方面，由于Montgomery 模乘算法通過移位避開了除法運算，其性能優于 Barrett 約減的模乘算法及 KOA 快速乘法，推薦使用。同時，Montgomery 模乘算法底層使用Montgomery 約減算法，因此在工業應用中可配合使用。在模逆運算方面，重點分析比較基于二進制的歐幾里得求逆算法和 Lehmer 擴展歐幾里得求逆算法。本文在 Intel(R) Core(TM) i5-7500 平臺上，用 32字節的數據測試了兩種求逆方法的性能，測試結果如表 2 所示。測試結果表明 Lehmer 歐幾里得算法的性能是二進制歐幾里得算法的 4 倍左右。推薦采用 Lehmer 歐幾里得算法。

表 2 兩種模逆算法性能測試結果

3.2　SM3 算法性能優化分析評估

本文對 2.2 節提出的兩項 SM3 性能優化技術方案進行測試驗證。方案 1 為 C 語言實現，采用消息拓展和壓縮函數。方案 2 為匯編實現，采用消息拓展壓縮函數以及 SIMD 指令。對比基線為原始未優化算法。經試驗測得，方法 1 和方法 2 加速效果相當，相比于原始算法性能均能提高 1 倍左右。不同之處在于方案 1 的性能與平臺差異較小，方案 2 的性能與平臺關系較大，若平臺對匯編指令支持不夠友好，則可以用于并行加速的部分甚少，加上匯編語言會增加代碼的復雜度，整體性能會有所下滑。在具體項目應用中，建議在兼容性較好的硬件平臺采用方案 2，在硬件環境比較特殊的場景下采用方案 1。

3.3　SM4 算法性能優化分析評估

本文 2.3 節研究了 3 項 SM4 性能優化技術方案。本節針對查表優化（方案 1）、SIMD 并行指令優化（方案 2）兩項技術方案進行了對比測試，對比基線為原始未優化算法。采用 SM4 ECB 模式。經試驗測得，方案 1 相比于基線方案性能提高至 2.7 倍，方案 2相比于基線方案性能提高至 5 倍。整體來說，方案2 的性能優于方案 1，但方案 2 與平臺相關，加速效果不盡相同，方案 1 跨平臺，可以廣泛使用。此外，比特切片及復合域等創新技術往往是在 SIMD 基礎上進行的再度優化，性能高于方案 1 和方案 2，但該方法也存在硬件平臺的差異，推薦在硬件支持的情況下使用。

3.4　評估分析總結

基于上述分析，總結商密算法性能優化方法的性能情況、應用場景并給出推薦指數建議，見表 3。針對 SM2、SM3、SM4 算法，本文總結的相關方法大部分可以配合使用，以達到性能疊加的效果。同時部分優化技術與硬件平臺強關聯，比如 CPU 指令集是否支持、CPU 位寬情況、硬件存儲資源是否受限等，在具體應用時，應結合硬件資源情況，進行方法的組合和篩選，在滿足實際需求的同時最大限度地提升性能。

商密算法性能優化應用實踐

隨著“等保”“密評”“國密改造”等工作的推進，商用密碼應用呈現泛在化發展趨勢，越來越多的信息系統紛紛采用商用密碼技術進行安全保護。本文選取云計算、隱私計算兩大創新場景，以新技術融合應用的視角，介紹高性能商密算法應用實踐。

4.1　面向政務云的高速率 SM2 簽名服務應用

政務云承載了大量的政務數據與應用，具備大規模集中計算、高效率業務保障、統一身份認證等需求。在政務云中構建密碼資源池，采用云簽名驗簽服務器提供高效率的 SM2 簽名服務，同時考慮系統的可擴展性，在密碼資源池中基于虛擬化服務器，部署高性能 SM2 軟算法，配套提供 SM2 軟算法簽名服務，通過軟、硬兩套方案協同，針對不同等級用戶、不同應用對象按需提供密碼運算功能，確保服務的可用性。相關應用場景見圖 4。

表 3 商密算法性能優化評估總結

圖 4　面向政務云的高速率 SM2 簽名服務場景

4.2　基于高性能商密算法的隱私計算應用

隱私計算是數據要素化發展的關鍵技術，密碼是其安全基石。隱私計算包含大量的對稱加密、消息雜湊、非對稱運算等密碼算法。可基于高性能商密算法，打造安全、合規的隱私計算協議。圖 5 為融合高性能商密算法的隱私計算應用場景，系統采用三方外包計算的模式，計算方在執行隱私計算協議時，將優化后的 SM4 算法應用于混淆電路場景中，優化后的 SM2 橢圓曲線算法應用于 PSI 場景中，優化后的 SM3 消息雜湊算法應用于特征工程等算法協議中，系統在實現密碼算法的國密改造的同時，也極大程度地提升了性能，促進新技術的融合應用發展。

圖 5 基于高性能商密算法的隱私計算應用場景

結　語

本文立足于 SM2、SM3、SM4 算法，分層次、成體系地梳理研究了商密軟算法的高性能優化實現方法，給出了不同優化技術的理論分析與仿真評估結果，得出了相關優化技術的應用建議，并以應用實踐的方式探討了高性能商密算法的應用場景，為高質量密碼能力建設提供了參考路徑。下一步，將深入應用場景及平臺環境，細化細分領域的算法優化技術方案，以進一步支撐高性能商密算法應用落地。