利用多進(jìn)制組合快速構(gòu)造S盒的AES算法設(shè)計

王海龍， 孟繁軍， 張躍軍， 張增平

（1.內(nèi)蒙古師范大學(xué) 網(wǎng)絡(luò)技術(shù)學(xué)院，內(nèi)蒙古呼和浩特 010022；2.內(nèi)蒙古師范大學(xué)計算機與信息工程學(xué)院，內(nèi)蒙古呼和浩特 010022；3.北京政法職業(yè)學(xué)院 信息技術(shù)系，北京 100024）

AES是一種迭代分組密碼，采用的是代替置換網(wǎng)絡(luò)（SPN）。將明文分組長度固定為128b，而且僅支持128、196、256b的密鑰長度，AES加密過程又包括1個作為初始輪的初始密鑰加法（AddRoundKey），接 著 進(jìn) 行 9 次 輪 變 換（Round），最后再使用1個輪變換（FinalRound）。其中包含的SubBytes（）是AES密碼中唯一的非線性變換。字節(jié)代替變換SubBytes（）是可逆的，由2個可逆變換復(fù)合而成。它是一個磚匠置換，該置換包含1個作用在狀態(tài)字節(jié)上的S盒。

目前有關(guān)S盒設(shè)計準(zhǔn)則的研究已經(jīng)有較大的進(jìn)展，其中以文獻(xiàn)［1－2］的工作最具有代表性，字節(jié)代替變換（即S盒變換）是許多分組密碼算法中的唯一非線性部件，它的密碼強度決定了整個分組密碼算法的安全強度，對于分析AES算法的強度具有重要意義。文獻(xiàn)［3］利用有限域上的跡變換，證明了AES算法中S盒的各坐標(biāo)函數(shù)均線性等價。文獻(xiàn)［4］利用布爾函數(shù)的譜分布和自相關(guān)系數(shù)給出了一種求各坐標(biāo)函數(shù)等價變換矩陣的一種方法。

S盒主要提供了分組密碼算法所必須的混淆作用，但如何全面準(zhǔn)確地度量S盒的密碼強度，如何設(shè)計安全有效的S盒是分組密碼設(shè)計和分析中的研究難題［5］。S盒主要有以下一些設(shè)計準(zhǔn)則：非線性度、差分均勻度、代數(shù)次數(shù)及項數(shù)分布、相關(guān)免疫性等［6－8］。基于以上設(shè)計準(zhǔn)則，人們提出了許多構(gòu)造方法，如隨機選取并測試、使用數(shù)學(xué)函數(shù)等方法。隨機選取方法要求設(shè)計者有足夠的時間和計算能力，而使用數(shù)學(xué)函數(shù)可以構(gòu)造一些好的S盒，目前常用的此類S盒有指數(shù)函數(shù)和對數(shù)函數(shù)、有限域GF（2n）上的逆映射以及有限域上的冪函數(shù)［9］。

1 算法設(shè)計

1.1 加解密算法思想

在AES算法加密中，字節(jié)代替變換（Sub－Bytes（））中需要進(jìn)行S盒替換，轉(zhuǎn)換過程描述如圖1a所示。多進(jìn)制組合加密算法理論是建立在多類S盒理論基礎(chǔ)之上的，具體過程可描述為：首先構(gòu)造出一類S盒，再找出這類S盒與十六進(jìn)制的轉(zhuǎn)換關(guān)系（假定這個多進(jìn)制轉(zhuǎn)換為M進(jìn)制轉(zhuǎn)換）；在AES算法的SubBytes（）中狀態(tài)轉(zhuǎn)換時，針對狀態(tài)元素，通過M進(jìn)制轉(zhuǎn)換關(guān)系將Sub－Bytes（）狀態(tài)的值轉(zhuǎn)換成M進(jìn)制，然后再對應(yīng)這個M進(jìn)制的S盒進(jìn)行M進(jìn)制磚匠替換；對替換出來的結(jié)果再進(jìn)行M進(jìn)制的轉(zhuǎn)換，這樣就得到了SubByetes（）想要的結(jié)果［10］。通過多進(jìn)制組合改進(jìn)后的SubBytes（）轉(zhuǎn)換過程如圖1b所示［11］。

在AES算法解密中，逆字節(jié)代替變換（Inv－SubBytes（））同樣也要進(jìn)行相應(yīng)的替換，InvSub－Bytes（）是SubBytes（）的逆變換。它將狀態(tài)中的每一個字節(jié)非線性地變換為另一個字節(jié)，此次的替換是針對逆S盒進(jìn)行的。多進(jìn)制組合解密算法理論的具體過程可描述為：首先構(gòu)造出加密算法中S盒的逆S盒，再找出逆S盒與十六進(jìn)制的轉(zhuǎn)換關(guān)系，假定這個多進(jìn)制轉(zhuǎn)換為M進(jìn)制轉(zhuǎn)換（肯定與加密算法過程中的進(jìn)制相同）；在AES算法的InvSubBytes（）中狀態(tài)轉(zhuǎn)換時，針對狀態(tài)元素，將InvSubBytes（）狀態(tài)的值轉(zhuǎn)換成M進(jìn)制，然后再對應(yīng)這個M進(jìn)制的逆S盒進(jìn)行M進(jìn)制磚匠替換；再對替換出來的結(jié)果進(jìn)行M進(jìn)制的轉(zhuǎn)換，這樣就得到了InvSubByetes（）想要的結(jié)果［9］。

圖1 SubBytes的轉(zhuǎn)換過程

1.2 算法實例

1.2.1 加密實例

首先任意構(gòu)造一個M進(jìn)制的S盒，這里以4×4矩陣的S盒為例來說明。4×4的S盒中字節(jié)替代值見表1所列，字節(jié)代替變換過程中的狀態(tài)初值見表2所列。

