SM4算法的FPGA優化實現方法

何詩洋，李 暉，李鳳華，3

(1.西安電子科技大學 大數據安全教育部工程研究中心，陜西 西安 710071；2.西安電子科技大學 網絡與信息安全學院，陜西 西安 710126；3.中國科學院 信息工程研究所，北京 100093)

隨著人類社會的高速發展，信息交互和數據生成總量呈井噴式增長；由此所帶來的隱私泄漏、消息竊聽和內容篡改等問題層出不窮，這些問題已經嚴重影響到社會公共秩序，甚至威脅國家安全。因此，信息安全已經成為人們關注的焦點。

數據加密是保證信息安全的重要手段之一，當前，主流加密算法主要分為對稱密碼算法和非對稱密碼算法。與非對稱密碼算法相比，對稱密碼算法具有簡潔高效、部署容易、加/解密速度快等優勢，被廣泛應用于數據加密場景中。

在對稱密碼算法中，數據加密標準(Data Encryption Standard，DES)是目前全世界使用最為廣泛的對稱密碼算法，它于1977年被正式批準作為美國聯邦信息處理標準，隨后該密碼算法被廣泛應用于軍事、政治、商業等各個領域中。由于DES對稱密碼算法的密鑰長度較短(僅為56 bit)，隨著人類計算能力的不斷增強，該算法的安全性受到了極大威脅，美國國家保密局(National Security Agency，NSA)宣布，1998年后不再批準DES為聯邦標準。2001年，美國批準使用新的對稱加密算法高級加密標準(Advanced Encryption Standard，AES)替代DES，相較于DES，AES具有更長的密鑰長度(128/192/256 bit)和更快的加/解密速度[1-2]。

2006年1月，在國家密碼管理局發布無線局域網產品密碼事宜公告中，SMS4密碼算法成為中國首個被批準應用于無線局域網產品的對稱密碼算法[3]。2012年3月，在《祖沖之序列密碼算法》等6項密碼行業標準公告中，國家密碼局批準《SM4分組密碼算法》(原《SMS4分組密碼算法》)為行業標準[4]。

與其他對稱密碼算法相比，SM4密碼算法具有以下主要優勢：① 安全性強。常用的對稱密碼算法(如DES)核心模塊(S盒)的設計準則到目前還沒有完全公開，是否留有陷門還無法得到證實[1]，而SM4密碼算法是由中國密碼學家呂述望等[5]設計完成并獲國家密碼管理局批準的密碼算法，與其他對稱密碼算法相比，安全性能夠得到保障；② 效率高。在算法結構方面，輪密鑰生成算法和加密算法結構相似；在算法加/解密流程方面，加/解密運算方法一致，只是輪密鑰使用順序相反；在算法計算方面，只包含異或、位移、置換等簡單運算；③ 易于硬件實現。SM4的算法結構能夠與FPGA器件的并行性、靈活性等特點充分結合，既能夠采用循環型架構在資源受限的硬件設備中高效實現，又能夠采用流水線型架構在資源豐富的硬件設備中高速實現。

現場可編程邏輯門陣列(Field Programmable Gate Array，FPGA)是一種可編程半定制電路，它比專用集成電路(Application Specific Integrated Circuit，ASIC)更加靈活，主要由可編程邏輯功能塊、可編程輸入/輸出塊、可編程內部互聯資源等組成。FPGA具有可重復編程、靈活性、并行性、低功耗等眾多優良特性，并被廣泛應用于密碼算法實現、圖像處理、信號處理等眾多領域。

SM4密碼算法不僅易于硬件實現，而且能夠充分利用硬件的特有優勢提升效率或提高性能。在硬件實現SM4密碼算法中，有很多學者進行了詳細的研究和分析。具體實現架構主要分為兩類：① 基于循環的電路架構，需要約32個時鐘循環完成一次加/解密。該方案能夠最大程度地節省硬件資源，適合部署在資源受限的設備上；② 基于流水線的電路架構，在電子密碼本模式(Electronic Code Book mode，ECB)下，僅需1個時鐘循環即可完成一次加解/密。它的優勢是吞吐量大，能夠達到20 Gb/s以上，但是資源消耗巨大，適合部署在資源豐富的設備上。

