錢曉捷，師攀攀，王建輝

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

0 引 言

IBM公司在1977年研制的一種加密算法，被美國國家標準局（NIST）公布并批準為非機要部門使用的數(shù)據(jù)加密標準（data encryption standard，DES）。然而，傳統(tǒng)的數(shù)據(jù)加密標準DES已經(jīng)不能滿足現(xiàn)有的安全需求，從1997年起，NIST通過發(fā)布公告來公開征集新的加密標準，即高級加密標準（advanced encryption standard，AES），以取代DES。通過對各候選算法的多輪篩選，NIST于2000年10月2日正式宣布Rijndael算法為新的高級加密標準［1］，并且未對Rijndael算法做任何修改。

多核處理器以其高性能、低功耗優(yōu)勢正逐步取代傳統(tǒng)的單核處理器成為市場的主流［2］，然而，在計算機安全領(lǐng)域，多核處理器的應用剛剛開始，利用多核多線程技術(shù)對加密算法進行并行優(yōu)化研究，對于提高網(wǎng)絡通信速度、強化計算機網(wǎng)絡安全有著重要的理論意義和實際價值。通過對Rijndael算法的輪變換進行分析，分別采用基于數(shù)據(jù)分解和數(shù)據(jù)流分解兩種方式對Rijndael算法進行并行化改造，充分利用硬件資源，通過多核多線程技術(shù)，將串行加密程序輪變換環(huán)節(jié)并行化實現(xiàn)，從而提高Rijndael算法的執(zhí)行效率。

1 Rijndael算法描述

AES的分組長度為128比特，密鑰長度有3種：128比特、192比特、256比特；Rijndael算法的分組長度和密鑰長度都是可變的，可以分別獨立地設為128比特、192比特、256比特［3－4］。

1.1 Rijndael算法的結(jié)構(gòu)

Rijndael算法是一個分組迭代密碼算法，其加密和解密的所有操作都在被稱為狀態(tài)（state）的中間結(jié)果上進行，狀態(tài)可以用圖1所示的矩陣陣列圖來表示，該圖的元素為字節(jié)［5］。該陣列的行數(shù)為4，列數(shù)為Nb，而Nb的大小由分組長度決定，等于分組長度除以除以32。

密碼密鑰的列數(shù)記為Nk，等于密鑰長度除以32。Ri－jndael算法的分組長度和密鑰長度均可獨立地設定為128、192、256位，所以Nb和Nk均可獨立取值為4、6、8。用Nr表示Rijndael算法迭代的輪數(shù)，Nr依賴于分組長度和密鑰長度。表1列出了作為Nb和Nk函數(shù)的Nr的值。

圖1 Nb＝6時的狀態(tài)

表1 對不同的Nb和Nk輪的個數(shù)值Nr

Rijndael算法的加密過程為：首先進行一次初始密鑰加法AddRoundKey，然后進行Nr－1次輪變換Round，最后執(zhí)行一次輪變換FinalRound，Rijndael算法各輪輪變換都作用在狀態(tài)State上［6］。128位Rijndael的流程圖如圖2所示。

從圖2可以看出，128位Rijndael算法是一個10輪迭代密碼算法。輸入是一個數(shù)據(jù)塊和初始密鑰。每一個輪變換作用于前一個輪變換之后的中間結(jié)果，是一個由以下4個變換構(gòu)成的序列：SubBytes、ShiftRows、MixColumns和AddRoundKey。最后一個輪變換稍有不同，相比其它輪少了MixColumns。輸出是經(jīng)過10輪變換后的加密數(shù)據(jù)塊［7］。

圖2 Rijndael算法流程

1.2 Rijndael算法的實現(xiàn)

1.2.1 密鑰編排

密鑰編排方案包括兩個組成部分，即密鑰的擴展和輪密鑰的選?。?］。

（1）密鑰擴展

密鑰擴展指的是在知道密碼密鑰的條件下獲取ExpandedKey，而不是直接指定ExpandedKey。在密鑰擴展階段，將密鑰擴展成4行Nb（Nr＋1）列的擴展密鑰數(shù)組，用 W ［Nb×（Nr＋1）］表示［8］，最先 Nk個字包含了加密密鑰，所有其他字用最小下標遞歸地定義，密鑰擴展函數(shù)依賴于Nk的值。

