基于多核的Rijndael算法的并行優化與實現

錢曉捷，師攀攀，王建輝

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

0 引 言

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

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

1 Rijndael算法描述

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

1.1 Rijndael算法的結構

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

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

圖1 Nb＝6時的狀態

表1 對不同的Nb和Nk輪的個數值Nr

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

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

圖2 Rijndael算法流程

1.2 Rijndael算法的實現

1.2.1 密鑰編排

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

（1）密鑰擴展

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

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

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

（2）輪密鑰的選取

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

圖3 輪密鑰的選取

1.2.2 輪變換

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

（1）SubBytes變換

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

（2）ShiftRows變換

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

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

（3）MixColumns變換

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

（4）AddRoundKey變換

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

2 Rijndael算法的并行優化實現

2.1 設計思想

2.1.1 工作模式

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

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

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

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

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

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

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

2.2 基于多核的Rijndael并行化

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

由于Rijndael算法輪變換中的4個構成變換之間存在相關性，即后一個變換執行前要知道前一個變換的結果，各個變換不能夠同時執行，故該算法不宜采用基于任務分解的方式進行并行化。下面從數據分解和數據流分解兩個方面對Rijndael算法進行并行優化。

2.2.1 基于數據分解方式的并行化

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

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

2.2.2 基于數據流分解方式的提出

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

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

圖4 前兩個構成變換的數據流分解

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

由于ShiftRows變換是逐行對狀態矩陣進行操作，MixColumns變換是逐列對狀態矩陣進行操作，故必須等到狀態矩陣的所有狀態字節執行完ShiftRows變換后才執行MixColumns變換，因次，MixColumns變換和ShiftRows變換之間無法采用基于基于數據流的分解方式進行并行優化。

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

圖5 后兩個構成變換的數據流分解

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

3 實驗結果分析

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

對Rijndael算法采用基于數據分解方式并行化實現后的實驗結果進行分析，發現采用此分解方式并行后的算法并沒有提高加密性能，反而降低了加密性能，這是因為這4個構成變換的函數主體均為二重循環，本身計算量都很小，并行化產生的收益遠遠小于并行化付出的代價。因此，通過基于數據分解的方式對Rijndael算法并行優化的方案是不可行的。

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

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

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

表4 性能對比數據

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

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

4 結束語

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

［1］JIANG Chuan，HAN Wei，FANG Xiangyan.Design and implementation of high－speed configurable rijndael algorithm ［J］.Computer＆ Digital Engineering，2009，37（1）：91－95（in Chinese）.［江川，韓威，方湘艷.高速可配置Rijndael算法的設計與實現［J］.計算機與數字工程，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）.［黃國睿，張平，魏廣博.多核處理器的關鍵技術及其發展趨勢 ［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快速實現 ［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算法的數據加密與簽名技術實現 ［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＋＋ 編程實現 ［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的數據加密傳送方案研究 ［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算法實現方案的設計策略研究 ［J］.計算機工程與設計，2008，29（23）：5958－5961.］

［15］HAN Qiang，FENG 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，李寶峰，等.多核程序設計技術－通過軟件多線程提升性能 ［M］.北京：電子工業出版社，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算法及其實現技術 ［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.］