輪內流水線型SM4算法的FPGA優化

Abstract：Aiming at the problems of complex structure and slow operation speed during the implementation of SM4 algorithm in field programmable gate array （FPGA），the FPGA implementation of SM4 algorithm is further optimized based on the pipelining idea.Multiple FPGA implementation strategies of SM4 algorithm are analyzed，and the critical path of each implementation strategy is found. The FPGA implementation strategy of the SM4 algorithm S-box is improved by spliting the S-box operation into lookup table （LUT） level storage operation and implementing it based on the LUT primitive，which reduces the complexity of the S-box operation. An improved in-round pipelined SM4 algorithm is proposed to shorten the critical path of the algorithm to a single-level LUT operation. The improved algorithm is synthesized and implemented based on the ZYNQ-7O2O development board，and the realized scheme has a running clock frequency of 518MHz and a throughput of 66.30Gb/s ，which is better than the existing scheme.

Key words：SM4 algorithm;FPGA;pipeline structure

0 引言

在當今數字化時代，信息安全問題變得越來越重要.隨著互聯網的普及和信息技術的快速發展，人們的敏感信息和機密數據面臨著日益增長的威脅，例如黑客攻擊、數據泄露和網絡間諜活動等.為了保護信息的機密性、完整性和可用性，加密技術成為了信息安全領域中不可或缺的一部分.

