SM4算法CBC模式的并行化研究與實現

◆李 莉史國振楊 鳳

（1.西安電子科技大學通信工程學院 西安 710071；2.北京電子科技學院 電子信息工程系 北京 100070）

SM4算法CBC模式的并行化研究與實現

◆李 莉1，2史國振2楊 鳳2

（1.西安電子科技大學通信工程學院 西安 710071；2.北京電子科技學院 電子信息工程系 北京 100070）

本文通過對CBC模式下SM4算法結構的分析，根據密文輸出前的反序變換，提出一種分組間部分并行的設計方案，改善了CBC模式只能串行執行的現狀，并對方案在xc5vllx110t上進行了設計實現，測試結果表明，本方案能夠提高單一多分組任務的CBC執行速度，同時不影響原設計方案對單個分組的執行速度。此方案可以在已有的SM4算法優化的基礎上進行實現，充分發揮多核架構的優勢。

CBC模式；SM4；并行設計

0 引言

信息安全是網絡信息化環境下的必然需求，密碼作為實現數據安全傳輸的基本手段，是信息安全領域不可或缺的環節。在數據密集型應用中，如何對數據進行快速的密碼算法處理，而不影響用戶的應用體驗，始終是密碼算法設計和實現領域關注的目標。隨著單核系統在速度提升上的瓶頸，片上多核系統已成為事實上的芯片發展趨勢，通過多核間的并行操作可以實現密碼算法的快速運算，有效提升數據處理速度。在密碼算法的工作模式中，CBC模式由于其可以隱藏相同明文的優勢，較之其他密碼工作模式更為安全，從而得到廣泛應用。但是CBC模式內在的并行性又限制了其在多核上的并行執行。在多核架構已成為事實存在的當下，有必要進行cbc模式并行化的研究。

1 相關研究

隨著2012年3月國家密碼管理局發布的SM4算法，SM4算法作為國家密碼管理局發布的密碼算法，近年來對其研究越來越多，文獻1根據應用需求，在8bit的智能卡上實現SM4算法；文獻2對SM4進行的功耗分析研究表明SM4算法具有一定的抗差分功耗分析的能力，通過合理的算法設計可以獲得高的側信道安全性。對于SM4算法的優化研究也多集中在縮短關鍵路徑和面積的優化上3,4，通過設計專用的指令集處理器，或者將密鑰擴展通過嵌入式的cpu核實現，來提高算法的速度和靈活性。文獻5通過對算法s盒置換和移位操作的優化，實現了895Mbps的吞吐率。

作為NIST推薦的分組密碼工作模式，CBC密碼模式由于具有隱藏長文件下的相同明文分組的特點，克服了ECB模式的缺陷，而得到廣泛使用。若某業務的數據流包含n個分組數據， CBC密碼模式如下所示：

其中Ci為第i個分組數據的加密結果。CBC密碼模式在對明文進行加密時引入了初始向量IV，并將前一個分組數據的運算結果Ci-1作為后一個分組的IV，從而保證了即使明文分組Pi相同，但是由于分組加密算法加密的是XOR(Ci-1, Pi)，所以密文并不相同。CBC運算模式的這種迭代關系，決定了對于同一個數據文件其加密操作只能是串行的，從而限制了其在多核處理器上的并行執行。

因此對于密碼算法的多核并行執行，多是采用ECB、CTR模式實現。例如文獻6介紹了AES算法ECB模式和CTR模式的高速實現，通過采用全流水線，以及對s盒和乘法逆變器的優化，實現了ECB模式在644.33MHz下的82.4Gbps，CTR模式在508.104 MHz下的260.15 Gbps的吞吐率。目前已有的探討CBC模式并行執行的文獻大多是以任務分片的模式進行，沒有深入進行密碼算法在CBC密碼模式下結構上的探討。文獻7研究了CBC模式下多SM4密碼處理引擎的并行處理機制，提出了CBC模式下多引擎的任務分配機制。此方案通過控制單元將不同的任務送至不同的SM4處理單元上，從而形成了多個任務之間的并行處理，提高了系統的總的吞吐率。但是對于單一任務的處理仍是在一個核上采用串行的方式完成。因此單一任務的處理速度并未得到提高。文獻8通過縮短設計中的關鍵路徑，在算法級將AES算法的中的字節代替變換與列混合變換進行合并，從而實現了AES算法的高速實現，在密鑰長度為128bit時，最高工作頻率可以達到781MHz，從而實現了高達9.9Gbps的吞吐率。雖然實現了高的吞吐率，但是此文獻在CBC模式的實現上仍然是采用串行的方式完成，即同一任務的不同分組之間仍然是采用串行方式完成。文獻9通過采用GCM模式，實現了基于SM4算法的加密與認證功能，設計基于fpga采用全流水線架構實現了22.248Gbps的吞吐率。本論文通過分析CBC模式下SM4算法的特點，提出了同一任務不同分組間的部分并行設計方法，此方法可以在上述提到的SM4算法優化的基礎上進行，測試表明此方法對系統最高工作頻率，以及資源的占用情況影響不大。

