◆李 莉史國(guó)振楊 鳳

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

SM4算法CBC模式的并行化研究與實(shí)現(xiàn)

◆李 莉1，2史國(guó)振2楊 鳳2

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

本文通過(guò)對(duì)CBC模式下SM4算法結(jié)構(gòu)的分析，根據(jù)密文輸出前的反序變換，提出一種分組間部分并行的設(shè)計(jì)方案，改善了CBC模式只能串行執(zhí)行的現(xiàn)狀，并對(duì)方案在xc5vllx110t上進(jìn)行了設(shè)計(jì)實(shí)現(xiàn)，測(cè)試結(jié)果表明，本方案能夠提高單一多分組任務(wù)的CBC執(zhí)行速度，同時(shí)不影響原設(shè)計(jì)方案對(duì)單個(gè)分組的執(zhí)行速度。此方案可以在已有的SM4算法優(yōu)化的基礎(chǔ)上進(jìn)行實(shí)現(xiàn)，充分發(fā)揮多核架構(gòu)的優(yōu)勢(shì)。

CBC模式；SM4；并行設(shè)計(jì)

0 引言

信息安全是網(wǎng)絡(luò)信息化環(huán)境下的必然需求，密碼作為實(shí)現(xiàn)數(shù)據(jù)安全傳輸?shù)幕臼侄?，是信息安全領(lǐng)域不可或缺的環(huán)節(jié)。在數(shù)據(jù)密集型應(yīng)用中，如何對(duì)數(shù)據(jù)進(jìn)行快速的密碼算法處理，而不影響用戶的應(yīng)用體驗(yàn)，始終是密碼算法設(shè)計(jì)和實(shí)現(xiàn)領(lǐng)域關(guān)注的目標(biāo)。隨著單核系統(tǒng)在速度提升上的瓶頸，片上多核系統(tǒng)已成為事實(shí)上的芯片發(fā)展趨勢(shì)，通過(guò)多核間的并行操作可以實(shí)現(xiàn)密碼算法的快速運(yùn)算，有效提升數(shù)據(jù)處理速度。在密碼算法的工作模式中，CBC模式由于其可以隱藏相同明文的優(yōu)勢(shì)，較之其他密碼工作模式更為安全，從而得到廣泛應(yīng)用。但是CBC模式內(nèi)在的并行性又限制了其在多核上的并行執(zhí)行。在多核架構(gòu)已成為事實(shí)存在的當(dāng)下，有必要進(jìn)行cbc模式并行化的研究。

1 相關(guān)研究

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

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

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

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

2 SM4算法

2.1 輪函數(shù)F

SM4算法以128bit為一個(gè)分組，采用非線性迭代結(jié)構(gòu)，以字為單位進(jìn)行加密運(yùn)算，共進(jìn)行32次輪變換。設(shè)明文輸入為：，密文輸出為：子密鑰為，則：

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

2.2 輪密鑰

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

3 部分并行

圖1 CBC模式部分并行

4 設(shè)計(jì)實(shí)現(xiàn)

4.1 數(shù)據(jù)幀格式說(shuō)明

為了簡(jiǎn)化控制時(shí)序，實(shí)現(xiàn)對(duì)數(shù)據(jù)的正確處理，設(shè)計(jì)如表1所示的數(shù)據(jù)幀格式，其中ID表示具體的任務(wù)，不同的任務(wù)ID號(hào)不同；MODE表示運(yùn)算需求，當(dāng)MODE=0x1時(shí)，表示工作模式為ECB加密，當(dāng)MODE=0x2時(shí)，表示工作模式為ECB解密，當(dāng)MODE=0x3時(shí)，表示工作模式為CBC加密，當(dāng)MODE=0x4時(shí)，表示工作模式為CBC解密；length表示任務(wù)包含數(shù)據(jù)的長(zhǎng)度，單位為字節(jié)。后面緊跟算法運(yùn)算的密鑰和初始向量IV，然后是進(jìn)行運(yùn)算的數(shù)據(jù)DATA。

表1 輸入數(shù)據(jù)結(jié)構(gòu)

4.2 系統(tǒng)架構(gòu)

本系統(tǒng)采用對(duì)稱的SM4 IP核架構(gòu)設(shè)計(jì)，整個(gè)系統(tǒng)包括輸入解析模塊、密鑰擴(kuò)展模塊、反饋控制模塊、SM4算法核和輸出模塊。反饋控制模塊通過(guò)對(duì)數(shù)據(jù)運(yùn)行狀態(tài)的監(jiān)控，實(shí)現(xiàn)數(shù)據(jù)在兩個(gè)對(duì)稱的IP核間的切換，通過(guò)兩個(gè)IP核間的交叉運(yùn)行，實(shí)現(xiàn)數(shù)據(jù)的加解密需求的并行處理。本系統(tǒng)支持命令和數(shù)據(jù)的連續(xù)輸入，即只要兩個(gè)算法核輸入隊(duì)列的fifo_afull信號(hào)無(wú)效，命令幀可以連續(xù)不斷地輸入。系統(tǒng)架構(gòu)如圖所示：

