張驍，周清雷，李斌

（鄭州大學信息工程學院，河南 鄭州 450001）

1 引言

開放的互聯(lián)網環(huán)境必然帶來諸多安全問題，為保證網絡中通信與數據交換的安全性，通常將傳輸的數據進行加密保護。SM4分組密碼算法比國外使用的同類算法具有較高的安全性[1-2]；同時它作為國家密碼管理局發(fā)布的密碼行業(yè)標準，適用于無線局域網和可信計算系統(tǒng)中，主要對具有敏感性的內部信息、行政事務信息、經濟信息等進行加密保護。

目前對SM4分組加密算法方面的研究主要有：文獻[3]提出了“一次一密”的加密機制，主要解決SM4算法加解密使用相同的密鑰并缺乏對密鑰保護的問題，從而提高整個算法的安全性；文獻[4]基于SM4的通用結構，利用混合線性整數規(guī)劃設計出一種較優(yōu)的認證加密算法SAME；文獻[5]結合AES-GCM實現了SM4-GCM方案，通過乒乓操作提高數據處理速度，并驗證了方案具有更高的吞吐量和較低的資源消耗；文獻[6]提出了一種邏輯化簡方法，通過減少算法關鍵路徑上時延，設計出多輪合一的組合邏輯電路減少時延，從而提高SM4算法在CBC模式下的吞吐率；文獻[7]針對SM4-CTR模式進行了優(yōu)化，實現了高吞吐率的ASIC設計。

隨著處理數據量的增大和多種加解密模式的出現，上述方案無法完全滿足大規(guī)模文本、物聯(lián)網、云計算以及視頻流媒體等復雜多變的應用場景對多種加密模式的需求。為了滿足高速的網絡傳輸環(huán)境和密碼行業(yè)標準的要求，本文基于可重構計算提出了適用于超混合可重構計算陣列（HRCA，hybrid reconfigurable computing array）上映射實現的SM4加密算法方案。首先，基于可重構計算思想對SM4算法計算、存儲與通信特征的分析后，實現了粗粒度的可重構計算單元。接著，對SM4進行多種映射展開以適應不同的加密工作模式，并對SM4整體架構進行了優(yōu)化設計，提高了算法的靈活性與可擴展性，在保證高性能與安全性的前提下滿足了不同應用場景的需要。

2 研究背景

2.1 SM4算法原理

SM4迭代分組密碼算法采用非平衡Feistel結構，數據分組長度均為128 bit，加解密算法與密鑰擴展算法均為32輪非線性迭代結構，加密密鑰和解密密鑰相同[8]。SM4算法加密結構與輪密鑰結構如圖1所示。

圖1 SM4分組密碼算法與密鑰擴展算法Figure 1 SM4 block cipher algorithm and key expansion algorithm

SM4算法包含輪函數F、合成置換T、非線性變換τ、線性變換L以及逆序轉換R等函數過程。設明文輸入為，密文輸出為，加密密鑰為，輪密鑰為。SM4算法的解密結構與加密結構相似，但兩者輪密鑰的使用次序不同，加密時輪密鑰使用次序為(rk0,rk1,rk2,…,rk31)；解密時逆序使用輪密鑰。SM4的加密原理描述如下。

其中，T為合成置換，由非線性變換τ和線性變換L復合而成，即T(·)=L(τ(·))。線性變換L由移位操作完成，即；非線性變化τ由S盒擾亂構成，輸入，非線性變換可以描述為

輪密鑰由加密密鑰通過密鑰擴展算法得到，FK與CK均為固定參數組，用于密鑰擴展算法。SM4密鑰擴展算法公式如下。

T′與加密算法輪函數T基本相同，只是線性變換移位長度不同，為

2.2 超混合可重構計算陣列原理

