可重構(gòu)分組密碼協(xié)處理器二維指令架構(gòu)

戴樂育，楊天池，郭　松，王家琰

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

0　引　言

現(xiàn)階段，可重構(gòu)分組密碼協(xié)處理器通過采用VLIW的4路并行處理架構(gòu)，提升了協(xié)處理器的指令并行度和密碼處理性能，但是為了能夠適配更多分組密碼算法，可重構(gòu)分組密碼寫出來由于功能單元數(shù)量、種類不斷增加，配置結(jié)存器數(shù)量不斷擴(kuò)充，導(dǎo)致協(xié)處理器的功耗與面積不斷增加。不斷增加的協(xié)處理器指令負(fù)載已經(jīng)嚴(yán)重限制了可重構(gòu)分組密碼協(xié)處理器的推廣應(yīng)用。研究如何進(jìn)一步提升可重構(gòu)分組密碼協(xié)處理器的指令并行度已經(jīng)成為提升協(xié)處理器密碼性能的亟待解決的問題。為了能夠進(jìn)一步提高可重構(gòu)分組密碼協(xié)處理器的密碼處理性能，國內(nèi)外學(xué)者主要的思路：通過增加運(yùn)算核心數(shù)量來提升可重構(gòu)密碼協(xié)處理器的密碼處理性能。

一類是通過直接增加可重構(gòu)分組密碼協(xié)處理器的運(yùn)算核心數(shù)量來提高協(xié)處理器的密碼處理性能和指令并行度。馮曉等建立了基于Amdahl定律擴(kuò)展的多核密碼處理器性能模型[1]，對多核密碼處理器設(shè)計(jì)提供了理論支持和有效建議，杜怡然等、陳曉鋼等分別對多核密碼處理器的片上網(wǎng)絡(luò)互連結(jié)構(gòu)[2]和數(shù)據(jù)緩存機(jī)制[3]進(jìn)行了研究，在提升多核密碼處理器數(shù)據(jù)交互、數(shù)據(jù)緩存的效率。然而雖然在增加可重構(gòu)分組密碼協(xié)處理器的運(yùn)算核心的情況下能夠一定程度地提高密碼處理性能和指令并行度，由于存在數(shù)據(jù)分配、核間通信等問題導(dǎo)致數(shù)據(jù)運(yùn)算的延遲，協(xié)處理器的性能提升并不是線性提升，然而協(xié)處理器面積和功耗的提升卻是顯著地。

另一類是先拆分可重構(gòu)功能單元，再增加運(yùn)算核心數(shù)量，提高指令并行度和密碼處理性能。如高性能眾核密碼算法協(xié)處理器[4]通過提高運(yùn)算核心數(shù)量、減少每個(gè)協(xié)處理器功能單元個(gè)數(shù)提高協(xié)處理器的能效。該方法雖然有效地提高了指令并行度，但是由于處理核心眾多，數(shù)據(jù)分配、核間通信更加復(fù)雜從而導(dǎo)致密碼算法編程、映射非常困難，制約可重構(gòu)密碼協(xié)處理器的推廣應(yīng)用。

為了能夠進(jìn)一步提升可重構(gòu)分組密碼協(xié)處理器的指令并行度和密碼處理能力，深入優(yōu)化性能與功耗、面積之間的矛盾，本文深入研究分析了分組密碼算法運(yùn)算特征和可重構(gòu)分組密碼協(xié)處理器運(yùn)算指令結(jié)構(gòu)特征，提出了可重構(gòu)分組密碼協(xié)處理器二維指令架構(gòu)和可重構(gòu)分組密碼協(xié)處理器架構(gòu)，通過提高協(xié)處理器指令并行度的方式降低協(xié)處理器指令負(fù)載，并研究了指令的執(zhí)行方式和并行處理模式。

1　分組密碼指令結(jié)構(gòu)特征

根據(jù)可重構(gòu)分組密碼處理器的特點(diǎn)，本節(jié)主要分析了分組密碼算法的特征和超長指令字處理架構(gòu)的分組密碼協(xié)處理器的指令執(zhí)行特點(diǎn)。

1.1　分組密碼運(yùn)算特征分析