當Nk≤6時，密鑰擴展函數(shù)的C＋＋語言代碼描述如下：

當Nk＞6時，密鑰擴展函數(shù)的C＋＋語言代碼描述如下：

（2）輪密鑰的選取

第i輪子密鑰是由 W ［Nb＊i］到 W ［Nb＊（i＋1）］間的位構(gòu)成。以Nb＝4，Nk＝4為例，如圖3所示。

圖3 輪密鑰的選取

1.2.2 輪變換

輪變換Round的每一輪都包含以下4個階段的代換，SubBytes（字節(jié)變換）、ShiftRows（行移位變換）、MixColumns（列混合變換）、AddRoundKey（輪密鑰加變換）［9］。

（1）SubBytes變換

字節(jié)變換SubBytes是Rijndael密碼中唯一的非線性變換［10］，它獨立地作用于每個狀態(tài)字節(jié)。字節(jié)替換由以下2個步驟組成：首先求出每個字節(jié)在GF（28）中的乘法逆元素，其中 “00”和 “01”的逆是它們自身［11］；然后將該逆元字節(jié)作GF（2）上的如下仿射變換

（2）ShiftRows變換

行移位變換ShiftRows是一線性組合，它能導致多輪循環(huán)的各個位之間的擴散［12］。根據(jù)不同的分組長度和密鑰長度，行移位變換會做出不同的旋轉(zhuǎn)，假設不同的狀態(tài)中每行的移位字節(jié)數(shù)分別為C0，C1，C2，C3，則C1，C2，C3跟分組長度Nb有關(guān)，具體分組長度對應的移位字節(jié)數(shù)如表2所示［13］。

表2 不同分組長度對應的移位偏移量

（3）MixColumns變換

列混合變換MixColumns把狀態(tài)中的每一列都看作是GF（28）上的多項式a（x）與一個固定多項式的模乘，假設b（x）＝c（x）·a（x）（modx4＋1），用矩陣乘法的形式可以表示如下［14］

（4）AddRoundKey變換

該變換主要是把通過以上3個變換得到的數(shù)據(jù)與該輪的輪密鑰進行異或運算，得到的數(shù)據(jù)再進行下一輪的輪變換。

2 Rijndael算法的并行優(yōu)化實現(xiàn)

2.1 設計思想

2.1.1 工作模式

AES工作模式主要分為串行模式和并行模式兩類。

串行模式的主要特點是各個分組的加密和解密過程依賴于其前序分組，并且影其響后序分組的加密結(jié)果，如果分組不存在規(guī)律變化，這一類模式基本上找不到可并行的計算方法［15］。該模式主要包括密碼分組連接（CBC）模式和密碼反饋（CFB）模式。

并行模式的主要特點是各個分組在加密和解密過程的輸入輸出不和其它分組產(chǎn)生關(guān)聯(lián)，故該模式能夠在時間優(yōu)先的策略下實現(xiàn)并行計算，以獲得較高的系統(tǒng)性能［15］。并行模式主要包括電子密碼本（ECB）模式、輸出反饋（OFB）模式。由于流水線結(jié)構(gòu)不適用于反饋模式，為了達到較高的運算速度，本文對Rijndael算法進行并行優(yōu)化采用的模式為電子密碼本（ECB）模式。

2.1.2 并行編程中的任務分解模式

并行編程使用線程來使得多個操作能夠同時運行。在面向多核平臺設計多線程應用程序的時候，開發(fā)人員必須采取與面向單核平臺時不同的設計思想。在單CPU下，是多個線程在同一個CPU上并發(fā)地執(zhí)行，而在多核下，則是由多個線程在多個核上并行地執(zhí)行。但目前的程序設計中對于多核的利用并沒有達到預期的效果。因此，在多核的環(huán)境下設計出更適合多核系統(tǒng)的程序，既是一個機遇又是一個挑戰(zhàn)。

要做到這一點，應該將應用程序看作是眾多相互依賴的任務的集合，將應用程序劃分成多個獨立的任務，并確定這些任務之間的相互依賴關(guān)系，這就稱為分解（decomposition）［16］。分解的方式主要有3種：任務分解、數(shù)據(jù)分解和數(shù)據(jù)流分解。表3給出了這3種分解方式之間的對比。