由于研究角度不同，人們對于可重構計算（RC，reconfigurable computing）的定義不盡相同。在1999年ACM國際會議上，由美國加州大學伯克利分?？芍貥嫾夹g研究中心的Dehon等[9]提出的定義是目前比較公認的?？芍貥嬘嬎憬Y構綜合軟件的靈活性和硬件的高效性，利用生產加工后結構上的空間特性優(yōu)化算法，通過對可重構處理單元硬件資源進行編程配置可以實現算法到計算引擎的空間映射，進而可以從時間和空間多維度上對計算任務進行展開。重構粒度是指可重構系統(tǒng)中映射工具所能尋址最小的處理單元數據通路的位寬[9]。依據可重構單元的不同粒度，可重構計算系統(tǒng)可依次分為細粒度、粗粒度和混合粒度可重構計算系統(tǒng)。

HRCA是一種新提出的可重構陣列，能夠以可重構方式支持不同精度和多種聚合單位的變化[10]。HRCA具有應用驅動、非指令執(zhí)行和高度可擴展等特點。其中，應用驅動是指通過對具體應用的分析從算法中提取可共用的基本操作，并形成在硬件上易于實現的基礎算核集，在此基礎上構建各種粒度的可重構單核；非指令執(zhí)行與通用處理器結構對算法的執(zhí)行過程有所區(qū)別，將算法直接映射到硬件結構中實現，即粗細粒度單元在單核內以硬件可重構方式實現算法中的基礎算核集，減少了通用處理器取指譯指的開銷，進而大幅提高執(zhí)行效率；高度可擴展是指核間采用全局異步、核內采用局部同步的互聯(lián)通信方式，可實現以單核為基礎的高度可擴展。HRCA結構如圖2所示，HRCA中可重構單元構成的更大規(guī)模硬件結構Re_Eng形成了可以支持應用算法各子模塊的高階運算棧。對比通用處理器結構，在HRCA中具有一定相似度的基本操作由不同粗粒度的高效可重構計算單元完成，各計算單元間的互聯(lián)結構支持具有并行特點的數據流，使高階運算棧在計算過程執(zhí)行上效率更高，因此通過這些結構可以支持各種應用的核心算法在計算過程中高效實現。

3 基于HRCA的可重構SM4實現

3.1 基礎算核的提取

為滿足高性能可重構計算陣列設計需求，需要對復雜的算法和計算部件進行分析，在一定條件下將復雜計算問題分解成若干簡單的計算，并刻畫出適合的粗粒度計算可復用算核，減少冗余的資源開銷，提高算法的映射效率。統(tǒng)計目前公開文獻中分組密碼算法的基本操作，可以發(fā)現分組算法僅由有限的幾種操作構成[11]。這給算核提取與可重構計算單元的構建提供了便利。

圖2 HRCA結構Figure 2 HRCA structure

作為構建HRCA中關鍵的算核提取過程，在所選算法滿足可重構的前提下，保證提取出的算核在重構過程中被使用概率基本一致，基礎算核集提取過程如下。

令HRCA芯片上總資源為R，基礎算核集表示，其中，bn為算核個數。CKi所需要資源為ri，則重構算核所需要資源即為。算法重構時所需要連接資源記為ra。算核CKi被算法調用時表示為

則算核CKi的利用率為

求解基礎算核集的算法是一個迭代過程，從算法各步驟所需算核集的簡單并集出發(fā)，調整使用算核集合，使算核利用率的方差最小。

根據基礎算核提取過程，在SM4算法中提取出以下基礎算核：S盒的查找表（LUT），以S盒內存放的數值替換相對應的輸入，查找表通過互聯(lián)方式使其他運算單元共享使用；移位操作包含對多種移位位數的處理；邏輯計算主要用于完成對多組相同位寬的輸入數據進行異或運算；比特位操作用于對數據進行拼接和拆分，使數據分組的位寬符合算法要求。SM4算法主要基礎算核如表1所示。

表1 SM4主要基礎算核Table 1 Basis computing kernel of SM4

3.2 粗粒度可重構單元