GAO等[6]提出SM4密碼算法硬件實現的循環型(rolling)和非循環型(unrolling)架構。在整體架構中，加/解密使用同一套電路實現，輪密鑰生成后存儲在寄存器中隨時取用，避免重復計算，在Straitx II FPGA平臺上實現，循環型架構吞吐量可達約0.54 Gb/s，資源消耗為1 552個自適應邏輯模塊(Adaptive Logic Module，ALM)，非循環型架構吞吐量可達20.74 Gb/s，資源消耗為8 373個ALM。JIN等[7]提出折疊(folded)型和流水線(pipelined)型SM4硬件實現架構，在Virtex-4 FPGA平臺上實現。折疊型硬件架構每36個時鐘循環完成一次分組加密，其中4個時鐘循環用于緩存，32個時鐘循環用于計算，共消耗380個邏輯單元(SLICE)和4個塊隨機存取存儲器(Block Random Access Memory，BRAM)，加密吞吐量達0.74 Gb/s，流水線型硬件架構消耗9 500個SLICE，吞吐量可達24.32 Gb/s。隨后，YAN等[8]基于超大規模集成電路(Very Large Scale Integration，VLSI)平臺設計實現SM4算法折疊型硬件架構，在0.13 μm CMOS技術下消耗22 000個門電路，加密吞吐量能夠達到800 Mb/s。在前人的工作基礎之上，GUAN等[9]考慮在性能和資源方面進行權衡，提出了包括Resource-first、Balance-4、Balance-8、Balance-16、Speed-first等5種實現架構方案，并針對不同架構進行了設計優化。其中Resource-first架構采用Moore型狀態機控制整個迭代加/解密計算，密鑰生成和加密操作同時進行；Speed-first架構采用32輪流水線迭代，在每層迭代電路間插入32 bit的寄存器保證流水線結構。在Straitx IV FPGA平臺上實現，Resource-first架構消耗687個查找表(Look Up Table，LUT)和448個觸發器(Flip Flop，FF)，每33個時鐘循環完成一次加/解密，吞吐量可約達0.82 Gb/s，Speed-first架構消耗7 667個LUT和5 438個FF，每1個時鐘循環完成一次加/解密，吞吐量可約達27.153 Gb/s。ZHAO等[10]考慮采用軟硬件結合的方式實現SM4密碼算法，輪密鑰生成與加密計算分開進行，使用主機完成32個輪密鑰的計算，使用FPGA完成加密操作。在加密模塊中，作者創新性的提出雙層蝶形架構，將32輪迭代循環從32個時鐘循環消耗壓縮為16個時鐘循環消耗，大幅度提升加密效率，作者在Kintex UltraScale平臺上實現該架構，共消耗1 365個LUT和1 351個FF，吞吐量可達1.9 Gb/s。

SM4密碼算法作為國家密碼局批準的對稱密碼算法具有安全性強、效率高和易于硬件實現等特點，在數據加密方面受到了廣泛的關注。但是在面對不同應用場景下，SM4算法的高效實現和部署還有進一步提升和優化的空間。文中面向資源節約型優化、資源平衡型優化和加密性能型優化等3個方面，提出并設計了1種循環型硬件架構和3種流水線型硬件架構。在循環型架構設計方面，硬件架構中輪密鑰生成模塊和加密模塊并行執行，既提升了加密效率，同時又將新鮮的輪密鑰直接用于加密，無需設計額外寄存器存儲輪密鑰，能夠節省大量寄存器消耗；與當前先進的硬件架構相比，性能提升，且資源消耗下降明顯。該架構拓寬了在資源受限場景下(如移動終端設備、物聯網設備等)SM4算法的部署和應用。在流水線型架構方面，文中提出基于LUT、BRAM、BRAM+REGISTER等3種架構，在BRAM流水線型架構中，文中以消耗33個BRAM的代價，將LUT的消耗量降低為原來的約30%，進一步平衡了硬件資源使用，提高了資源利用率，使SM4算法能夠部署在更多硬件平臺上，進一步拓寬了SM4算法部署的廣泛性。在BRAM+REGISTER流水線型架構中，進一步優化關鍵路徑，提高運行頻率，使加密吞吐量達到42.10 Gb/s，解決了在加密性能要求較高的場景(如云服務器、大數據加密等)下，SM4算法的高效應用和部署問題。