表3 各分解方式之間的對比

2.2 基于多核的Rijndael并行化

隨著多核處理器的普及，充分利用現(xiàn)有的多核資源用于Rijndael加解密對于提高加解密效率有著重要的實際意義。

由于Rijndael算法輪變換中的4個構(gòu)成變換之間存在相關(guān)性，即后一個變換執(zhí)行前要知道前一個變換的結(jié)果，各個變換不能夠同時執(zhí)行，故該算法不宜采用基于任務分解的方式進行并行化。下面從數(shù)據(jù)分解和數(shù)據(jù)流分解兩個方面對Rijndael算法進行并行優(yōu)化。

2.2.1 基于數(shù)據(jù)分解方式的并行化

Rijndael算法中輪變換的4個構(gòu)成變換都是獨立的作用于狀態(tài)的字節(jié)、行或者列之上的，故可以把構(gòu)成變換對整個狀態(tài)的作用分割成對狀態(tài)的每一個組成單元（字節(jié)、行或列）的作用［17］。構(gòu)成變換對狀態(tài)作用的獨立性，也就決定了各個構(gòu)成變換對狀態(tài)的每一個組成單元的作用都能夠以并行進行。

假設處理器內(nèi)核數(shù)為N，分組長度、密鑰長度均為128位，則Nb＝Nk＝4。由于SubBytes變換獨立地作用于每一個狀態(tài)字節(jié)之上，所以該構(gòu)成變換可以并行執(zhí)行。假定對每一個狀態(tài)字節(jié)作一次SubBytes變換需要1個時間單位，則所有狀態(tài)字節(jié)串行模式下執(zhí)行完SubBytes變換需要16個時間單位，而在并行模式下，只需要16/N個時間單位即可執(zhí)行完該變換［17］。同理，假定一行狀態(tài)字節(jié)作一次ShiftRows變換需要1個時間單位，串行模式下整個ShiftRows變換需要3個時間單位，并行模式下只需要3/N個時間單位；假定對一列狀態(tài)字節(jié)作MixColumns變換需要1個時間單位，串行模式下整個MixColumns變換需要4個時間單位，并行模式下只需要4/N個時間單位；假定每個狀態(tài)字節(jié)作一次AddRoundKey變換需要1個時間單位，串行模式下整個AddRoundKey變換需要16個時間單位，并行模式下只需要16/N個時間單位。

2.2.2 基于數(shù)據(jù)流分解方式的提出

Rijndael算法輪變換由4個構(gòu)成變換組成，從第2個變換開始，每個變換在執(zhí)行之前，都需要知道前一個變換執(zhí)行后的結(jié)果，即前一個變換的輸出是后一個變換的輸入。如果將兩個變換采用不同的線程并行執(zhí)行，那么處理后一個變換的線程需要一直等到前一個變換完成變換工作之后才能開始執(zhí)行。

通過對SubBytes變換和ShiftRows變換的分析，ShiftRows變換獨立地作用于狀態(tài)矩陣的每一行，故每當狀態(tài)矩陣的某一行執(zhí)行完SubBytes變換后，即可開始對該行執(zhí)行ShiftRows變換，而不必等到所有的狀態(tài)字節(jié)全部執(zhí)行SubBytes變換后才執(zhí)行ShiftRows變換。記狀態(tài)矩陣第N行執(zhí)行SubBytes變換為SB（N），執(zhí)行ShiftRows變換為SR（N），基于以上分析，通過基于數(shù)據(jù)流的分解方式，可對輪變換的前兩個構(gòu)成變換執(zhí)行過程進行如圖4所示的描述。

圖4 前兩個構(gòu)成變換的數(shù)據(jù)流分解

假定對狀態(tài)矩陣的一行字節(jié)執(zhí)行SubBytes變換需要a個時間單位，對狀態(tài)矩陣的一行字節(jié)執(zhí)行ShiftRows變換需要b個時間單位，則前兩個變換執(zhí)行完畢需要消耗（4a＋4b）個時間單位。采用基于數(shù)據(jù)流的分解方式并行化之后，若a＞b，則前兩個變換只需要（4a＋b）個時間單位；若a＜b，則前兩個變換只需要（a＋4b）個時間單位。