2 SM4算法

2.1 輪函數F

SM4算法以128bit為一個分組，采用非線性迭代結構，以字為單位進行加密運算，共進行32次輪變換。設明文輸入為：，密文輸出為：子密鑰為，則：

為了保證加解密的一致性，在32輪變換之后，進行了一次以32bit為單位的反序變換，即：

2.2 輪密鑰

SM4算法中加密算法的輪密鑰由128bit的加密密鑰通過密鑰擴展算法生成。若加密密鑰為：，則輪密鑰的生成過程如下：

3 部分并行

圖1 CBC模式部分并行

4 設計實現

4.1 數據幀格式說明

為了簡化控制時序，實現對數據的正確處理，設計如表1所示的數據幀格式，其中ID表示具體的任務，不同的任務ID號不同；MODE表示運算需求，當MODE=0x1時，表示工作模式為ECB加密，當MODE=0x2時，表示工作模式為ECB解密，當MODE=0x3時，表示工作模式為CBC加密，當MODE=0x4時，表示工作模式為CBC解密；length表示任務包含數據的長度，單位為字節。后面緊跟算法運算的密鑰和初始向量IV，然后是進行運算的數據DATA。

表1 輸入數據結構

4.2 系統架構

本系統采用對稱的SM4 IP核架構設計，整個系統包括輸入解析模塊、密鑰擴展模塊、反饋控制模塊、SM4算法核和輸出模塊。反饋控制模塊通過對數據運行狀態的監控，實現數據在兩個對稱的IP核間的切換，通過兩個IP核間的交叉運行，實現數據的加解密需求的并行處理。本系統支持命令和數據的連續輸入，即只要兩個算法核輸入隊列的fifo_afull信號無效，命令幀可以連續不斷地輸入。系統架構如圖所示：

圖2 CBC并行處理系統架構圖

（1）輸入解析模塊。輸入解析模塊通過對命令幀的解析，實現對密鑰、初始向量IV和運算數據data的提取。將密鑰送入密鑰擴展模塊，實現密鑰的擴展；將IV送入IV寄存器，等待與第一分組數據的異或操作；將同一任務下的數據data分為多個128bit的數據分組，并交叉送入兩個SM4 IP核的入口隊列中。若任務的長度length不足128bit的整數倍，則自動添零補齊，拆分后的分組個數送入任務長度寄存器NUM存儲。通過對MODE的解析，決定輸入SM4算法核的數據來源，在ECB模式下，mode1=0時，SM4入口隊列的數據直接控制輸入SM4算法核；在CBC模式下，mode1=1，SM4入口隊列的數據通過與SM4反饋數據異或后輸入SM4算法核。并產生對應的加/解密控制信號至SM4算法核，其中mode0=1時，表示加密操作，mode0=0時，表示解密操作。

（2）SM4算法核

SM4算法核采用輪迭代的數據結構，圖3所示，為其中一個算法核的內部結構，由異或、非線性變換S、線性移位變換L和反序變換R構成。其中input1來自于反饋控制模塊的輸出，rki為密鑰擴展后產生的輪密鑰，cipherout1為分組數據的運算結果，rdy311、rdy321分別標識第31輪和32輪的運算狀態，當其值為1時，表示此輪運算完成。F_cnt為輪計數器。

圖3 SM4算法核結構圖

加密模塊由8個狀態構成，各狀態下的操作如表2所示：

表2 SM4算法核狀態

本算法核的設計與傳統設計的不同體現在s4狀態和s6狀態上。s4狀態下，不同分組數據在第一輪運算時異或操作的數據不同：

當輪數f_cnt=0時，迭代結果來自于上一分組的運算結果和本次分組運算線性移位結果的異或：，否則來自于自身上一輪的輪運算結果cipherout[127：96]

S6狀態將判斷是否啟動下一個分組和本次分組的下一輪運算并行執行。當輪數f_cnt=30時，rdy31=1，通知反饋控制模塊啟動另一個SM4算法核，并輸出加密完成的96bit數據，供下一分組的第一輪運算。當count=31時，rdy32=1，輸出反序變換后的密文。

（3）反饋控制模塊

