基于HRCA的可重構(gòu)SM4密碼算法研究與實現(xiàn)

張驍，周清雷，李斌

（鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001）

1 引言

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

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

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

2 研究背景

2.1 SM4算法原理

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

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

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

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

輪密鑰由加密密鑰通過密鑰擴展算法得到，F(xiàn)K與CK均為固定參數(shù)組，用于密鑰擴展算法。SM4密鑰擴展算法公式如下。

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

2.2 超混合可重構(gòu)計算陣列原理

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

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

3 基于HRCA的可重構(gòu)SM4實現(xiàn)

3.1 基礎(chǔ)算核的提取

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

圖2 HRCA結(jié)構(gòu)Figure 2 HRCA structure

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

令HRCA芯片上總資源為R，基礎(chǔ)算核集表示，其中，bn為算核個數(shù)。CKi所需要資源為ri，則重構(gòu)算核所需要資源即為。算法重構(gòu)時所需要連接資源記為ra。算核CKi被算法調(diào)用時表示為

則算核CKi的利用率為

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

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

表1 SM4主要基礎(chǔ)算核Table 1 Basis computing kernel of SM4

3.2 粗粒度可重構(gòu)單元

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

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

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

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

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

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

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

3.3 SM4算法結(jié)構(gòu)的映射策略

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

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

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

圖4 2合1邏輯結(jié)構(gòu)Figure 4 2 in 1 logical structure

3.3.2 流水線映射

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

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

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

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

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

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

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

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

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

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

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

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

圖7 SM4整體結(jié)構(gòu)Figure 7 Overall structure of SM4

4 實驗與性能對比

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

4.1 資源占用

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

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

4.2 性能對比

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

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

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

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

5 結(jié)束語

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