為了能夠進(jìn)一步分析分組密碼運(yùn)算的可并行處理特性，分析了分組密碼算法DES、IDEA、AES、MESH[7]、ARIA[8]、FOX[9]、PP-2[10]等分組密碼算法，通過分析上述分組密碼算法，發(fā)現(xiàn)分組密碼運(yùn)算具有以下特征：

(1)迭代運(yùn)算特性

分組密碼算法是通過弱密碼函數(shù)多次反復(fù)迭代產(chǎn)生的密碼算法[11]，如AES就是通過10輪迭代運(yùn)算實(shí)現(xiàn)的密碼算法。

(2)相鄰的兩個(gè)復(fù)雜運(yùn)算操作不同

目前，分析的分組密碼運(yùn)算操作有S盒、比特置換、有限域乘法、移位、模乘、模加等復(fù)雜運(yùn)算操作和“與”、“異或”、“非”等簡單運(yùn)算操作，通過對上述13種分組密碼算法分析發(fā)現(xiàn)，分組密碼算法運(yùn)算過程中連續(xù)的兩個(gè)復(fù)雜運(yùn)算操作大多都是不同的。

利用上述兩種特性，倘若能夠一次性驅(qū)動(dòng)若干運(yùn)算操作或一次迭代運(yùn)算，而兩個(gè)或多個(gè)分組的第一次運(yùn)算操作能夠相繼驅(qū)動(dòng)，那么就會(huì)出現(xiàn)若干個(gè)不同的功能單元在同一時(shí)鐘周期內(nèi)同時(shí)進(jìn)行運(yùn)算，如圖1所示。

圖1　若干分組相繼進(jìn)行運(yùn)算

1.2　運(yùn)算指令結(jié)構(gòu)特征

可重構(gòu)分組密碼協(xié)處理器的工作模式是通過運(yùn)算指令控制數(shù)據(jù)流和可重構(gòu)密碼運(yùn)算單元，完成相應(yīng)密碼運(yùn)算操作，通過多條指令組合實(shí)現(xiàn)密碼算法。

傳統(tǒng)可重構(gòu)分組密碼協(xié)處理器采用了超長指令字架構(gòu)的指令結(jié)構(gòu)[12]，能夠?qū)崿F(xiàn)的4條32位操作指令并行控制4次32位密碼運(yùn)算，如圖2(a)所示，或者4條32位操作指令組合共同控制1次128位密碼運(yùn)算，如圖2(b)所示。因此基于超長指令字的可重構(gòu)分組密碼協(xié)處理器具有并行處理能力強(qiáng)、運(yùn)算位寬大等特點(diǎn)。但是超長指令字的指令執(zhí)行模式采用了取指、譯碼/取數(shù)、執(zhí)行/回寫的三級流水線形式，其中執(zhí)行僅占單獨(dú)的時(shí)鐘周期即一個(gè)運(yùn)算指令僅能支持驅(qū)動(dòng)一個(gè)可重構(gòu)密碼運(yùn)算單元完成運(yùn)算，并不具備完成上述的一次性驅(qū)動(dòng)若干運(yùn)算操作的能力，更不能具備同時(shí)驅(qū)動(dòng)同一個(gè)運(yùn)算通路中兩個(gè)不同可重構(gòu)功能單元的能力。

圖2　可重構(gòu)分組密碼協(xié)處理器指令執(zhí)行結(jié)構(gòu)

鑒于此，通過調(diào)整指令執(zhí)行的方式，使得協(xié)處理器能夠?qū)崿F(xiàn)一次性驅(qū)動(dòng)若干運(yùn)算操作和同時(shí)驅(qū)動(dòng)同一個(gè)運(yùn)算通路中兩個(gè)不同可重構(gòu)功能單元的能力，必然能夠達(dá)到提升協(xié)處理器功能單元并行執(zhí)行效率的目的。

2　面向分組密碼的二維指令架構(gòu)

通過上述分析可知，超長指令字架構(gòu)的指令通過增加并行執(zhí)行的指令數(shù)量這一維度，提高協(xié)處理器的密碼運(yùn)算位寬和指令并行度，從而提高了協(xié)處理器并行處理能力。而為了能夠?qū)崿F(xiàn)一次性驅(qū)動(dòng)若干運(yùn)算操作，必須通過增加單條指令的執(zhí)行周期這一維度實(shí)現(xiàn)。因此，提出了面向分組密碼的二維指令架構(gòu)。

