面向單片機(jī)及嵌入式系統(tǒng)的AES算法改進(jìn)研究

，，

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

引 言

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

1 AES算法簡(jiǎn)介

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

1.1 字節(jié)代換

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

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

1.2 行移位

行移位就是對(duì)狀態(tài)中的各行進(jìn)行循環(huán)左移，這是一種線性運(yù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ù)

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

1.3 列混合

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

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

M(x)=x4+1

列混合變換可以用矩陣乘法來(lái)表示，即

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

1.4 密鑰加

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

2 AES算法的改進(jìn)

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

2.1 S盒上的改進(jìn)

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

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

② 進(jìn)行乘法求逆。

③ 再進(jìn)行一次步驟①的仿射變換。

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

2.1.1 新S盒代換表

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

2.1.2 新舊S盒對(duì)比

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

表2 新舊S盒性能對(duì)比

比較結(jié)果表明，改進(jìn)后的新S盒既保留了原S盒的優(yōu)點(diǎn)，又彌補(bǔ)了原S盒在仿射變換周期、迭代輸出周期、表達(dá)式項(xiàng)數(shù)過(guò)短上的缺點(diǎn)。

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

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

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

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

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

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

圖1 AES加解密過(guò)程輪變換順序

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

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

2.3 密鑰擴(kuò)展上的改進(jìn)

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

2.3.1 新密鑰擴(kuò)展方式

新密鑰擴(kuò)展方式原理如圖2所示。

圖2 新密鑰擴(kuò)展方式原理圖

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

2.3.2 新舊密鑰擴(kuò)展算法對(duì)比

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

表3 密鑰擴(kuò)展算法改進(jìn)前后對(duì)比

3 仿 真

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

圖3 改進(jìn)前AES算法的仿真

圖4 改進(jìn)后AES算法的仿真

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

結(jié) 語(yǔ)

周炳(碩士研究生)，主要研究方向?yàn)樾畔⑴c智能計(jì)算。通信作者：洪家平(教授)，碩士生導(dǎo)師。