由于ShiftRows變換是逐行對狀態(tài)矩陣進行操作，MixColumns變換是逐列對狀態(tài)矩陣進行操作，故必須等到狀態(tài)矩陣的所有狀態(tài)字節(jié)執(zhí)行完ShiftRows變換后才執(zhí)行MixColumns變換，因次，MixColumns變換和ShiftRows變換之間無法采用基于基于數(shù)據(jù)流的分解方式進行并行優(yōu)化。

繼而對MixColumns變換和AddRoundKey變換進行分析，發(fā)現(xiàn)這兩個變換同樣可以通過基于數(shù)據(jù)流分解的方式并行優(yōu)化。狀態(tài)矩陣的每一列執(zhí)行完MixColumns變換之后，即可對該列執(zhí)行AddRoundKey變換，而不必等到整個狀態(tài)矩陣的所有字節(jié)都執(zhí)行MixColumns變換后才執(zhí)行AddRoundKey變換。記狀態(tài)矩陣第N列執(zhí)行MixColumns變換為 MC（N），執(zhí)行AddRoundKey變換為ARK（N），在以上分析的基礎上，再通過基于數(shù)據(jù)流的分解方式，可以將輪變換的后兩個構(gòu)成變換執(zhí)行過程進行如圖5所示的描述。

圖5 后兩個構(gòu)成變換的數(shù)據(jù)流分解

假定狀態(tài)矩陣的一列字節(jié)執(zhí)行MixColumns變換需要消耗c個時間單位，對狀態(tài)矩陣的一列字節(jié)執(zhí)行AddRound－Key變換需要消耗d個時間單位，則狀態(tài)矩陣的全部狀態(tài)字節(jié)在串行模式下執(zhí)行完后兩個變換共需消耗（4c＋4d）個時間單位。通過基于數(shù)據(jù)流分解方式的并行化之后，若c＞d，則后兩個變換只需要（4c＋d）個時間單位；若c＜d，則后兩個變換只需要（c＋4d）個時間單位。

3 實驗結(jié)果分析

實 驗 采 用 Intel Core 2Duo E7200（雙 核， 主 頻2.53GHZ），2GB RAM PC機，Windows XP操作系統(tǒng)平臺，使用Visual C＋＋6.0作為開發(fā)平臺。

對Rijndael算法采用基于數(shù)據(jù)分解方式并行化實現(xiàn)后的實驗結(jié)果進行分析，發(fā)現(xiàn)采用此分解方式并行后的算法并沒有提高加密性能，反而降低了加密性能，這是因為這4個構(gòu)成變換的函數(shù)主體均為二重循環(huán)，本身計算量都很小，并行化產(chǎn)生的收益遠遠小于并行化付出的代價。因此，通過基于數(shù)據(jù)分解的方式對Rijndael算法并行優(yōu)化的方案是不可行的。

文獻 ［18］給出Rijndael算法輪變換的4個構(gòu)成變換的時間消耗比為4a：4b：4c：4d＝31：63：266：31，串行模式下4個構(gòu)成變換共消耗4a＋4b＋4c＋4d＝31＋63＋266＋31＝391個時間單位，由于a＜b，c＞d，則采用基于數(shù)據(jù)流的分解方式并行化之后共消耗a＋4b＋4c＋d＝31＊0.25＋63＋266＋31＊0.25＝344.5個時間單位。

本文采用加速比來衡量并行程序設計所帶來的性能收益，即用串行算法的執(zhí)行時間除以并行程序的執(zhí)行時間。對比采用數(shù)據(jù)流分解方式對Rijndael算法輪變換4個構(gòu)成變換并行化前后所消耗的時間可知，串行算法的執(zhí)行時間/并行程序的執(zhí)行時間＝（4a＋4b＋4c＋4d）/（a＋4b＋4c＋d）＝391/344.5＝1.135，即理論加速比為1.135，或者說理論上性能可以提高13.5%。