2.1　二維指令的執(zhí)行結(jié)構(gòu)

二維指令架構(gòu)主要由運(yùn)算型基本指令和重構(gòu)型運(yùn)算指令兩種運(yùn)算指令組成，其中運(yùn)算型基本指令能夠驅(qū)動(dòng)協(xié)處理器完成一次單一功能的密碼運(yùn)算操作，兼容原協(xié)處理器的運(yùn)算類指令。重構(gòu)型運(yùn)算指令通過若干個(gè)運(yùn)算型基本指令定義，被定義后的重構(gòu)型二維指令，能夠按照運(yùn)算型基本指令定義的順序，逐個(gè)執(zhí)行，并執(zhí)行多個(gè)時(shí)鐘周期，如圖3所示。

圖3　指令定義與指令執(zhí)行

在指令定義階段通過運(yùn)算型基本指令定義重構(gòu)型運(yùn)算指令，從而使得協(xié)處理器的二維指令成為一種可重構(gòu)的指令；在指令執(zhí)行階段，二維指令被分解成若干個(gè)運(yùn)算型基本指令，分別在相鄰的時(shí)鐘周期執(zhí)行，使得一個(gè)指令能夠一次性驅(qū)動(dòng)若干個(gè)運(yùn)算操作。根據(jù)二維指令架構(gòu)，提出了二維指令的執(zhí)行結(jié)構(gòu)和并行處理模式。

二維指令的執(zhí)行過程是指令進(jìn)行反復(fù)譯碼，數(shù)據(jù)在功能單元反復(fù)運(yùn)算的過程，如圖4所示。進(jìn)行本時(shí)鐘周期數(shù)據(jù)運(yùn)算的同時(shí)，進(jìn)行下一時(shí)鐘周期的指令譯碼。當(dāng)一個(gè)重構(gòu)型二維指令的第一個(gè)基本型指令進(jìn)入執(zhí)行級時(shí)，第二個(gè)基本型指令則進(jìn)入譯碼級，當(dāng)?shù)诙€(gè)基本型指令進(jìn)入執(zhí)行級時(shí)，第三個(gè)基本型指令則進(jìn)入譯碼級。從而使得一個(gè)指令能夠一次性驅(qū)動(dòng)多個(gè)密碼運(yùn)算操作。

圖4　二維指令的執(zhí)行結(jié)構(gòu)

2.2　二維指令的并行處理模式

雖然上述二維指令結(jié)構(gòu)能夠解決一個(gè)指令一次性驅(qū)動(dòng)多個(gè)密碼運(yùn)算操作，但是采用現(xiàn)有協(xié)處理器架構(gòu)依然不能提高密碼運(yùn)算單元的利用率，因此必須增加相應(yīng)的譯碼電路和數(shù)據(jù)級聯(lián)網(wǎng)絡(luò)才能夠?qū)⑦\(yùn)算通路中的不同運(yùn)算單元進(jìn)行分離，如圖5所示。二維指令的運(yùn)算型基本指令分別通過寄存器寄存，并進(jìn)入對應(yīng)的譯碼電路驅(qū)動(dòng)相應(yīng)運(yùn)算單元；運(yùn)算數(shù)據(jù)通過取數(shù)電路將數(shù)據(jù)從寄存器文件中取出，并通過數(shù)據(jù)級聯(lián)交互網(wǎng)絡(luò)將數(shù)據(jù)傳送至下一個(gè)運(yùn)算單元，最后通過回寫電路回寫至寄存器文件中。

圖5　二維指令與數(shù)據(jù)路徑簡化

采用上述數(shù)據(jù)路徑簡化，能夠?qū)崿F(xiàn)當(dāng)一條重構(gòu)型二維指令在驅(qū)動(dòng)一個(gè)可重構(gòu)功能單元時(shí)，上一條重構(gòu)型二維指令在驅(qū)動(dòng)其它的可重構(gòu)功能單元。從而實(shí)現(xiàn)了協(xié)處理器同時(shí)驅(qū)動(dòng)同一運(yùn)算通路中的若干個(gè)不同可重構(gòu)功能單元。存在以下兩種情況的二維指令不能進(jìn)行并行化運(yùn)算：