粗粒度的可重構體系結構主要針對計算密集型應用，一般要求配置的最小數據位寬大于4 bit，可以并行處理大量算數運算。同時，SM4作為分組加密算法具有如下特性：運算類型集中，加解密過程主要通過輪函數運算完成；循環(huán)迭代為主，需要經過32輪完全相同的輪函數運算；密鑰擴展過程與加解密過程結構基本相同且形式固定。因此，在提取相關算核的基礎上，除部分移位操作外，可以對算法中關鍵操作進行重構，使用相似的結構與運算單元來實現算法。本文將SM4算法中每一次輪函數單元計算構建為粗粒度重構運算單元[12]。

粗粒度可重構運算單元作為可重構的適用于HRCA的高階運算棧，包含邏輯功能單元、選擇器、寄存器組、算術邏輯單元和移位異或選擇單元，其基本結構如圖3所示，主要功能如下。

（1）邏輯功能單元：作為控制配置中心負責接收陣列中的配置信息，主要執(zhí)行以下幾個任務。一是控制粗粒度可重構單元待執(zhí)行的運算功能；二是確定片上存儲器和主存儲器之間的運算類型以及數據的流向，通過不同的配置條件確定任務特征及部件狀態(tài)，將任務分配到匹配的部件或子結構上計算；三是允許配置IV寄存器使算法工作在不同的加密模式下。

（2）選擇器：用來處理輸入數據的拆分與拼接，拆分成32位數據字長并輸入算術邏輯單元進行計算。

（3）寄存器組：作為片上陣列中的存儲單元為運算部件提供加密算法所需的系統(tǒng)參量和固定參量，同時存儲一些必要的中間結果。