表4是對Rijndael算法采用基于數(shù)據(jù)流分解方式并行化前后的加解密測試結(jié)果，顯示了當密鑰長度和分組長度均為128位時，串行和并行的運行消耗時間的比較。輸入明文字節(jié)總數(shù)記為N，數(shù)據(jù)流分解前串行程序運行時間記為T1，基于數(shù)據(jù)流分解后并行程序運行時間T2，時間單位是10－6s，實驗結(jié)果如表4所示。為了保證測試的普遍性與準確性，實驗采用大數(shù)據(jù)量明文分別對Rijndael算法進行串行和并行測試，表4中的運行時間T1和T2都是通過對十次測試結(jié)果取平均值得到的。

表4 性能對比數(shù)據(jù)

通過對表4中串行和并行時間對比分析可知，采用基于數(shù)據(jù)流分解方式對Rijndael算法輪變換Round的各個構(gòu)成變換的分解，分解之后的Rijndael算法并行實現(xiàn)程序運行時間較分解之前串行程序運行時間有了縮短。

并行后的Rijndael算法所獲得的平均加速比＝（1.054＋1.065＋1.079＋1.071＋1.068）/5＝1.0674，性能較并行前有了6.74%的提升，雖然距理論值13.5%還有一些差距，綜合多種因素來看，并行后的性能提升還是可以接受的。因此，對Rijndael算法并行優(yōu)化所帶來的性能提升基本符合實驗預期要求。

4 結(jié)束語

本文通過對Rijndael算法輪變換的各構(gòu)成變換進行分析，采用基于數(shù)據(jù)流的分解方式對各構(gòu)成變換進行分解，把各構(gòu)成變換對整個狀態(tài)的作用分割成對狀態(tài)的每個組成單元的作用，使得各構(gòu)成變換可以并行進行。通過實驗對該優(yōu)化方案進行了驗證，在保證安全性和對內(nèi)存空間需求基本不變的情況下獲得了較為明顯的性能提升效果。對于強化計算機網(wǎng)絡安全和提高網(wǎng)絡通信效率有著重要的理論意義和實際價值。

［1］JIANG Chuan，HAN Wei，F(xiàn)ANG Xiangyan.Design and implementation of high－speed configurable rijndael algorithm ［J］.Computer＆ Digital Engineering，2009，37（1）：91－95（in Chinese）.［江川，韓威，方湘艷.高速可配置Rijndael算法的設計與實現(xiàn)［J］.計算機與數(shù)字工程，2009，37（1）：91－95.］

［2］HUANG Guorui，ZHANG Ping，WEI Guangbo.Key techniques of multi－core processor and its development trends ［J］.Computer Engineering and Design，2009，30（10）：2414－2418（in Chinese）.［黃國睿，張平，魏廣博.多核處理器的關(guān)鍵技術(shù)及其發(fā)展趨勢 ［J］.計算機工程與設計，2009，30（10）：2414－2418.］

［3］LU Zhengding，LIAO Zhensong.Research on the Rijndael algorithm ［J］.Computer Engineering ＆ Science，2005，27（6）：72－74（in Chinese）.［盧正鼎，廖振松.Rijndael算法的研究［J］.計算機工程與科學，2005，27（6）：72－74.］

［4］YE Jian，LI Lixin.Fast implementation of AES based on GPU［J］.Computer Engineering and Design，2010，31（2）：256－259（in Chinese）.［葉劍，李立新.基于GPU的AES快速實現(xiàn) ［J］.計算機工程與設計，2010，31（2）：256－259.］

［5］TONG Xiaojun，AI Guangping，JIANG Wei，et al.Realization of data encryption and digital signature based on rijndael algorithm atc ［J］.Microprocessors，2007，（2）：80－86（in Chinese）.［佟曉筠，艾廣平，姜偉，等.基于Rijndael算法的數(shù)據(jù)加密與簽名技術(shù)實現(xiàn) ［J］.微處理機，2007，（2）：80－86.］

［6］FU Desheng，WANG Jiesong.A high－speed arithmetic and application of rijndael ［J］.Microcomputer Applications，2007，28（10）：1112－1116（in Chinese）.［傅德勝，王潔松.一種快速Rijndael算法及其應用 ［J］.微計算機應用，2007，28（10）：1112－1116.］