1 SM4密碼算法原理

SM4算法是一個分組加密算法，消息分組和密鑰長度均為128 bit，主要包括密鑰擴展算法、加密算法和解密算法。算法采用32輪非線性迭代結構，加密和解密算法結構相同，只是輪密鑰使用順序相反。

1.1 SM4中的主要參數和術語

文中所用的符號說明見表1。

表1 符號說明

(1) 輪函數F。

輸出：F(X0，X1，X2，X3，rk)=X0⊕T(X1⊕X2⊕X3⊕rk)。

(2) 非線性變換τ。

輸出：τ(A)=(Sbox(a0)，Sbox(a1)，Sbox(a2)，Sbox(a3))。

(3) 線性變換L。

輸出：L(B)=B⊕(B<<<2)⊕(B<<<10)⊕(B<<<18)⊕(B<<<24)。

(4)線性變換L′。

輸出：L′(B)=B⊕(B<<<13)⊕(B<<<23)。

圖1所示為S盒的結構圖。

圖1 S盒結構

1.2 SM4中的主要算法

(1) 加/解密算法。

①Xi+4=F(Xi，Xi+1，Xi+2，Xi+3，rki)=Xi⊕T(Xi+1⊕Xi+2⊕Xi+3⊕rki)，i=0，1，…，31，連續迭代32輪。

② (Y0，Y1，Y2，Y3)=R(X32，X33，X34，X35)=(X35，X34，X33，X32)，將迭代結果順序進行翻轉，得到加密密文。

解密算法與加密算法過程相同，輪密鑰的使用順序相反，為(rk31，rk30，…，rk0)。

(2) 密鑰擴展算法。

輸出：輪密鑰rki，i=0，1，…，31。

① (K0，K1，K2，K3)=(MK0⊕FK0，MK1⊕FK1，MK2⊕FK2，MK3⊕FK3)。

②rki=Ki+4=Ki⊕T′(Ki+1⊕Ki+2⊕Ki+3⊕CKi)，進行32輪迭代運算，得出32個輪密鑰。

2 SM4密碼算法的硬件實現

針對SM4密碼算法的硬件設計，分為循環架構和流水線架構兩種。循環架構面向資源節約優化，使SM4密碼算法能夠輕易部署在資源受限的硬件設備上；流水線架構面向加密性能優化，分別采用基于LUT、BRAM、BRAM+REGISTER的架構設計，使SM4密碼算法能夠部署在對吞吐量要求較高的場景中。

2.1 面向資源節約優化的循環硬件架構

循環硬件架構主要由控制模塊、輪密鑰生成模塊、加密模塊等3個模塊組成。整體架構如圖2所示。該設計架構在控制模塊的協調下，輪密鑰生成模塊與加密模塊并行執行，能夠帶來多種優勢。首先，輪密鑰生成模塊產生的新鮮輪密鑰直接傳遞給加密模塊進行迭代計算，不需要使用額外的寄存器來存儲輪密鑰，大約能夠節省32×32=1 024個FF；其次，兩個模塊并行執行，當密鑰更新時，輪密鑰生成模塊可以實時計算最新的輪密鑰，加密模塊無需等待，整個加密過程能夠連續進行；最后，輪密鑰生成模塊和加密模塊在整個分組數據加密過程中所需要的時鐘循環為常數，能夠有效抵抗側信道攻擊。該設計架構完成1次分組數據加密需要輪密鑰生成模塊和加密模塊循環執行32次，加密模塊比密鑰生成模塊晚啟動1個時鐘循環，完成1組數據加密共需32個時鐘循環。

