，，

(1.湖北師范大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黃石 435002；2.湖北師范大學(xué) 物理與電子科學(xué)學(xué)院)

引 言

AES算法能夠取代DES作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)，原因就在于 AES不僅全面繼承了DES的優(yōu)點，還彌補了DES存在的不足。AES比DES更安全，它能夠抵抗目前已知的大部分攻擊；AES算法在大多的平臺上都可以實現(xiàn)，且代碼比較緊湊，運行速度也很快。然而AES算法還是有著自身的不足，諸如S盒的結(jié)構(gòu)需進一步優(yōu)化，加、解密結(jié)構(gòu)不對稱，擴展密鑰安全性不夠等。針對AES算法的這些不足，本文提出了一些改進措施，然后通過系統(tǒng)仿真軟件在一個最小單片機系統(tǒng)上對改進前和改進后的AES算法進行了比較研究。

1 AES算法簡介

AES算法[1]中最重要的部分之一就是輪函數(shù)，輪函數(shù)一共包括4種計算部件，分別是字節(jié)代換(ByteSub)、行移位(ShiftRow)、列混合(MixColumn)、密鑰加(AddRoundKey)。這4種部件可以看成是輪函數(shù)的3個層，即線性混合層、非線性層、密鑰加層。每個層都有各自獨立的功能。線性混合層是為了保證多次輪變換的高度擴散；非線性層是將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用；密鑰加層是對中間狀態(tài)實施的一次性掩蓋。

1.1 字節(jié)代換

字節(jié)代換的過程分兩步進行：第一步，將字節(jié)用多項式的形式來表示，然后映射到自己的乘法逆元；第二步，映射完之后，再對字節(jié)做出仿射變換。

逆字節(jié)代換的過程[2]也是分兩步進行的：先進行上述仿射變換的逆變換；再求每一個字節(jié)在有限域GF(28)上的逆元。

1.2 行移位

行移位就是對狀態(tài)中的各行進行循環(huán)左移，這是一種線性運算[3]。State矩陣有4行Nb列，現(xiàn)設(shè)置從第0行到第3行循環(huán)左移的字節(jié)數(shù)分別為C0、C1、C2、C3，其中C0是恒等于0的。C1、C2、C3與Nb的關(guān)系如表1所列。

表1 位移量與列數(shù)的函數(shù)

逆行移位就是對狀態(tài)矩陣的后3列分別以Nb-C1、Nb-C2、Nb-C3個字節(jié)數(shù)來進行循環(huán)移位。

1.3 列混合

在列混合變換中，需要將狀態(tài)矩陣中的每一列視為一個向量[4]，把它看成是系數(shù)在有限域GF(28)上的多項式，然后再和多項式c(x)進行模M(x)相乘。c(x)和M(x)的表達式如下：

c(x)=03x3+01x2+01x+02

M(x)=x4+1

列混合變換可以用矩陣乘法來表示，即

逆列混合變換的運算是相似的，現(xiàn)直接用矩陣乘法來表示如下：

1.4 密鑰加

密鑰加的運算[5]就是將輪密鑰與狀態(tài)陣列對應(yīng)位的字節(jié)進行位異或。輪密鑰陣列則是通過種子密鑰經(jīng)密鑰編排算法得到的，密鑰加運算的逆過程就是其自身。

2 AES算法的改進

AES算法的S盒可以說是唯一的非線性部件，因此，S盒的好壞[6]將直接影響算法的性能。根據(jù)研究可知，S盒滿足平衡性，非線性度為112，嚴(yán)格雪崩準(zhǔn)則距離為432，差分均勻度為4，仿射變換對周期為4。總的來說，S盒的性質(zhì)[2]還是不錯的。不過，S盒的仿射變換對周期最大可以取到16，其次是8，標(biāo)準(zhǔn)算法選用的是周期為4的仿射變換對；迭代輸出周期不大于88，代數(shù)表達式僅有9項，存在周期過小、項數(shù)過短的不足。此外，AES算法中加密解密輪變換順序不一致給算法的實現(xiàn)帶來了不便；擴展密鑰中存在著前后輪密鑰關(guān)聯(lián)性過強、易推導(dǎo)的缺陷?，F(xiàn)從以下3個方面對算法做出改進。

2.1 S盒上的改進

AES算法的S盒之所以存在上述不足，主要與選用的仿射變換對和S盒構(gòu)造方式有關(guān)。所以，現(xiàn)提出一種新S盒的構(gòu)造，新S盒的構(gòu)造分如下3步進行：

① 選用仿射變換對(‘6B’，‘5D’)進行仿射變換：

② 進行乘法求逆。

③ 再進行一次步驟①的仿射變換。

逆S盒的構(gòu)造方式與S盒是一樣的，(‘6B’，‘5D’)的逆仿射變換對為(‘70’，‘4A’)，逆仿射變換定義為：