［7］LE Deguang.Parallel AES algorithm for fast data encryption on GPU ［C］.Chengdu：2nd International Conference on Computer Engineering and Technology，2010：V6－1－V6－6.

［8］HE Minwei，LIU Rui.An improved method based on AES Rijndael algorithm ［J］.Control ＆ Automation，2008，22（6－3）：94－96（in Chinese）.［賀敏偉，劉睿.高級加密標準 RIjndael算法的 一 種 改 進 ［J］.微 計 算 機 信 息，2008，22（6－3）：94－96.］

［9］WU Xiaobo.Analysis of AES encipher algorithm and its C＋＋language implementation ［J］.Network ＆ Computer Security，2007，7（12）：44－46（in Chinese）.［吳小博.AES加密算法分析與C＋＋ 編程實現(xiàn) ［J］.計算機安全，2007，7（12）：44－46.］

［10］YIN Xinchun，YANG Jie.Scheme of replacement of S－box in AES Rijndael algorithm ［J］.Computer Engineering，2006，32（21）：173－176（in Chinese）.［殷新春，楊潔.高級加密標準Rijndael算法中S盒的替換方案 ［J］.計算機工程，2006，32（21）：173－176.］

［11］GE Honghua，DING Xiuhuan.A hybrid cryptosystem based on AES and ECC ［J］.Science ＆ Technology Information，2011，28（9）：455－457（in Chinese）.［葛宏華，丁秀歡.基于AES和ECC的混合密碼體制 ［J］.科技信息，2011，28（9）：455－457.］

［12］LIU Zhihui，LIU Jianhui.Research of data encryption transmission based on AES and RSA ［J］.Network ＆ Computer Security，2007，7（11）：39－41（in Chinese）.［劉志會，劉建輝.基于AES和RSA的數(shù)據(jù)加密傳送方案研究 ［J］.計算機安全，2007，7（11）：39－41.］

［13］WANG Xuemei，SUN Xiaodong，CHEN Haoming，et al.The introduction and pipeline designing study of AES ［J］.Network ＆ Computer Security，2007，7（10）：5－8（in Chinese）.［王雪梅，孫曉東，陳昊明，劉艷.AES算法介紹及其流水線設計研究 ［J］.計算機安全，2007，7（10）：5－8.］

［14］LIU Hongyan，YUAN Ping，WU Hengbai.Design strategy research on realizing scheme of Rijndael algorithm ［J］.Computer Engineering and Design，2008，29（23）：5958－5961（in Chinese）.［劉鴻雁，袁平，吳恒柏.Rijndael算法實現(xiàn)方案的設計策略研究 ［J］.計算機工程與設計，2008，29（23）：5958－5961.］

［15］HAN Qiang，F(xiàn)ENG Yi，DING Jing.The design and characteristics of the working modules based on the advanced encryption standard ［J］.Joumal of Yunnan Nationalities University（Natural Sciences Edition），2008，17（4）：362－365（in Chinese）.［韓強，馮翼，丁靜.高級加密標準工作模式的設計與特性分析 ［J］.云南民族大學學報（自然科學版），2008，17（4）：362－365.］

［16］Shameem Akhter，Jason Roberts，TransLation，et al.Multi－Core programming－increasing performance through software multi－threading ［M］.Beijing：Publishing House of Electronics Industry，2007（in Chinese）.［Shameem Akhter，Jason Roberts，李寶峰，等.多核程序設計技術(shù)－通過軟件多線程提升性能 ［M］.北京：電子工業(yè)出版社，2007.］

［17］ZHANG Chao，LU Langru，CHU Zefu，et al.AES algorithms and its implementation technology ［J］.Computer and Communications，2001，19（2）（in Chinese）.［張超，陸浪如，楚澤甫，等.AES算法及其實現(xiàn)技術(shù) ［J］.交通與計算機，2001，19（2）.］

［18］XU Xiaolong.The parallelization research of ECC and AES based on multi－core ［D］.Chendu：University of Electronic Science and Technology of China，2010（in Chinese）.［許小龍.基于多核平臺橢圓曲線算法和AES算法的并行化研究［D］.成都：電子科技大學，2010.］