圖2 循環型架構

控制模塊主要由計數器和Moore型狀態機構成，負責根據輸入密鑰、待加密數據和控制信號等，生成round_rk和round_enc信號控制輪密鑰生成模塊和加密模塊，進行32輪迭代加密計算。

輪密鑰生成模塊主要由S盒模塊、CK參數模塊、多路選擇器、異或電路和寄存器等構成。架構如圖3所示，其中S盒使用4個并行的LUT組合邏輯實現，能夠進一步簡化電路，減少資源消耗；CK參數模塊同樣采用LUT組合邏輯實現。在控制模塊round_rk信號控制調節下，輪密鑰生成模塊每個時鐘循環完成一次迭代運算，生成當前的輪密鑰rki，并傳遞給加密模塊，用于下一步加密計算。

圖3 循環型輪密鑰生成模塊架構

加密模塊與輪密鑰生成模塊類似，主要由S盒模塊、多路選擇器、異或電路、寄存器等構成。架構如圖4所示，S盒使用4個并行的LUT組合邏輯實現，能夠進一步簡化電路，減少資源消耗。在輪密鑰生成模塊的輸出信號rki和控制模塊round_enc信號控制調節下，加密模塊每個時鐘循環完成一次迭代運算，32輪迭代運算后輸出密文。

圖4 循環型加密模塊架構

2.2 面向性能優化的流水線硬件架構

流水線硬件架構主要由控制模塊、輪密鑰生成模塊和流水線加密模塊構成。整體架構如圖5所示。

與循環硬件架構不同，并行流水線硬件架構面向性能優化，主要體現在：① 增加了輪密鑰寄存器，輪密鑰生成模塊將32輪輪密鑰存儲在寄存器中，每個時鐘循環都可以向加密模塊輸入當前輪密鑰，保證流水線加密不間斷；② 流水線加密模塊實例化32套迭代加密電路，每套迭代電路間插入寄存器以保證加密過程流水線運行；③ 在S盒電路設計方面，文中采取3種方案。第1種是基于LUT的設計架構，第2種是基于BRAM的設計架構，第3種是基于BRAM+REGISTER的設計架構。第2種設計架構能夠在BRAM用量增加不多且性能相差不大的前提下，大幅度降低LUT資源的使用。第3種設計架構采用帶有輸出寄存器的BRAM，同時對加密模塊進行少許優化，在增加部分寄存器和32個額外時鐘時延的代價下，能夠約減關鍵路徑，提高運行頻率，進一步提高性能。由于采用流水線架構，在等待32(64)個時鐘時延后，每個時鐘循環即可完成一次分組數據加密，加密速度快，吞吐量大。

圖5 流水線型架構

控制模塊主要由計數器和Moore型狀態機構成，負責根據輸入密鑰、待加密數據和控制信號等，生成round和valid信號，控制輪密鑰生成模塊進行32輪迭代加密計算并存入寄存器，間接控制流水線加密模塊啟動數據加密。

輪密鑰生成模塊和加密模塊整體架構與循環型中兩模塊架構類似，主要不同在于S盒的設計。文中采用3種設計方法并在論文后半部分進行對比。第1種是基于LUT的設計，該方案與循環型架構中S盒的設計思路一致，均采用組合邏輯設計；第2種是基于BRAM的設計，該方案中，輪密鑰生成模塊和加密模塊整體架構如圖6和圖7所示，通過引入雙口BRAM資源，在增加33個BRAM資源消耗的代價下，能夠直接減少32×4=128套S盒的LUT使用，進一步平衡資源利用；第3種是基于BRAM+REGISTER的設計，該方案總體架構與第2種類似，不同之處在于選取帶有輸出寄存器的雙口BRAM，順勢將加密模塊外的寄存器巧妙地插入模塊中，不僅能夠確保流水線系統的正常運行，而且可以進一步縮短關鍵路徑，極大提高運行頻率，但代價是增加部分寄存器消耗和增加32個時鐘時延。

