LTE中的Rijndael算法研究*

吳云梅，李小文，劉丹丹

（重慶郵電大學 通信學院，重慶 400065）

責任編輯:孫 卓

1 引言

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

2 Rijndael算法介紹

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

1）2個多項式的加法運算

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

2）2個多項式的乘法運算

多項式相乘之后的結果很容易造成溢位，解決溢位的方式是把2個多項式相乘的結果再模余1個不可約多項式 m（x）。 在 Rijndael算法中，該多項式為 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算法外部結構

Rijndael算法的外部輸入由明文比特流和密鑰比特流兩部分組成，輸出為密文比特流，如圖1所示。明文比特流映射到4×Nb的狀態矩陣中，密鑰比特流也是一個4×Nk的矩陣。在Rijndael算法中，運算的輪數Nr由Nb和Nk決定，輪數的變動關系如表1所示。在當前的LTE系統中均采用128 bit明文和128 bit密鑰的分組方式，即Nb=4，Nk=4，所以執行的輪變換次數為10次。筆者將以LTE系統中使用的Nb=4，Nk=4的分組方式說明。

表1 Rijndael算法中Nb，Nk與Nr之間的關系

3.2 Rijndael算法內部數學模型

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

3.2.1 字節替代變換

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

用a-1進行仿射運算可得到字節替換的最終結果為

3.2.2 行移位變換

在行移位變換中，中間狀態矩陣第1，2，3，4行分別循環左移 0，1，2，3 位，如圖 2 所示。

圖2 狀態矩陣行移位變換示意圖

3.2.3 混合列變換

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

式中:0≤c≤3。

3.2.4 輪密鑰加

經過混合列變換的狀態矩陣與密鑰矩陣按位異或（符號為⊕），根據加密的輪數使用相應的擴展密鑰矩陣，具體為

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

4 Rijndael算法加密/解密的實現

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

圖3 Rijndael算法加密流程圖

基于圖3的Rijndael算法加密流程設計出以下偽C代碼描述的加密主程序為:

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

5 小結

Rijndael算法的設計策略為寬軌跡策率（Wide Trail Strategy），提高抗差分攻擊和線性攻擊的強度。算法中各變換均為可逆變換，降低了解密過程的實現代價，字節替代變換起到混淆作用，提高差分均勻性，行移位和混合列變換都屬于線性混合運算，確保多輪迭代運算的高度擴散性。Rijndael算法是將安全、高效、性能及靈活性集于一體，并且在不同的硬件和軟件運行環境中都表現出始終如一的良好性能，這使它成為AES的合適選擇。也正是因為這些優點，Rijndael在當前LTE系統中得到廣泛的應用。

[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.