(1)當(dāng)前后兩條重構(gòu)型運(yùn)算指令同時(shí)驅(qū)動(dòng)相同的可重構(gòu)功能單元時(shí)，將會(huì)出現(xiàn)功能單元調(diào)用沖突，這種沖突將會(huì)導(dǎo)致其中一個(gè)二維運(yùn)算指令的運(yùn)算結(jié)果錯(cuò)誤或丟失，需要對后一條二維運(yùn)算指令插入氣泡；

(2)當(dāng)前后兩條重構(gòu)型運(yùn)算指令同時(shí)驅(qū)動(dòng)回寫單元時(shí)，將會(huì)出現(xiàn)回寫沖突，這種沖突會(huì)導(dǎo)致其中一個(gè)二維指令的運(yùn)算結(jié)果回寫失敗，需要對后一條二維運(yùn)算指令插入氣泡；

然而，由于分組密碼算法具有相鄰復(fù)雜運(yùn)算操作不同的特點(diǎn)，合理規(guī)劃重構(gòu)型二維指令能夠大大地降低插入氣泡的數(shù)量，提高密碼處理能力。

2.3　可重構(gòu)分組密碼協(xié)處理器架構(gòu)

針對面向分組密碼的二維指令架構(gòu)，可重構(gòu)分組密碼協(xié)處理器必須能夠在不增加功能單元的情況下提高指令運(yùn)算的并行度。鑒于此，二維密碼協(xié)處理器架構(gòu)如圖6所示。

圖6　可重構(gòu)分組密碼協(xié)處理器架構(gòu)

面向二維指令的可重構(gòu)分組密碼協(xié)處理器采用經(jīng)典的三級流水線架構(gòu)，包括取指級、譯碼級、執(zhí)行/回寫級，取指級主要包括指令RAM、取指電路、重構(gòu)型指令存儲(chǔ)器和重構(gòu)指令取指電路；譯碼級主要包括基本指令譯碼電路和4個(gè)重構(gòu)型指令譯碼電路；執(zhí)行/回寫級包括4個(gè)可重構(gòu)密碼單元(reconfigurable cipher unit，RCU)、回寫仲裁單元、回寫網(wǎng)絡(luò)，其中每一個(gè)RCU均由7個(gè)可重構(gòu)單元組成。特別地，增加了數(shù)據(jù)級聯(lián)交互網(wǎng)絡(luò)，用于在執(zhí)行重構(gòu)型運(yùn)算指令時(shí)，完成上一條指令的目的操作數(shù)到下一條指令的源操作數(shù)的數(shù)據(jù)交互問題。

3　算法實(shí)現(xiàn)與指令并行度評估

為了驗(yàn)證二維指令在密碼算法實(shí)現(xiàn)的能力，本文對AES算法進(jìn)行了指令實(shí)現(xiàn)。首先定義AES輪運(yùn)算二維指令，見表1。

表1　AES算法實(shí)現(xiàn)

其中RCFG為定義二維指令的指令助記符，AES_Round_Encryption為定義的AES算法輪運(yùn)算指令。在二維指令的定義過程中，RgA0僅是為一個(gè)對象，并不具有實(shí)際意義，在二維指令調(diào)用時(shí)，改變二維指令的操作對象，如下：

AES_Round_Encryption[RgA0,RgB0,RgC0,RgD0][RgA1,RgB1,RgC1,RgD1]

表示利用AES輪運(yùn)算指令運(yùn)算GRA5，GRB5，GRC5，GRD5和GRA6，GRB6，GRC6，GRD6兩組對象，并把數(shù)據(jù)回寫至GRA5，GRB5，GRC5，GRD5寄存器中。采用上述二維指令的定義方法能夠利用58條指令實(shí)現(xiàn)3個(gè)分組的AES加密運(yùn)算。

為了評估二維指令架構(gòu)的指令并行度，利用二維指令架構(gòu)實(shí)現(xiàn)SM4算法、ARIA算法、PP-2算法3種主流算法進(jìn)行了實(shí)現(xiàn)，并對指令并行度提升進(jìn)行了比較，見表2。其中改進(jìn)后SM4算法的指令并行度是改進(jìn)前的4倍，改進(jìn)后ARIA算法的指令并行度是改進(jìn)前的2倍，改進(jìn)后PP-2算法的指令并行度是改進(jìn)前的3倍。