圖2 CBC并行處理系統(tǒng)架構(gòu)圖

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

（2）SM4算法核

SM4算法核采用輪迭代的數(shù)據(jù)結(jié)構(gòu)，圖3所示，為其中一個(gè)算法核的內(nèi)部結(jié)構(gòu)，由異或、非線性變換S、線性移位變換L和反序變換R構(gòu)成。其中input1來(lái)自于反饋控制模塊的輸出，rki為密鑰擴(kuò)展后產(chǎn)生的輪密鑰，cipherout1為分組數(shù)據(jù)的運(yùn)算結(jié)果，rdy311、rdy321分別標(biāo)識(shí)第31輪和32輪的運(yùn)算狀態(tài)，當(dāng)其值為1時(shí)，表示此輪運(yùn)算完成。F_cnt為輪計(jì)數(shù)器。

圖3 SM4算法核結(jié)構(gòu)圖

加密模塊由8個(gè)狀態(tài)構(gòu)成，各狀態(tài)下的操作如表2所示：

表2 SM4算法核狀態(tài)

本算法核的設(shè)計(jì)與傳統(tǒng)設(shè)計(jì)的不同體現(xiàn)在s4狀態(tài)和s6狀態(tài)上。s4狀態(tài)下，不同分組數(shù)據(jù)在第一輪運(yùn)算時(shí)異或操作的數(shù)據(jù)不同：

當(dāng)輪數(shù)f_cnt=0時(shí)，迭代結(jié)果來(lái)自于上一分組的運(yùn)算結(jié)果和本次分組運(yùn)算線性移位結(jié)果的異或：，否則來(lái)自于自身上一輪的輪運(yùn)算結(jié)果cipherout[127：96]

S6狀態(tài)將判斷是否啟動(dòng)下一個(gè)分組和本次分組的下一輪運(yùn)算并行執(zhí)行。當(dāng)輪數(shù)f_cnt=30時(shí)，rdy31=1，通知反饋控制模塊啟動(dòng)另一個(gè)SM4算法核，并輸出加密完成的96bit數(shù)據(jù)，供下一分組的第一輪運(yùn)算。當(dāng)count=31時(shí)，rdy32=1，輸出反序變換后的密文。

（3）反饋控制模塊

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

圖4 反饋控制模塊邏輯圖

（4）輸出模塊

當(dāng)任一個(gè)SM4算法核的rdy32為1時(shí)，表示一個(gè)分組運(yùn)算完成，密文即可輸出。

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

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

end if;

5 測(cè)試

為了驗(yàn)證設(shè)計(jì)的正確性，本文在xilinx公司的xc5vllx110t上進(jìn)行了原型設(shè)計(jì)，并與已有的SM4實(shí)現(xiàn)方案進(jìn)行了對(duì)比。

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

表3 文件運(yùn)行時(shí)間對(duì)比

邏輯資源占用、系統(tǒng)的最高頻率、吞吐率及功耗測(cè)試如表4所示。通過(guò)對(duì)比改進(jìn)后的部分并行CBC模式，可以發(fā)現(xiàn)，改動(dòng)后的程序的資源占用情況有所減少，功耗影響很小，且系統(tǒng)的最高工作頻率沒(méi)有改變。

表4 設(shè)計(jì)性能對(duì)比

?

6 結(jié)論

本文提出的分組間部分并行的設(shè)計(jì)方案，改善了CBC模式只能串行執(zhí)行的不足，通過(guò)部分并行確實(shí)能提高數(shù)據(jù)的處理速度，本方案對(duì)算法原先的實(shí)現(xiàn)方案改動(dòng)不大，可以在已有的算法優(yōu)化的基礎(chǔ)上進(jìn)行，實(shí)現(xiàn)優(yōu)化后算法核間的并行操作，且適合于多任務(wù)數(shù)據(jù)的處理，即不僅能夠進(jìn)行單任務(wù)SM4-CBC并行處理，也能夠進(jìn)行多任務(wù)SM4-CBC并行處理。但是這種并行設(shè)計(jì)方式對(duì)速度的提升有限，且只針對(duì)SM4算法，如何獲得更優(yōu)的改進(jìn)方案是以后研究的目標(biāo)。

[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]. 計(jì)算機(jī)工程與設(shè)計(jì),2013.

[8]劉楠,陳迅,李軍偉. 面向CBC模式的AES高速芯片設(shè)計(jì)與實(shí)現(xiàn)[J]. 電子技術(shù)應(yīng)用,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的低復(fù)雜度實(shí)現(xiàn)[J]. 計(jì)算機(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.