LTE中的Rijndael算法研究*

吳云梅，李小文，劉丹丹

（重慶郵電大學(xué) 通信學(xué)院，重慶 400065）

責(zé)任編輯:孫 卓

1 引言

自20世紀(jì)70年代以來(lái)，被廣泛使用的數(shù)據(jù)加密標(biāo)準(zhǔn)（DES）日益不能滿足人們對(duì)數(shù)據(jù)安全性的需求。2000年10月，美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究所（NIST）經(jīng)過(guò)多次評(píng)估，確定Rijndael算法為美國(guó)高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）[1]，代替使用了 20 多年的 DES。如今該標(biāo)準(zhǔn)已在LTE系統(tǒng)中多處使用，其中在非接入層初始密鑰的形成過(guò)程中[2]，使用了7次的Ek核就是Rijndael算法，只是每次使用的明文和密鑰矩陣都不同。另外，非接入層和接入層的完整性保護(hù)算法（128-EIA2）與加密算法（128-EEA2）都是基于AES的Rijndael算法[3]。

2 Rijndael算法介紹

Rijndael算法中的許多運(yùn)算是按字節(jié)為單位定義，1 byte可以看作是有限域GF（28）中的一個(gè)元素，由b7b6b5b4b3b2b1b0構(gòu)成的字看作是多項(xiàng)式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0，其中 bi∈GF（2），0≤i≤7，bi為 0 或1。算法中涉及的運(yùn)算主要有兩種:

1）2個(gè)多項(xiàng)式的加法運(yùn)算

定義為:相同指數(shù)項(xiàng)的系數(shù)和再模余2，即異或運(yùn)算。例如，（x7+x5+x4+x3+x+1）+（x6+x5+x4+x2+x）=x7+x6+x3+x2+1。

2）2個(gè)多項(xiàng)式的乘法運(yùn)算

多項(xiàng)式相乘之后的結(jié)果很容易造成溢位，解決溢位的方式是把2個(gè)多項(xiàng)式相乘的結(jié)果再模余1個(gè)不可約多項(xiàng)式 m（x）。 在 Rijndael算法中，該多項(xiàng)式為 m（x）=x8+x4+x3+x+1。例如，（x7+x4+x3+x2+x）mod（x8+x4+x3+x+1）=x7+x4+x3+x2+x。

3 Rijndael算法原理

3.1 Rijndael算法外部結(jié)構(gòu)

Rijndael算法的外部輸入由明文比特流和密鑰比特流兩部分組成，輸出為密文比特流，如圖1所示。明文比特流映射到4×Nb的狀態(tài)矩陣中，密鑰比特流也是一個(gè)4×Nk的矩陣。在Rijndael算法中，運(yùn)算的輪數(shù)Nr由Nb和Nk決定，輪數(shù)的變動(dòng)關(guān)系如表1所示。在當(dāng)前的LTE系統(tǒng)中均采用128 bit明文和128 bit密鑰的分組方式，即Nb=4，Nk=4，所以執(zhí)行的輪變換次數(shù)為10次。筆者將以LTE系統(tǒng)中使用的Nb=4，Nk=4的分組方式說(shuō)明。

表1 Rijndael算法中Nb，Nk與Nr之間的關(guān)系

3.2 Rijndael算法內(nèi)部數(shù)學(xué)模型

算法的核心是輪運(yùn)算，中間每輪運(yùn)算由字節(jié)替代變換（SubByte）、行移位變換（ShiftRow）、混合列變換（Mix-Column）、輪密鑰加（AddRoundKey）組成，但終結(jié)輪（Final Round）運(yùn)算沒(méi)有混合列變換。筆者以一輪加密過(guò)程為例分析其數(shù)學(xué)模型。

3.2.1 字節(jié)替代變換

字節(jié)替代變換是Rijndael算法中唯一的線性變換。它是一個(gè)磚匠置換，該置換包含一個(gè)作用在狀態(tài)字節(jié)上的S盒。該S盒由有限域GF（28）上的乘法逆和仿射（Affine）運(yùn)算構(gòu)成。在有限域GF（28）上求逆運(yùn)算保證了S盒的非線性。有限域GF（28）上的乘法逆運(yùn)算定義為