表1 4×4S盒－字節(jié)xy的四進(jìn)制代替值

表2 SubBytes（）過程中狀態(tài)初值

表3 SubBytes（）過程中經(jīng)過多進(jìn)制組合后狀態(tài)初值

1.2.2 解密實例

在解密過程中，根據(jù)加密的M進(jìn)制的S盒，構(gòu)造出對應(yīng)的4×4矩陣的逆S盒，見表4所列；InvSubBytes（）過程中狀態(tài)初值見表5所列；Inv－SubBytes（）過程中經(jīng)過多進(jìn)制組合后狀態(tài)初值見表6所列［12－13］。

表4 4×4逆S盒－字節(jié)xy的四進(jìn)制代替值

表5 InvSubBytes（）過程中狀態(tài)初值

表6 InvSubBytes（）過程中經(jīng)過多進(jìn)制組合后狀態(tài)初值

2 算法測試

2.1 模擬實驗

通過C＃語言實現(xiàn)AES算法和利用多進(jìn)制組合的AES算法對圖片進(jìn)行加密解密效果，如圖2a和圖2b所示。

通過模擬實驗，能夠看出多進(jìn)制組合后的AES加密算法與原AES加密算法在對圖像進(jìn)行加密和解密時，能夠得到相同的效果，從而驗證了多進(jìn)制組合AES算法的可行性。

圖2 AES與多進(jìn)制組合對圖像加解密的影響

2.2 測試結(jié)果分析

下面給出原圖、AES算法加密后的圖和經(jīng)過多進(jìn)制組合的AES算法加密后的圖3類圖像的各種通道的直方圖比較效果，如圖3～圖6所示。

通過分析比較各通道直方圖相關(guān)參數(shù)，可得出如下結(jié)果：① 像素均無變化；②2種算法對中間值都有變化，但是變化值相同；③ 平均值和標(biāo)準(zhǔn)偏差變化都不相同。

在平均值上，亮度、綠色和藍(lán)色，多進(jìn)制組合AES算法比原來算法稍微偏高，而紅色偏低。在標(biāo)準(zhǔn)偏差上，亮度、紅色和藍(lán)色，多進(jìn)制組合AES算法比原來算法稍微偏高。

因此，如果把多進(jìn)制組合AES算法應(yīng)用在圖像加密方向上，與原算法相比，更有利于圖像加密，對圖像置亂效果增強。再結(jié)合其他算法，可以達(dá)到更加滿意的效果［14］。

圖3 亮度通道比較

圖4 紅色通道比較

圖5 綠色通道比較

圖6 藍(lán)色通道比較

3 結(jié)束語

針對AES算法中的S盒構(gòu)造問題，本文給出了一種快速構(gòu)造S盒的方法，即多進(jìn)制組合AES算法，通過這種方法可以快速構(gòu)造出各種不同的S盒。

經(jīng)過算法測試實驗和實驗分析，證明此算法設(shè)計較為合理，運算速度得以提高，并在加解密效果上變化不大，有比較廣泛的應(yīng)用前景。

［1］Dawson M H，Tavares S E.An expanded set of design criteria for substitution box and their use in strengthening DES－like cryptosystems［C］／／IEEE Pacific Rim Conference on Communications，Computer and Sigual Processing，1991：191－195.

［2］Dawson M H，Tavares S E.An expanded set of design criteria based on information theory and its relation to differential－like attacks［M］／／Advances in Cryptology：EUROCRYPT’91.Berlin：Springer－Verlag，1991：352－367.

［3］金晨輝，孫 瑩.AES密碼算法S盒的線性冗余研究［J］.電子學(xué)報，2004，32（4）：639－641.

［4］Gligoroski D，Moe M E G.On deviations of the AES S－box when represented as vector valued Boolean function［J］.International Journal of Computer Science and Network Security，2007，7（4）：156－161.

［5］胡 斌，金晨輝.AES算法S盒中的等價線性變換［J］.計算機工程與應(yīng)用，2005（22）：70－72.

［6］馮等國，寧 鵬.S盒的非線性準(zhǔn)則之間的關(guān)系［J］.通信學(xué)報，1998，19（4）：72－76.

［7］馮登國.線性結(jié)構(gòu)與非線性度之間的關(guān)系［J］.電子學(xué)報，2000，28（1）：139－141.

［8］陳令羽，宋國民，徐 齊，等.DES在數(shù)字高程模型信息偽裝中的應(yīng)用研究［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2012，35（2）：189－192，279.

［9］劉曉晨，馮國登.滿足若干密碼學(xué)性質(zhì)的S盒的構(gòu)造［J］.軟件學(xué)報，2000，11（10）：1299－1302.

［10］Nyberg K.Differentially uniform mappings for cryptography［C］／／Helleseth T.Advances in Cryptology，Proc EUROCRYPT’93，LNCS 765.Berlin：Springer－Verlag，1994：55－64.

［11］阮傳概，孫 偉.近世代數(shù)及其應(yīng)用［M］.北京：北京郵電大學(xué)出版社，2001：351－403.

［12］Ziedan I E，F(xiàn)ouad O，Salem D H.Application of data encryption standard to bitmap and JPEG images［C］／／The 20th National Radio Science Conference，2003：16－18.

［13］肖華勇，李建輝.基于AES的S盒圖像置亂算法研究［J］.西北工業(yè)大學(xué)學(xué)報，2008，26（1）：74－77.

［14］楊 釩，薛模根.復(fù)合混沌二級置亂圖像加密算法研究［J］.合 肥 工 業(yè) 大 學(xué) 學(xué) 報：自 然 科 學(xué) 版，2009，32（8）：1128－1131.