圖6 流水線型輪密鑰生成模塊架構

圖7 流水線型加密模塊架構

3 性能分析和比較

針對SM4密碼算法設計和優化了循環型、LUT流水線型、BRAM流水線型和BRAM+REGISTER流水線型等4種硬件架構。并在XILINX KINTEX-7 XC7K325TFFG 900上實現，設計電路經過綜合布局布線后，資源消耗和性能詳見表2。

方案中的循環型架構設計主要采用1套輪密鑰生成電路、1套加密電路和控制電路構成，整個架構消耗193個SLICE，運行頻率約為333 MHz，吞吐量能夠達到1.27 Gb/s，適用于對吞吐量要求不高且資源受限的場景。與先前學者提出的循環型方案相比(詳見表3)，該架構方案在資源消耗和吞吐量方面優勢明顯。首先，文中方案加密模塊無需等待所有32個輪密鑰生成后再啟動，而是在輪密鑰生成模塊開始一個時鐘循環后即啟動加密，兩個模塊幾乎并行執行，極大地提升了運行效率。與其他方案相比，吞吐量提升約54.9%；其次，文中方案中，輪密鑰生成模塊生成的當前輪密鑰直接傳遞給加密模塊進行加密。與其他方案相比，輪密鑰無需儲存，避免大量寄存器使用，能夠節省約40.2%的FF消耗；最后，文中方案中，輪密鑰生成和加密運行時鐘循環消耗為常數，能夠有效抵抗側信道攻擊。

表2 資源消耗和性能表現

表3 循環型架構資源消耗和性能對比

文中方案中的流水線型硬件架構主要采用1套輪密鑰生成電路、32套加密電路和控制電路構成。在S盒的設計方面，采用基于LUT的設計方法和基于BRAM的設計方法。LUT流水線型架構共消耗7 466個LUT和5 158個FF，吞吐量為30.52 Gb/s。BRAM流水線型架構共消耗2 261個LUT、4 945個FF和33個BRAM，吞吐量為27.74 Gb/s，與LUT流水線型架構、GAO等[6]、JIN等[7]和GUAN等[9]架構相比，BRAM流水線型架構在吞吐量差別不大的前提下，以增加33個BRAM消耗為代價，大幅度節約了LUT資源，如將LUT消耗降低為LUT流水線型架構的約30%(減少5 205個LUT)，平衡了硬件資源使用，提高了資源利用率。

在BRAM流水線型架構的基礎上，文中進一步優化電路結構，提出BRAM+REGISTER流水線型架構，采用帶有輸出寄存器的BRAM，并在流水線加密模塊架構中插入寄存器以保證流水線結構。與表4中其他方案相比，此方案極大地簡約了關鍵路徑，運行頻率與原BRAM型流水線型架構相比，提升約51.5%，加密吞吐量可達42.10 Gb/s。但是由于電路中插入部分寄存器，增加了2 791個FF的消耗和32個時鐘循環時延。

表4 流水線型架構資源消耗和性能對比

4 結束語

針對不同應用場景，筆者提出4種SM4密碼算法硬件機構設計，包括面向資源優化的循環型架構和面向性能優化的流水線型架構。這4種硬件架構均在XILINX KINTEX-7 XC7K325TFFG900上實現。在循環型架構設計方面，文中方案輪密鑰生成模塊與加密模塊幾乎并行執行，寄存器資源節約明顯；在流水線型架構設計方面，文中方案采用基于LUT、BRAM、BRAM+REGISTER的設計方案，不論是在資源消耗、權衡資源使用、性能等方面，對比先前學者提出的方案，都具有較為明顯的優勢。