SM4分組密碼算法[作為我國自主研發設計并采用的首個分組對稱密碼算法，于2006年公布，2012年成為國家密碼行業標準，2018年6月正式成為國家標準，2021年作為國際標準由國際標準化組織ISO/IEC正式發布.SM4被廣泛應用于國內敏感但非機密場合，尤其是通信、醫療、金融等領域，將逐步取代數據加密標準（DES）、高級加密標準（AES）等國外分組密碼標準2.

SM4算法可部署于中央處理器（CPU）[3-5]、圖形處理器（GPU）[6-8]、FPGA[9-11]等各類硬件平臺中.其中，基于FPGA平臺的部署方案較為靈活，能夠在資源消耗與運算速度之間進行取舍.何詩洋等[2基于FPGA實現了低資源消耗的循環型SM4算法，所實現方案僅消耗193個邏輯單元.李建立等[13]提出輪內流水線型SM4算法FPGA實現方案，在ZCU-102開發板中實現了 420MHz 的時鐘頻率.本文提出了改進的基于FPGA的SM4算法輪內流水線方案，優化了S盒的流水線劃分策略，進一步提高了SM4算法的運行時鐘頻率.

1 SM4算法原理

1.1 SM4密碼算法的加密運算

SM4密碼算法是一個分組算法.該算法的分組長度為 128bit ，密鑰長度為128bit.加密算法與密鑰擴展算法均采用非線性迭代結構，運算輪數均為32 輪.

SM4密碼算法的輸入為128bit明文及128bit密鑰，輸出為128bit密文.將明文輸人記為（X₀，X₁，X₂，X₃）∈（Z₂³²）⁴ ，將密鑰輸入記為 MK =（MK，MK，MK，MK）∈（Z₂³²）⁴ ，將密文輸出記為 （Y₀，Y₁，Y₂，Y₃）∈（Z₂³²）⁴ ：

加密算法由32次迭代運算和1次反序變換 R 組成.加密運算的初始輸入由明文輸入 （X₀，X₁ . X₂，X₃）∈（Z₂³²）⁴ 以及由密鑰 MK 經過輪密鑰擴 展運算得到的 rk_i（i=0，1，…，31） 組成.

設某一輪迭代運算的輸入為 X_i 、 X_i+1 ） X_i+2 ！

X_i+3?rk_i ，輸出為 X_i+4 .將該輪迭代運算的第一步運算結果記為 A ，有：

A=X_i⊕X_i+1⊕X_i+2⊕X_i+3⊕rk_i

A 為32bit數據.將 A 拆分為4個8bit數據，記為 a₀…a₁…a₂…a₃ ，即：

A=（a₀，a₁，a₂，a₃）∈（Z₂⁸）⁴

迭代運算的第二步為對由 A 拆分得到的 a₀ 、a₁，a₂，a₃ 進行非線性變換 由四個并行的S盒組成.將四個S盒的輸出總記為 B ，則有：

B=（b，b₁，b₂，b₃）=τ（A）

=（Sbox（a₀），Sbox（a₁），Sbox（a₂），Sbox（a₃））

其中S盒為8bit輸入、8bit輸出的非線性變換結構，對于確定的輸入有對應確定的輸出.SM4算法的S盒具體數據可通過對應的國家標準查詢.

迭代運算的第三步為線性變換 L ，即對S盒的輸出 B 循環移位后進行異或，將異或得到的結果記為 c ：

C=L（B）

=B⊕（Blt;lt;2）⊕（Blt;lt;10）

⊕（Blt;lt;18）⊕（Blt;lt;lt;24）

最后再將 C 與迭代運算的輸入 X_i 進行異或，就完成了一次迭代運算，即：

X_i+4=C⊕X_i

加密算法的32次迭代運算完成后，執行反序變換 R ，得到密文輸出 （Y₀，Y₁，Y₂，Y₃） ，見式（6）：（Y，Y₁，Y₂，Y₃）=R（X₃₂，X₃₃，X₃₄，X₃₅） （6）

1.2SM4密碼算法的密鑰擴展運算

密鑰擴展算法的結構與加密運算中的迭代運算結構基本一致，只需將迭代運算中的線性變換 L 替換為 L^' 即可.

L^′（B）=B⊕（Blt;lt;13）⊕（Blt;lt;23）

1.3SM4密碼算法的解密運算

SM4算法中數據解密和數據加密的算法結構相同，只是輪密鑰的使用順序相反，解密輪密鑰是加密輪密鑰的逆序[1].

1.4SM4密碼算法的迭代運算分析

迭代運算的第一步可以概括為4個32位的數據進行異或；第二步可以概括為4個8位的數據通過S盒進行非線性變換；第三步可以概括為6個32位數據進行異或.輪密鑰擴展運算的步驟與迭代運算的步驟基本一致，只需將迭代運算第三步中6個32位數據進行異或替換為4個32位數據進行異或即可.

將迭代運算第一步運算所需時間記為 t_xor4 ，第二步運算所需時間記為 t_Sbox ，第三步運算所需時間記為 t_xor6 .將迭代運算的關鍵路徑延時記為 t_cp ，則有：

t_cp?max（t_xor4，t_Sox，t_xor6）

對于SM4算法的迭代運算，其第一步與第三步的異或運算結構簡單，能夠在FPGA中通過單個LUT實現.而S盒的結構相對復雜，在FPGA中需要多個LUT以及寄存器（REG）才能實現.因此有：

t_Sboxgt;max（t_xor4，t_xor6）

t_cp?t_Sox?max（t_xor4，t_xor6）

將迭代運算的FPGA最高運行時鐘頻率記為f_max ，有：

由式（11）可知，S盒的運算速度制約了SM4算法在FPGA中的最高時鐘頻率.同時，算法的理論最高時鐘頻率為異或運算的時鐘頻率，

2SM4算法的FPGA實現架構

2.1低資源消耗的循環型架構

循環型架構以節省資源消耗為目的，由一個輪密鑰擴展模塊、一個加密模塊以及控制邏輯組成.由于加密模塊需要比輪密鑰擴展模塊晚一個時鐘周期啟動，因此完成一次加密至少需要33個時鐘周期[14].

由于只有一組硬件模塊，因此循環型架構中每個時鐘周期只有輪密鑰擴展模塊/加密模塊的輸入/輸出發生變化，這一變化過程由有限狀態機控制.循環型SM4算法架構如圖1所示.

1上一輪的計算結果輪密鑰擴展模塊下一輪的輸入有限

狀態 擴展得到的輪密鑰機 ↓1上一輪的計算結果加密模塊下一輪的輸入

對循環型架構的優化主要集中于對控制邏輯的改良，設計一個高速高效運行的控制模塊是循環型SM4算法系統的關鍵15].

Shang等[16提出了一種超緊湊的SM4知識產權（IP）架構，該架構采用8位作為處理單元，只例化了一組加密運算/輪密鑰擴展運算模塊，并且只有一個S盒.基于Virtex-6FPGA芯片進行實現，資源消耗為164個邏輯單元，時鐘頻率為253MHz

由于同一用戶的密鑰幾乎是不變的，因此Lv等[15]設計了新舊密鑰比較機制，通過控制模塊根據對比結果決定是否執行輪密鑰擴展運算.同時，為了在密鑰擴展時繼續使用舊的輪密鑰，控制模塊分別對密鑰擴展過程、各模塊所處理的數據以及加密和解密所需的輪密鑰進行編號.相應地，在設計中也有比較和數據選擇機制.因此，當密鑰更改時，可以將新擴展的輪密鑰與舊輪密鑰同步地取出到各自所需.

梁浩等從S盒優化角度人手，提出一種基于復合域的S盒實現方式.采用循環型架構實現整個算法，取得了比查找表式S盒更小的面積消耗.

總體而言，目前各實現方案中的循環型架構，其最小單元均為單個加密模塊.單個加密模塊中迭代運算的三個步驟需要在一個時鐘周期內串行執行，因此循環型架構的迭代運算關鍵路徑延時 t_cp1 為：

t_cp1=t_xor4+t_Stor+t_xor6

可見循環型架構的運算速度受限于單次迭代運算的執行所需時間.并且由于以低資源消耗為目的，一些以面積為代價的速度優化方法并不適用，因此循環型架構無法達到很高的時鐘頻率.

2.2輪間流水線型架構

輪間流水線型架構由1個輪密鑰擴展模塊與32個加密模塊組成，結構如圖2所示.

在加密模塊開始工作之前，輪密鑰擴展模塊首先開始工作，耗時32個時鐘周期完成輪密鑰擴展運算.在輪密鑰擴展運算完成后，加密模塊1首先開始工作，其余加密模塊由于缺乏輸入處于等待狀態.一個時鐘周期后，加密模塊1完成計算，將計算結果輸入加密模塊2，此時加密模塊1與加密模塊2同時開始工作.之后的每一個時鐘周期，一個新的加密模塊結束等待開始工作，直到32個加密模塊同時開始工作.此時輪間流水線啟動完成，每1個時鐘周期能夠完成一次加密運算并將加密得到的密文進行輸出.

在此基礎上，Guan 等[18]提出了2輪迭代的16級流水線結構、4輪迭代的8級流水線結構、8輪迭代的4級流水線結構，并對輪間流水線型SM4算法的速度與面積關系進行了分析.朱麒瑾等9實現了可變流水級SM4加解密算法硬件設計，并將該算法封裝成為符合高級外圍總線（APB）和高級可擴展接口（AXD協議的標準IP.

張宏科等[19]對SM4算法復合域S盒進行了改進，采用循環密鑰擴展與32級流水線進行加解密，降低了資源消耗并提高了數據處理速度.另外，采用代數式S盒，將線性運算合并，從不同不可約多項式生成的合并矩陣中篩選出最優矩陣以減少組合邏輯，進一步降低了資源消耗和運算量，提高了工程頻率.其速度優先的實現方案系統頻率達到390 MHz.

與循環型架構相同，輪間流水線型架構的最小單元亦為單個加密模塊.單個加密模塊中迭代運算的三個步驟需要在一個時鐘周期內串行執行，因此輪間流水線型架構的迭代運算關鍵路徑延時 t_cp2 為：

t_cp2=t_xor4+t_Soox+t_xor6

可見循環型架構的運算速度同樣受限于單次迭代運算的執行所需時間.

2.3輪內流水線型架構

2.3.1 輪內流水線型架構原理

輪內流水線是在輪間流水線架構的基礎上，將流水線思想應用于SM4算法的單次迭代運算內部.將單次迭代運算拆分為多個分步驟，以單個分步驟作為最小單元，每個分步驟都需要一個時鐘周期進行計算.分步驟之間形成流水線結構，縮短了迭代運算的關鍵路徑.不同的輪內流水線方案有不同的分步驟劃分，分步驟的劃分方式以及實現方式決定了輪內流水線型架構的性能.輪內流水線型SM4算法架構如圖3所示.

由于單次迭代運算需要由多個時鐘周期完成，因此輪內流水線型架構需要更多的時間啟動流水線.假設輪內流水線型架構單個加密模塊進行一次運算需要 n 個時鐘周期，則輪密鑰擴展運算完成后輪內流水線需要 n*32 個時鐘周期進行啟動.在流水線啟動完成后每1個時鐘周期能夠完成一次加密運算并將加密得到的密文進行輸出，

輪內流水線型架構可以對S盒運算進行拆分，用多個時鐘周期進行S盒運算，以降低S盒的關鍵路徑延時.設拆分后S盒的關鍵路徑延時為t_S ，則：

t_Sbox?t_S

迭代運算中第一步與第三步均為不可再分的異或運算，可以由單級LUT實現，因此有：

t_Sbox?t_S?max（t_xor4，t_xor6）

將輪內流水線型架構的迭代運算關鍵路徑延時記為 t_cp3 ，則有：

t_cp3=max（t_xor4，t_xor6，t_S）=t_S

結合式（12）、（13）、（15）、（16），可知輪內流水線型架構的關鍵路徑延時要小于循環型架構和輪間流水線型架構，并且輪內流水線型架構的理論最短關鍵路徑為單級LUT運算.

2.3.2 改進的輪內流水線型S盒

根據1.4節的分析，一次加密運算可以分為三個步驟：第一步為異或計算，第二步為S盒計算，第三步為循環移位后的異或計算.其中異或運算易于硬件實現，而S盒計算相對復雜，存在優化空間.

SM4算法的S盒可以看作從8bit數據輸入到8bit數據輸出的非線性變換.對于確定的輸人，S盒的輸出也是確定的，因此可以通過存儲的方式實現S盒.在FPGA中，存儲器件有BRAM、LUT等.BRAM是一種可編程存儲資源，大多數FPGA中集成了一定數量的BRAM.在實際應用中，BRAM能夠根據功能要求進行配置[20].LUT作為FPGA中最重要的資源，能夠實現極其復雜的存儲和邏輯功能[21].BRAM的缺點在于速度相對較慢，而LUT是FPGA中最快的存儲器類型.因此在時鐘頻率較高的項目中，更適合使用LUT進行存儲.

在FPGA芯片中，有兩種基本LUT，分別為6輸入LUT和4輸入LUT.單個6輸入LUT的輸入為6bit數據，輸出為1bit數據.其輸入與輸出關系可以用64位二進制數來表示.在使用6輸入LUT原語時，給定64位二進制數，就確定了該6輸入LUT的輸入輸出關系.將兩個6輸入LUT并聯，再加入一個二選一數據選擇器（MUX），可以構成一個7輸入LUT；同理，將四個6輸人LUT6并聯，再加入一個四選一數據選擇器，可以構成一個8輸入LUT，其結構如圖4所示.

對于S盒的8bit輸入、8bit輸出的存儲需求，可以通過8個8輸人LUT并聯來實現，其結構如圖5所示.

因此對于SM4算法的S盒，可以通過32個并聯的6輸入LUT以及8個四選一數據選擇器來實現.并且，可以使用6輸入LUT來代替四選一數據選擇器.這樣實現的S盒總體結構為兩級6輸人LUT，如圖6所示.

圖6中的兩級6輸人LUT直接相連，輸入數據在一個時鐘周期內需要完成兩級LUT運算，因此該S盒的關鍵路徑即為兩級LUT運算.在兩級LUT之間插人寄存器，將第一級LUT的輸出緩存一個時鐘周期后再輸入第二級LUT，則此時S盒的關鍵路徑縮短為單級LUT運算.同時，在第二級LUT之后插入寄存器，對S盒的輸出進行緩存，方便后續處理.改進后的S盒結構如圖7所示.

2.3.3 改進的輪內流水線型架構

結合改進后的S盒結構，可將加密運算拆分為四個分步驟，形成輪內流水線，如圖8所示.

在改進的輪內流水線型SM4算法的迭代運算中，輪內流水線的第一級為4個32位數據進行異或，可以通過32個并聯的4輸人LUT完成；輪內流水線的第二級為S盒第一級LUT運算，由32個并聯的6輸人LUT完成；輪內流水線的第三級為S盒第二級LUT運算，由8個并聯的6輸入LUT完成；輪內流水線的第四級為5個32位數據進行異或，可以通過32個并聯的6輸人LUT完成.可知改進后的輪內流水線結構的每一級運算均為單級LUT運算，因此系統的關鍵路徑即為單級LUT運算，達到了2.3.1小節中提出的理論最短關鍵路徑.

本文的輪內流水線結構需要 4*32 個時鐘周期進行啟動.流水線啟動完成后，每個時鐘周期能夠完成一次加密運算并將密文進行輸出.

3 測試與驗證

3.1改進的輪內流水線S盒測試結果基于Vivado2019.1軟件，對本文提出的改進輪內流水線型S盒進行了性能測試.

結果顯示對于單個S盒，基于ZYNQ-7020開發板進行綜合與實現，S盒的運行頻率可達625MHz ;資源消耗為 40LUT+42 個觸發器（FF），接近2.3.2小節中提出的理論最小資源消耗.

同時，基于ZYNQ-7020開發板對單個LUT串聯單個寄存器的結構進行了綜合與實現，結果顯示其最高運行頻率同樣為 625MHz 這表明本文所提出的改進S盒的關鍵路徑即為單級LUT運算，與2.3.1小節中提出的理論值相符.

3.2改進的輪內流水線SM4密碼算法測試結果

基于Vivado2019.1軟件，對本文提出的改進流水線型SM4算法進行了仿真.仿真過程中設定以10ns 為一個時鐘周期.自仿真的135ns至 175ns SM4運算模塊的輸人密鑰為0123456789ABCDEFFEDCBA9876543210，輸人明文依次為00000000000000000000000000000000、11111111111111111111111111111111、22222222222222222222222222222222、33333333333333333333333333333333、44444444444444444444444444444444.Vivado 仿真軟件中的輸入數據如圖9所示，

在1415ns時，觀察到SM4運算模塊完成了加密，輸出的密文依次為2677f46b09c122cc975533105bd4a22a、6b3633a5ed04f5abd5197870b5506642、7c3bc4eb1c18e7fld879ea602eec46cf、99cfe9d2b4f88cb9d52049f758e230d9、d7a7d1b8c65c593ae8694c078c54e853，分別與之前輸人的明文及密鑰相對應.Vivado仿真軟件中的輸出數據如圖1o所示.

從輸入明文到完成加密，用時 1 280ns ，對應128個時鐘周期，符合流水線啟動所需時間的理論值.輸入的明文密鑰與輸出的密文能夠正確匹配，證明了加密模塊的正確性；每個時鐘周期都能夠輸出密文，證明了流水線結構的有效性.

4性能比較與分析

基于ZYNQ-7020開發板對本文提出的改進輪內流水線型SM4算法進行了綜合與實現，實現結果消耗了18498LUT和23485FF，時鐘頻率為 518MHz與3.1節中單個S盒的實現結果對比，完整算法的實現結果有著更低的時鐘頻率.這是因為完整的算法有更復雜的運算邏輯以及更高的資源消耗，導致布局布線的性能受到了一定影響.

對部分文獻中的SM4算法FPGA實現方案進行了比對，如表1所示.

與循環型方案以及輪間流水線型方案對比，輪內流水線型方案的系統關鍵路徑較短，因此可以達到更高的時鐘頻率.同時，由于輪內流水線型方案的整體流水線級數更高，因此需要更為復雜的控制邏輯以及額外的存儲單元，這導致輪內流水線型方案的資源消耗相對更高，符合速度與面積互換的原則.

在李建立等[13]提出的輪內流水線方案中，算法的關鍵路徑為2個與門、7個異或門.在FPGA中單個6輸人LUT最多可等效為5個異或門，因此該方案的關鍵路徑至少為兩級LUT運算.本文提出的改進流水線型方案，其關鍵路徑為單級LUT運算，因此取得了更高的時鐘頻率.

5結論

本研究以提升SM4算法的FPGA運算速度為目的，從關鍵路徑的角度對該算法進行了分析.通過將SM4算法的S盒拆分為基本的LUT運算，簡化了S盒的硬件結構，提高了S盒的運算速度.

結果表明對于SM4算法，在采用輪內流水線型架構且將分步驟劃分到LUT級別的情況下，能夠將系統的關鍵路徑延時降到最低，取得較高的時鐘頻率.基于ZYNQ-7020開發板進行了仿真與綜合實現，仿真結果證明了改進輪內流水線架構的正確性.實現結果的運行時鐘頻率達到 518MHz ，較已有方案提升了 23.3% ，適用于對速度有較高要求的加密場景.

參考文獻

[1]GB/T32907-2016，SM4分組密碼算法[S].

[2]李胡，彭長根，侯金秋.流密碼框架下的SM4專用認證加密算法[J].計算機工程與應用，2024，60（2）：272-278.

[3]陳晨，郭華，劉源灝，等.基于寄存器的SM4軟件優化實現方法[J].密碼學報，2024，11（2）：427-440.

[4]陳晨，郭華，王闖，等.一種基于復合域的國密SM4算法快速軟件實現方法[J].密碼學報，2023，10（2）：289-305.

[5]王磊，龔征，劉哲，等.基于塔域的SM4算法快速軟件實現[J].密碼學報，2022，9（6）：1081-1098.

[6]董建闊，黃躍花，付宇笙，等.基于異構多核心GPU的高性能密碼計算技術研究進展[J」.軟件學報，2024，35（12）：5 582-5608.

[7]李曉東，胡一鳴，池亞平，等.基于通用計算平臺SM4-CTR算法并行實現與優化[J].密碼學報，2022，9（4）：663-676.

[8]李秀瀅，吉晨昊，段曉毅，等.GPU上SM4算法并行實現[J].信息網絡安全，2020，20（6）：36-43.

[9]朱麒瑾，陳小文，魯建壯.可變流水級SM4加解密算法硬件設計及FPGA實現[J].計算機工程與科學，2024，46（4）：606-614.

[10]翟嘉琪，李斌，周清雷，等.基于FPGA的高性能可擴展SM4-GCM算法實現[J].計算機科學，2022，49（10）：74-82.

[11]王凱，劉凱，李拓，等.可重構高速數據加密系統設計和實現[J].電子測量技術，2021，44（19）：8-15.

[12]何詩洋，李暉，李鳳華.SM4算法的FPGA優化實現方法[J].西安電子科技大學學報，2021，48（3）：155-162.

[13]李建立，莫燕南，粟濤，等.基于國密算法SM2、SM3、SM4的高速混合加密系統硬件設計[J].計算機應用研究，2022，39（9）：2 818-2825，2 831.

[14]劉金峒，梁科，王錦，等.SM4 加密算法可裁剪式結構設計與硬件實現［J].南開大學學報（自然科學版），2019，52（4）：41-45.

[15]Lv Q，LiL，Cao YY.The IP-core design of controller andF/F'transformer in high-speed and low-cost SM4 chip[C]//2018 8th International Conference on Applied Sci-ence，Engineering and Technology （ICASET 2018）.Qingdao，China：AtlantisPress，2018：196-202.

[16] Shang M，Zhang Q，Liu Z，et al. An ultra-compact hard-ware implementationof SMS4[C]//2014 IIAI 3rd Inter-national Conference on Advanced Applied Informatics.Kokura，Japan：IEEE，2014：86-90.

[17］梁浩，烏力吉，張向民.基于復合域的SM4算法的設計與實現[J].微電子學與計算機，2015，32（5）：16-20.

[18]Guan Z，Li Y，Shang T，et al. Implementation of SM4 onFPGA： Trade-off analysis between area and speed[C]//2018 IEEE International Conference on Intelligence andSafety for Robotics（ISR）.Shenyang，China：IEEE，2018：192-197.

[19］張宏科，袁浩楠，丁文秀，等.基于FPGA的 SM4 算法高效實現方案[J].通信學報，2024，45（5）：140-150.

[20]許莉，韋，車書玲.FPGA 中嵌入式塊存儲器的 IP軟核設計[J].微電子學，2019，49（4）：524-528.

[21］林曉會，解維坤，宋國棟.基于新型 BIST的LUT測試方法研究[J].現代電子技術，2024，47（4）：23-27.

[22]申懿鑫，韓躍平，唐道光.高層次綜合的 SM4算法硬件實現與優化[J].單片機與嵌入式系統應用，2023，23（8）：11-14.

[23]聶懷昊，韓躍平，李可欣.敏捷開發的SM4算法FPGA實現與優化[J].集成電路與嵌入式系統，2024，24（7）：80-84.

【責任編輯：陳 佳】