表2　其它算法改進(jìn)前后密碼性能指令級比較

4　結(jié)束語

本文針對可重構(gòu)分組密碼協(xié)處理器指令并行度和密碼處理性能提升困難的問題，通過分析分組密碼算法特征以及協(xié)處理器運(yùn)算指令結(jié)構(gòu)特征，提出了一種二維指令架構(gòu)提高協(xié)處理器的功能單元利用率，并提供了二維指令架構(gòu)中指令的執(zhí)行結(jié)構(gòu)和并行處理模式，通過對SM4、ARIA、PP-2這3種密碼算法實(shí)現(xiàn)和協(xié)處理器指令負(fù)載的評估，進(jìn)一步驗(yàn)證了二維指令架構(gòu)能夠較好地適應(yīng)分組密碼處理，提高可重構(gòu)分組密碼協(xié)處理器的指令并行度。

參考文獻(xiàn)：

[1]FENG Xiao,DAI Zibin,LI Wei,et al.Performance model of multicore crypto processor based on Amdahl’s law[J].Journal of Electronics and Information,2016,38(4):827-833(in Chinese).[馮曉,戴紫彬,李偉,等.基于Amdahl定律的多核密碼處理器性能模型研究[J].電子與信息學(xué)報(bào),2016,38(4):827-833.]

[2]DU Yiran,LI Wei,DAI Zibin.Research and implementation of network-on-chip interlinkage structure for multi-core cipher processor[J].Microelectronics & Computer,2016,33(1):10-14(in Chinese).[杜怡然,李偉,戴紫彬.多核密碼處理器中的片上網(wǎng)絡(luò)互連結(jié)構(gòu)研究[J].微電子學(xué)與計(jì)算機(jī),2016,33(1):10-14.]

[3]CHEN Xiaogang,LI Wei,XU Jinfu.Research on data buffer mechanism of MCP[J].Microelectronics & Computer,2016,33(5):153-156(in Chinese).[陳曉鋼,李偉,徐金甫.多核密碼處理器數(shù)據(jù)緩存機(jī)制研究[J].微電子學(xué)與計(jì)算機(jī),2016,33(5):153-156.]

[4]YE Bin.High-performance crypto algorithm with many-core architecture[J].Communications Technology,2013,46(4):9-12(in Chinese).[葉賓.眾核構(gòu)造高性能密碼算法協(xié)處理器[J].通信技術(shù),2013,46(4):9-12.]

[5]Megalingam RK,JosephI P,Gautham P,et al.Reconfigurable cryptographic processor for multiple crypto-algorithms[C]//Students’Technology Symposium.IEEE,2011:204-210.

[6]Tian C,Zhu J,Shan W,et al.VLSI design of reconfigurable cipher coprocessor supporting both symmetric and asymmetric cryptographic algorithms[C]//Proceedings of International Conference on Computer Science and Information Technology,2014:299-307.

[7]Júnior JN.Faster variants of the MESH block ciphers[C]//International Conference on Cryptology in India,2004:162-174.

[8]Kwon D,Kim J,Park S,et al.New block cipher:ARIA[G].LNCS 2971:Information Security and Cryptology-ICISC 2003.Springer Berlin Heidelberg,2003: 432-445.

[9]Wu Z,Luo Y,Lai X,et al.Improved cryptanalysis of the FOX block cipher[C]//1st International Conference on Trusted Systems,2009:236-249.

[10]Bucholc K,Chmiel K,Grocholewska-Czurylo A,et al.PP-2block cipher[C]//7th International Conference on Emerging Security Information,2013:162-168.

[11]JIN Chenhui.Cryptology[M]//Beijing:Higher Education Press,2009(in Chinese).[金晨輝.密碼學(xué)[M].北京:高等教育出版社,2009.]

[12]YU Xuerong.Parallel co-processor architecture research and instruction system design for block ciphers[D].Zhengzhou:Information Engineering University,2007(in Chinese).[于學(xué)榮.并行分組密碼處理結(jié)構(gòu)研究及指令系統(tǒng)設(shè)計(jì)[D].鄭州:信息工程大學(xué),2007.]