（4）重構的算術邏輯單元RE_ALU與異或移位單元RE_L：作為依據算法處理流程中提取出的基礎算核所重構而成的邏輯部件，是完成SM4算法運算的主要功能模塊。RE_ALU主要完成32位加減法、邏輯異或運算等基本算術和邏輯操作，并通過查找表的方式對S盒訪問，將計算數據作為SBOX存儲器的地址，并將相應地址中的內容作為輸出，從而在算法中實現數據的替換功能。移位異或選擇單元RE_L和RE_L`在完成基本的邏輯異或操作基礎上分別完成不同位長的移位操作。

粗粒度可重構運算單元的運算周期為一個時鐘，運算單元按照運算步驟劃分算法，確保了多個重構單元可以串行或并行地映射到流水線上，達到提高計算性能和效率的目的?？芍貥媶卧鳛镠RCA中的高階運算棧Re_Eng采用交叉的可重構互聯(lián)結構，充分利用單元件的程序執(zhí)行局部性，提高系統(tǒng)的靈活性與可擴展性。

3.3 SM4算法結構的映射策略

SM4作為分組密碼算法擁有多種工作模式，其中，CBC模式和CTR模式具有較高的安全性[13]。CBC模式中存在數據依賴性，不適于使用流水線并行結構，而CTR模式適合數據分組，不存在依賴性，可并行實現[14-15]。為了同時滿足CBC和CTR等加密模式的SM4分組算法的運行，本文按照不同策略對算法分別進行循環(huán)串行展開映射以及流水線并行展開映射以提高算法在不同工作模式下的處理性能，同時降低對硬件資源的占用。構建的粗粒度可重構計算單元作為算法中的關鍵循環(huán)塊，將運算分配到這些可重構計算單元上進行執(zhí)行。

3.3.1 循環(huán)迭代映射

這種結構下完成一組數據的加解密只需要進行原來輪計算次數的一半，即32次輪計算，則總耗時為32TF+32Treg。這種映射方式中，輪函數在資源和時間上的開銷是整個算法的主要部分，算法運算時間縮短了一半。該映射方案可以應用于實現CBC模式下的SM4加解密運算。

圖4 2合1邏輯結構Figure 4 2 in 1 logical structure

3.3.2 流水線映射

由于HRCA中單元的粗粒度可重構計算單元的獨立性，算法可以映射到多個計算單元進行流水線運算。流水線映射策略主要有兩種：一種是循環(huán)展開的全流水線映射，即將循環(huán)迭代過程分配到不同的計算單元；另一種是基于數據分配的方式，由不同單元獨立承擔完成數據全部的運算任務。全流水展開方案中，將密鑰擴展運算和加解密運算中的輪運算作為主體進行映射，不同的可重構計算單元承擔不同迭代次序的輪運算，同一組數據的處理由多個計算單元共同完成。流水線映射方案主要可以實現CTR模式下的SM4加解密運算。

在循環(huán)展開的全流水映射中，加密過程的流水線分為兩級，分別是密鑰擴展運算流水線和輪函數運算流水線，全流水線映射時空圖如圖5所示。密鑰和明文數據被分配進入不同的流水線進行處理，加解密流水線需要在密鑰擴展流水線完成第一輪計算得到輪密鑰后才可以啟動。流水線從接收到第一組明文和密鑰直至填滿整個流水線需要經過33FT，因此該流水線映射方案時延僅需33個時鐘周期。在同一條流水線中，由不同的運算單元承擔不同迭代次序的運算，中間結果直接由下一級運算單元接力處理，因此不需要寄存器存儲中間結果。這種映射策略在加密過程中具有較好的表現，既減少了存儲中間結果資源消耗也減少了通信消耗。但是，該映射方案在解密過程因為輪密鑰逆序使用需要增加一組寄存器進行存儲，并且需要等待全部輪密鑰計算完成。因此，僅在密鑰更新周期長的情況下具有良好的性能，在密鑰頻繁更換的情況下解密速度和循環(huán)迭代的串行速度一致。

圖5 全流水線映射時空圖Figure 5 Full-pipeline space-time mapping graph

基于數據分配的流水線映射方式，將分組數據直接分配給可重構處理單元，密鑰擴展和加解密在同一條流水線中。加解密運算需在完成所有密鑰擴展運算后才可以開始，因此每條流水線的中間輪密鑰結果都需要使用寄存器進行存儲。流水線從被分配到數據直至整個流水線被填滿需要經過64TF，因此該流水線映射方案的時延為64個時鐘周期。該映射方式的流水線時空圖如圖6所示。相較于全流水線映射策略，基于數據分配的映射策略可以將加解密過程統(tǒng)一在一個策略下，但中間結果需要大量FIFO進行存儲。

圖6 基于數據分配的流水線映射時空圖Figure 6 Data distribution based pipeline mapping space-time graph

具體分析兩種流水線映射方式帶來的性能提高，主要包括以下兩個方面。

基于國家職業(yè)教育資源庫的建設成果，我們將混合式教學方式應用于2017年春季，面向烏魯木齊職業(yè)大學信息管理、計算機網絡及物聯(lián)網應用技術三個專業(yè)學生開授的“Java語言程序設計”課程中，修課學生為118人。課程結合筆者主持的“混合式教學方法在程序設計教學中的實證研究”課題，采用“智慧職教云”平臺輔助教學并進行教學改革嘗試。課程設計將課堂教學與云平臺學習同步。學生自我學習和教師講解異步教學有機結合，為學生提供一個持續(xù)學習的環(huán)境，主要包含建構基于國家職業(yè)教育資源庫的云平臺學習環(huán)境設計、線上線下的課程內容設計、多元互動的學習活動設計以及多維度的學習評價方式等。

（1）流水線的使用可以減少系統(tǒng)運算部件的空閑時間。由于SM4需要經過密鑰擴展流程得到輪密鑰才能進行加密過程，得到一組完整的加解密數據的時延至少是64個周期，其中32個周期用來進行輪密鑰計算，另外32個周期進行加解密過程。這就造成一半的時間主要運算模塊處于等待狀態(tài)。用流水線方法映射SM4算法，可減少運算單元的等待時間，大幅度提高資源利用效率。

（2）減少通信量。如果運算單元按照順序執(zhí)行時，系統(tǒng)需要為這些模塊的數據預留很多空間來存儲中間運算結果，同時在時序上增加了中間數據的存儲與讀取。采用流水線的方式并行處理各個運算單元可以減少中間數據存儲和通信的開銷。

3.4 整體算法優(yōu)化

為了使FPGA芯片滿負荷工作，基于控制算法細化、模塊化和最佳適用性原則，本文按照所選擇硬件架構對整體算法進行設計，主要劃分為控制平面的上層控制和數據平面的核心算子兩部分完成。

SM4整體結構如圖7所示，主要包括控制平面的輪密鑰擴展控制與加解密控制以及數據平面的密鑰擴展模塊與加解密模塊。加解密模塊僅用控制命令確定算法進行加密操作還是解密操作?？刂破矫嫱ㄟ^實例化多個核心算子以及放置多條流水線以增加芯片的利用率，并對各算子進行資源的分配回收與任務的分發(fā)調度，同時可以控制加解密模式，選擇算法運行在串行或流水行結構中。數據平面的核心算子分為密鑰擴展模塊和加解密模塊，這些模塊主要由粗粒度可重構計算單元組成，模塊間可以進行數據傳輸。SM4算法作為計算密集型任務在數據平面通過可重構計算單元高速實現，使管理控制與數據間存在不同的吞吐量和復雜度。因此，通過控制平面與數據平面的分割避免速度差異導致算法整體性能降低。

圖7 SM4整體結構Figure 7 Overall structure of SM4

4 實驗與性能對比

為評估本文提出的粗粒度重構計算單元與多種展開方案并驗證性能與資源開銷，本文使用Verilog HDL硬件描述語言對以上方案進行描述，然后使用XILINX公司的Vivado2018.2進行功能和時序仿真驗證算法功能的正確性，并在FPGA集成加速卡進行實現，芯片型號為XILINX公司的XCKU060。

4.1 資源占用

表2給出了本文各種映射方案的資源開銷情況。從表中可以看出，循環(huán)迭代映射與流水線映射中，流水線并行策略消耗資源多，因為后者為達到可用的流水線級數需要的可重構計算單元較多。在全流水線并行和數據分配并行中，后者每一級流水線都需要寄存器存放中間結果，因此所需資源明顯增多。

表2 不同方案資源開銷情況Table 2 Resources utilization of different schemes

4.2 性能對比

本文在對SM4進行重構的基礎上，通過多種映射策略對算法進行實現。表 3給出了本文所有映射策略的性能。從表中看出，在流水線展開策略有較高的吞吐率，可達到25.6 Gbit/s。

表3 不同方案性能分析Table 3 Performance analysis of different schemes

為了盡可能利用芯片資源，在200 MHz頻率下對循環(huán)迭代映射和流水線映射方案分別實例化了41個SM4算子和20個SM4算子，占用資源分別為82%和80%。為了說明本文基于可重構計算單元進行映射在性能方面的提高，給出了與其他文獻提出的方法的對比情況，如表4所示。

表4 不同文獻性能與資源對比Table 4 Comparison of performance and resources with other references

5 結束語

當前SM4算法的應用主要集中在專用ASIC和CPU這兩種平臺上實現，然而，隨著應用需求的不斷發(fā)展與極速變化，應用使用SM4算法進行身份認證、系統(tǒng)自檢以及數據加密等不同的場景階段所需加密的數據量與工作模式有所不同，上述兩種平臺不能平衡性能與靈活性的需求。針對這些問題，本文基于超混合可重構計算陣列對SM4算法進行了算粒集提取和粗粒度可重構單元的設計，同時對算法按照不同的策略進行了展開，結合FPGA并行性和靈活可編程的特性，通過狀態(tài)機實現減少訪存時間，使算法處理速度進一步提高，兼顧了高性能與靈活性。通過實驗分析了不同映射方案對性能和資源的影響，結果表明，對于CBC模式使用的串行運算和CTR模式使用的流水線運算，本文通過采用重構設計和映射方案，在單算子和多算子情況下對算法的運行效率有不同程度的提高。本文方案可以加快數據的加解密速度，并通過配置可在硬件平臺下實現多模式轉換，在要求算法具備多種加密工作模式的復雜應用場景中具有重要的意義。