用a-1進(jìn)行仿射運(yùn)算可得到字節(jié)替換的最終結(jié)果為

3.2.2 行移位變換

在行移位變換中，中間狀態(tài)矩陣第1，2，3，4行分別循環(huán)左移 0，1，2，3 位，如圖 2 所示。

圖2 狀態(tài)矩陣行移位變換示意圖

3.2.3 混合列變換

混合列變換是把狀態(tài)矩陣中的每一列看作GF（28）上的多項(xiàng)式s（x）與一個(gè)固定多項(xiàng)式c（x）作乘法運(yùn)算，如果發(fā)生溢位，則再模余 x4+1，表示為 c（x）={03}x3+{01}x2+{01}x+{02}，c（x）與 x4+1 互質(zhì)，以矩陣乘法表示為

式中:0≤c≤3。

3.2.4 輪密鑰加

經(jīng)過(guò)混合列變換的狀態(tài)矩陣與密鑰矩陣按位異或（符號(hào)為⊕），根據(jù)加密的輪數(shù)使用相應(yīng)的擴(kuò)展密鑰矩陣，具體為

式中:0≤c≤3，ExpandedKey[i]c為第 i輪擴(kuò)展密鑰矩陣的第c列。

4 Rijndael算法加密/解密的實(shí)現(xiàn)

根據(jù)LTE系統(tǒng)中使用的Nb=4，Nk=4的分組方式，筆者設(shè)計(jì)的Rijndael算法加密流程圖如圖3所示，首先是4×4的狀態(tài)矩陣與4×4的初始密鑰矩陣按位執(zhí)行異或運(yùn)算，然后進(jìn)行9輪迭代輪變換，每一輪的變換由字節(jié)替代變換、行移位變換、混合列變換、輪密鑰加組成，終結(jié)輪變換不包含混合列變換。作為Rijndael算法的最終輸出結(jié)果，密文比特流從經(jīng)過(guò)加密處理的狀態(tài)矩陣中由左至右按列輸出。

圖3 Rijndael算法加密流程圖

基于圖3的Rijndael算法加密流程設(shè)計(jì)出以下偽C代碼描述的加密主程序?yàn)?

所以最終輸出密文比特流就是Round[10]密文，再將得到的密文比特流作為解密過(guò)程的輸入，得到相應(yīng)的明文比特流，這樣互相驗(yàn)證了加/解密過(guò)程的正確性。

5 小結(jié)

Rijndael算法的設(shè)計(jì)策略為寬軌跡策率（Wide Trail Strategy），提高抗差分攻擊和線性攻擊的強(qiáng)度。算法中各變換均為可逆變換，降低了解密過(guò)程的實(shí)現(xiàn)代價(jià)，字節(jié)替代變換起到混淆作用，提高差分均勻性，行移位和混合列變換都屬于線性混合運(yùn)算，確保多輪迭代運(yùn)算的高度擴(kuò)散性。Rijndael算法是將安全、高效、性能及靈活性集于一體，并且在不同的硬件和軟件運(yùn)行環(huán)境中都表現(xiàn)出始終如一的良好性能，這使它成為AES的合適選擇。也正是因?yàn)檫@些優(yōu)點(diǎn)，Rijndael在當(dāng)前LTE系統(tǒng)中得到廣泛的應(yīng)用。

[1]NIST FIPS PUB 197，Advanced Encryption Standard-federal information processing standards publication[S].2001.

[2]3GPP TS 35.205， 3rd generation partnership project； technical specification group services and system aspects；3G security；specification of the milenage algorithm set:an example algori-thm set for the 3GPP authentication and key generation func-tions f1，f1*，f2，f3，f4，f5and f5*；Document 1:general[S].2002.

[3]3GPP TS 33.401 V8.5.0， 3GPP system architecture evolution；security architecture[S].2009.