2.1.1 新S盒代換表

有限域GF(28)中一共只有256個元素，如果把這256個元素全部進行一遍改進后的字節(jié)代換，對應(yīng)的結(jié)果繪制成表格，就可以得到新S盒代換表。

2.1.2 新舊S盒對比

舊S盒與改進后的新S盒密碼性質(zhì)對比如表2所列。

表2 新舊S盒性能對比

比較結(jié)果表明，改進后的新S盒既保留了原S盒的優(yōu)點，又彌補了原S盒在仿射變換周期、迭代輸出周期、表達式項數(shù)過短上的缺點。

2.2 結(jié)構(gòu)上的改進

2.2.1 加密結(jié)構(gòu)上的改進

在分組長度為128位的AES算法中，迭代輪數(shù)Nr為10。前9輪的輪變換順序都是一樣的，依次進行字節(jié)代換BS、行移位SR、列混合MC、密鑰加AK?，F(xiàn)將前9輪變換中行移位和列混合操作進行合并，設(shè)某輪字節(jié)代換后的狀態(tài)為S1，該輪密鑰加之前的狀態(tài)為S2，則：

如果將矩陣S1和S2看成是一維數(shù)組的話，那么上述的運算經(jīng)過變形就可以改為：

2.2.2 解密結(jié)構(gòu)上的改進

在AES加解密算法中，輪函數(shù)的4個部件計算順序并不相同，這導(dǎo)致加解密對應(yīng)著不同的模塊，給算法的實現(xiàn)帶來了不便。加解密過程中輪變換的順序如圖1所示。

圖1 AES加解密過程輪變換順序

針對這一問題，可以調(diào)整解密輪變換的順序，使得加解密輪變換順序保持一致。InvShiftRow和InvByteSub的交換比較容易理解，現(xiàn)給出AddRoundKey和InvMixColumn可以交換的證明，設(shè)狀態(tài)矩陣為X，該輪的輪密鑰為W，如下：

調(diào)整解密算法的輪變換順序后，也可以合并逆行移位和逆列混合操作，現(xiàn)直接給出結(jié)果(見下頁)：

2.3 密鑰擴展上的改進

在原密鑰擴展算法中，最初的Nk個字就是種子密鑰，之后的每Nk個字都是由前Nk個字遞歸得到。由擴展密鑰的生成過程可以得出，雖然每一輪密鑰的生成都經(jīng)過了復(fù)雜的變換，但該輪密鑰與上一輪密鑰間有著密切的關(guān)聯(lián)。如果截獲了某一輪密鑰，逆推出上一輪密鑰只需要窮舉232次。因此，現(xiàn)在提出一種新的密鑰擴展方式。

2.3.1 新密鑰擴展方式

新密鑰擴展方式原理如圖2所示。

圖2 新密鑰擴展方式原理圖

在原密鑰擴展算法中，Wi+1、Wi+2、Wi+3都是采用同一種方式生成，而這正是它脆弱的地方?，F(xiàn)保持原算法中其他過程不變，僅改變Wi+1、Wi+2、Wi+3的生成方式。Wi+1由Wi-3和Wi-2異或得到，Wi+2又由生成的Wi+1與Wi異或得到，Wi+3就由Wi+1和Wi+2異或得到。最后，再補加一個Wi+2的外輪循環(huán)移位。

2.3.2 新舊密鑰擴展算法對比

將原密鑰擴展算法和改進后的算法在Keil環(huán)境下用單片機C語言來實現(xiàn)，單片機的型號為AT89C55，CPU的頻率為12 MHz，模擬得出算法的性能對比，對比結(jié)果如表3所列。

表3 密鑰擴展算法改進前后對比

3 仿 真

Proteus是一款常見的系統(tǒng)仿真軟件，現(xiàn)將原AES標(biāo)準(zhǔn)算法和改進算法用Proteus進行仿真，測試改進前后算法的性能。T1和T2分別表示改進前后算法中密鑰擴展函數(shù)運行所花費的時間(ms)，S1和S2分別表示改進前后算法在單片機中所占據(jù)的空間大小(KB)。改進前后算法的仿真運行分別如圖3和圖4所示。

圖3 改進前AES算法的仿真

圖4 改進后AES算法的仿真

通過在相同的硬件和軟件環(huán)境下仿真運行，標(biāo)準(zhǔn)AES算法運行所占據(jù)的空間大小為6.025 KB，其中密鑰擴展函數(shù)代碼執(zhí)行所花費的時間為45.46 ms，而改進后算法運行所占據(jù)的空間大小為5.996 KB，密鑰擴展函數(shù)代碼執(zhí)行所花費的時間為45.37 ms。

結(jié) 語

周炳(碩士研究生)，主要研究方向為信息與智能計算。通信作者：洪家平(教授)，碩士生導(dǎo)師。