反饋控制模塊用于實現數據流入和流出的控制，其內部邏輯結構如圖4所示。其中cipher1、cipher2為兩個算法IP核的輸出，input1和input2為兩個算法IP核的輸入，datain為分組數據輸入端，rdy311、rdy321和rdy312、rdy322分別為兩個算法IP核的第31輪和32輪的運算完成狀態標識。分組計數器P_cnt用于對同一任務的不同分組進行計數，用于決定進入到SM4算法核的數據以及判斷同一任務是否執行完成。當P_cnt=0時，表示128bit的分組數據為任務的第一個分組，在CBC模式下，需要將分組數據datain與IV異或后，送SM4加密模塊；否則，若0＜P_cnt＜num，則分組數據datain需要與前一分組的第31輪或第32輪的運算結果進行異或后送SM4加密模塊進行SM4算法的第一輪和第二輪運算。

圖4 反饋控制模塊邏輯圖

（4）輸出模塊

當任一個SM4算法核的rdy32為1時，表示一個分組運算完成，密文即可輸出。

if rdy321='1' then cipher＜=cipher1;

elsif rdy322='1' then cipher＜=cipher2;

end if;

5 測試

為了驗證設計的正確性，本文在xilinx公司的xc5vllx110t上進行了原型設計，并與已有的SM4實現方案進行了對比。

為了驗證單一業務處理的速度，我們分別對1Kb、10Kb、100Kb、1000Kb的文件在CBC串行和部分并行的方式下，進行了對比測試，在相同的時鐘頻率下，各文件消耗的時鐘數如表3所示，單個任務的平均速度提升為3%。

表3 文件運行時間對比

邏輯資源占用、系統的最高頻率、吞吐率及功耗測試如表4所示。通過對比改進后的部分并行CBC模式，可以發現，改動后的程序的資源占用情況有所減少，功耗影響很小，且系統的最高工作頻率沒有改變。

表4 設計性能對比

?

6 結論

本文提出的分組間部分并行的設計方案，改善了CBC模式只能串行執行的不足，通過部分并行確實能提高數據的處理速度，本方案對算法原先的實現方案改動不大，可以在已有的算法優化的基礎上進行，實現優化后算法核間的并行操作，且適合于多任務數據的處理，即不僅能夠進行單任務SM4-CBC并行處理，也能夠進行多任務SM4-CBC并行處理。但是這種并行設計方式對速度的提升有限，且只針對SM4算法，如何獲得更優的改進方案是以后研究的目標。

[1]Dawei Zhang; Wenrui Ding; Ding Ding, "Fast Implementation of SMS4 Cryptographic Algorithms on Smart Card," in Intelligent Information Hiding and Multimedia Signal Processing, 2008. IIHMSP '08 International Conference on , vol., no., pp.287-290, 15-17 Aug. 2008.

[2]Shuang Qiu; Guoqiang Bai, "Power analysis of a FPGA implementation of SM4," in Computing, Communication and Networking Technologies (ICCCNT), 2014 International Conference on , vol., no., pp.1-6, 11-13 July 2014.

[3]Zhenzhou Li; Feng Li; Zhiping Jia; Lei Ju; Renhai Chen, "The Research and Application of a Specific Instruction Processor for SMS4," in Trust, Security and Privacy in Computing and Communications (TrustCom), 2012 IEEE 11th International Conference on , vol., no., pp.1883-1888, 25-27 June 2012.

[4]Zhang Lei; Li Li; Xianwei Gao; Wang Jianxin, "Design and realization of SMS4 algorithm based on MicroBlaze," in Electronic Measurement & Instruments (ICEMI), 2011 10th International Conference on , vol.1, no., pp.106-109, 16-19 Aug. 2011.

[5]Sklavos, N.; Kitsos, P., "Architectural Optimizations & Hardware Implementations of WLANs Encryption Standard," in New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on , vol., no., pp.1-5, 7-10 May 2012.

[6]An ultra-high throughput and fully pipelined implementation of AES algorithm on FPGA，2015.

[7]李校南,徐巖,戴紫彬. CBC模式下SMS4算法并行化研究[J]. 計算機工程與設計,2013.

[8]劉楠,陳迅,李軍偉. 面向CBC模式的AES高速芯片設計與實現[J]. 電子技術應用,2014.

[9]Meng Zhao; Guochu Shou; Yihong Hu; Zhigang Guo, "High-Speed Architecture Design and Implementation for SMS4-GCM," in Communications and Mobile Computing (CMC), 2011 Third International Conference on , vol., no., pp.15-18, 18-20 April 2011.

[10]王晨光,喬樹山,黑勇. 分組密碼算法SM4的低復雜度實現[J]. 計算機工程,2013.

[11]Yier Jin;Haibin Shen; Rongquan You, "Implementation of SMS4 Block Cipher on FPGA," in Communications and Networking in China, 2006. ChinaCom '06. First International Conference on , vol., no., pp.1-4, 25-27 Oct. 2006.

[12]Sklavos, N.; Kitsos, P., "Architectural Optimizations & Hardware Implementations of WLANs Encryption Standard," in New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on , vol., no., pp.1-5, 7-10 May 2012.