基于AES的短分組加密技術(shù)的改進(jìn)

1、 157基于 AES 的短分組加密技術(shù)的改進(jìn)劉連浩,崔 杰,胡睿達(dá),劉上力(中南大學(xué)信息科學(xué)與工程學(xué)院,長沙 410083摘 要:介紹了基于 AES 的短分組加密算法,研究并指出算法中 S 盒的大小對(duì)加密性能有很大影響。通過求逆、作仿射變換構(gòu)造了新的 十進(jìn)制 S 盒,空間是原先的 10倍。將新 S 盒應(yīng)用于短分組加密仿真系統(tǒng)中,分析發(fā)現(xiàn)其增強(qiáng)了算法的抗攻擊能力,提高了算法的安全性。 實(shí)驗(yàn)仿真結(jié)果表明,新 S 盒使加解密的各項(xiàng)擴(kuò)散率指標(biāo)有明顯提高,加密過程中密鑰對(duì)密文的擴(kuò)散率提高了 25%。 關(guān)鍵詞:短分組; AES ; S 盒;加密Improvement on Short-block Encr

2、yption Technology Based on AESLIU Lianhao, CUI Jie, HU Ruida, LIU Shangli(College of Information Science and Engineering, Central South University, Changsha 410083【 Abstract 】 This paper introduces the short-block encryption algorithm based on AES, studies the S-box of the algorithm, and points out

3、that thesize of S-box has great influence on encryption performance. The new decimal S-box is constructed by taking multiplicative inverse and applyingaffine transformation, and its size is 10 times of the original one. And the new S-box is applied in the short-block encryption simulationsystem, and

4、it shows that the new S-box strengthens the resistance of the algorithm against attack and improves the security of the encryption algorithm.Experiments and simulation indicate that the new S-box improves all the diffusion rate, during which thekey to cipher in encryption processincreases by 25 perc

5、ent.【 Key words】 short-block; AES; S-box; encryption計(jì) 算 機(jī) 工 程 Computer Engineering第 33卷 第 14期Vol.33 No.14 2007年 7月July 2007安全技術(shù) 文章編號(hào):1000 3428(200714 0157 03文獻(xiàn)標(biāo)識(shí)碼:A中圖分類號(hào):TP301.6計(jì)算機(jī)適宜處理十六進(jìn)制數(shù),即二進(jìn)制,加密算法一般 針對(duì)十六進(jìn)制數(shù)進(jìn)行設(shè)計(jì),加密通信中密文一般由通信線路 傳送,其加密技術(shù)已很成熟。但在國民經(jīng)濟(jì)的某些應(yīng)用中, 因?yàn)橥ㄐ烹p方?jīng)]有直接聯(lián)系,密文由人傳送,屬于免介質(zhì)通 信,所以對(duì)密文的進(jìn)制和分組長度有很

6、嚴(yán)格的要求,要求短 分組的十進(jìn)制密文能表示最大信息量。如在預(yù)付費(fèi)代碼表計(jì) 等應(yīng)用中對(duì)密文就作如此要求,購買信息的密文為固定長度 12、 16位等十進(jìn)制數(shù),由人傳送和輸入。該短密文要表示購 買量、 表計(jì) ID 、 購買次數(shù)、 信息校驗(yàn)和用身份戶認(rèn)證等信息。 進(jìn)制轉(zhuǎn)換很容易實(shí)現(xiàn),但通過進(jìn)制轉(zhuǎn)換得到的固定長度密文 不能表示最大信息量。如 6位十六進(jìn)制數(shù),其十進(jìn)制數(shù)的最 高位只能為 0到 4。因此,進(jìn)制轉(zhuǎn)換得到的十進(jìn)制數(shù)密文不 能表示最大信息量。此外,短分組加密應(yīng)用 (如預(yù)付費(fèi)代碼表 計(jì) 中要求同一明文對(duì)于不同的購電次數(shù)或不同表計(jì)加密產(chǎn) 生的密文不同,采用 AES 1,2加密不能滿足這種要求?；?A

7、ES 的短分組加密技術(shù) 3很好地解決了此問題,本文對(duì)其進(jìn) 行了研究,并提出了改進(jìn)方案。1 短分組加密算法的 4種運(yùn)算及加密 /解密文獻(xiàn) 3提出的基于 AES 的短分組加密算法以 AES 為基礎(chǔ),并對(duì) AES 的 4種加密運(yùn)算進(jìn)行重新設(shè)計(jì),以滿足實(shí)際應(yīng) 用中對(duì)短分組加密的要求。 將 AES 中的輪密鑰加改為輪密鑰 運(yùn)算控制,不同的密鑰加密運(yùn)算的輪密鑰運(yùn)算控制算法不一 樣,使加密算法具有隨機(jī)性。提出了動(dòng)態(tài)密鑰的概念,做到 了加密解密一次一密,使加密算法具有混沌加密算法一次一 密的特點(diǎn) 4,5。因此,該算法同時(shí)具有 AES 加密算法、隨機(jī) 加密算法、混沌加密算法的優(yōu)點(diǎn)。下面分別對(duì)短分組加密算 法中的

8、 4種加密運(yùn)算及加密 /解密過程進(jìn)行簡(jiǎn)要介紹。1.1 S盒替換 (S_box文獻(xiàn) 3的短分組加密算法采用的 S 盒是一位十進(jìn)制 S 盒, S 盒的空間為 GF(10,為了使?fàn)顟B(tài)在加 /解密時(shí)得到較好 的擴(kuò)散,該 S 盒替換使替換值與原值有 2bit 的變化。該 S 盒 如圖 1所示。01236849圖 1 S盒替換表1.2 行移位 (ShiftRows表 1中 Nb 為狀態(tài) state 的列數(shù), c i 為第 i 行移位的位數(shù)。 狀態(tài)根據(jù)實(shí)際使用情況可分為 8位、 12位、 16位、 20位、 24位、 28位、 32位等十進(jìn)制數(shù)。狀態(tài)中最后 3行循環(huán)移位 的位數(shù)如表 1所示,即第 0行不移位

9、,第 1行移位 c 1位數(shù), 第 2行移位 c 2位數(shù),第 3行移位 c 3位數(shù)。對(duì)與小于 4列和大 于 7列的狀態(tài)移位要進(jìn)行特殊處理。表 1 位移量與狀態(tài)列數(shù)的關(guān)系Nbc 1c 2c 3 說明2 1238位狀態(tài),第 2列循環(huán)向上移 1位3 12 該行與第 0行交換 12位狀態(tài) 4 12 3 16位狀態(tài) 5 12 3 20位狀態(tài) 8 13 4 32位狀態(tài) 158 1.3 列混合 (MixColumnAES 列混合中的按位異或加對(duì)于十進(jìn)制數(shù)沒有可逆性, 文獻(xiàn) 3短分組加密算法的列混合采用線性列混合的加密方 法。加密時(shí)對(duì)每一列的數(shù)據(jù)進(jìn)行列混合處理,得到的結(jié)果放 回到原來的矩陣中。記加密中列混合矩陣

10、為 A ,解密中逆列混合矩陣為 B ,A 和 B 是互逆正整數(shù)矩陣 1, 即 A *B = E mod 10(E 為單位矩陣 。該短分組加密算法采用的列混合矩陣見式 (1。 00 11 22 3353211523mod 1021533215c c c c c c c c s s s s s s s s =(1該短分組加密算法采用的逆列混合矩陣見式 (2。 00 11 22 3359433594mod 1042599435c c c c c c c c s s s s s s s s =(21.4 輪密鑰運(yùn)算控制 (ControlRoundKey由于異或運(yùn)算對(duì)于十進(jìn)制數(shù)沒有可逆性,因此該短分組

11、加密算法將 AES 輪密鑰加改為輪密鑰運(yùn)算控制。 輪密鑰運(yùn)算 控制程序有 4個(gè)入口,不同的入口對(duì)應(yīng)不同的運(yùn)算。入口由 每一輪加密運(yùn)算所使用密鑰的按位的和模上 4來確定 3。每 一輪加密所用的密鑰是由密鑰擴(kuò)展函數(shù)根據(jù)上一輪加密所用 的密鑰擴(kuò)展得到。1.5 短分組加密算法的加密 /解密用 C 代表 ControlRoundKey , B 代表 S_box, S 代表 ShiftRows , M 代表 MixColumn ,加密流程如下:C BSMC BSMC BSC由于該短分組加密運(yùn)算中采用的每一種運(yùn)算都是可逆的,因此解密流程如下:C -1S -1B -1 C -1M -1S -1B -1 C -

12、1M -1S -1B -1 C -12 新 S 盒的設(shè)計(jì)基于 AES 的短分組加密算法的 S 盒運(yùn)算是一個(gè)獨(dú)立作用 于狀態(tài)單元的非線性變換,文獻(xiàn) 3中短分組加密算法采用的 是一位十進(jìn)制 S 盒,其 S 盒空間為 GF (10,由于該 S 盒的運(yùn) 算域比 AES 的 S 盒 GF (256小得多,因此 S 盒的非線性和擴(kuò) 散性并非很高。從安全性的角度考慮,目前對(duì) AES 最為可行 的攻擊方法就是設(shè)計(jì)者自己提出的 Square 攻擊, 該短分組加 密算法和 AES 具有類似的結(jié)構(gòu),算法的行移位、列混合和輪 密鑰運(yùn)算控制的基本加密運(yùn)算域是一位十進(jìn)制數(shù),如果 S 盒 運(yùn)算也采用一位十進(jìn)制數(shù)替換,就很容

13、易使用改進(jìn)的 Square 攻擊算法對(duì)其實(shí)施攻擊, 并且攻擊的復(fù)雜度大大低于 AES 的 相應(yīng)攻擊,其安全性受到一定的威脅。為了有效提高該加密 算法的擴(kuò)散性和安全性,本文設(shè)計(jì)了一種新的、兩位十進(jìn)制 數(shù) S 盒, S 盒的空間為 (100GF 。新 S 盒運(yùn)算包括在有限域(100GF 中的求乘法逆運(yùn)算和在域 (10GF 下的仿射變換運(yùn)算兩個(gè)步驟。 其中, 求逆運(yùn)算是將兩位十進(jìn)制數(shù)看作域 (100GF 的元素,求其在十進(jìn)制不可化約多項(xiàng)式 2( 1m x x =+下的逆,而仿射變換是求逆結(jié)果與 (10GF 上矩陣 M 相乘然后與向量 I 相加。其中, M =2111;向量 I =(2,3T 。 S

14、盒運(yùn)算具體過程 如下:(1在 GF (102 域,求乘法的逆運(yùn)算,即對(duì)于 GF (102求 GF (102 ,使 2( 1mod 1x =+;(2在 GF (10域作仿射變換: (1100212113y x y x =+ 通過計(jì)算得到 GF (102 域上各個(gè)元素的逆元。 規(guī)定 0元素的逆為其自身。經(jīng)過仿射變換,得到的新 S 盒如表 2所示。表 2 新兩位十進(jìn)制 S 盒Y97344847282 25 65 10 1628從表 2可以看出, GF (102 域上各個(gè)元素的 S 盒替換值遍歷整個(gè) GF (102 空間。 通過作仿射變換, 很好地消除了不動(dòng)點(diǎn) 和對(duì)立不動(dòng)點(diǎn)。3 S盒改進(jìn)前后加密性能比

15、較3.1 S盒改進(jìn)前后加密算法安全性比較文獻(xiàn) 3短分組加密算法是以 AES 為基礎(chǔ)設(shè)計(jì)的, 秉承了 AES 的許多特點(diǎn)。該算法每一輪的加密分為 S 盒替換、行移 位、列混合和輪密鑰運(yùn)算控制 4個(gè)步驟。加密運(yùn)算的基本域 是狀態(tài)中的一位十進(jìn)制數(shù)。目前, Square 攻擊是對(duì) AES 最為 有效的攻擊方法。經(jīng)研究發(fā)現(xiàn),對(duì)于此短分組加密算法可以 使用改進(jìn)的 square 算法進(jìn)行攻擊。 描述改進(jìn) square 攻擊算法, 需要定義 2個(gè)概念:集和平衡。定義 1 集是一個(gè)包含 101個(gè)狀態(tài)的集合,這些狀態(tài)在 某些十進(jìn)制位 (稱為活動(dòng)位 上兩兩互異 (遍歷位所有可能取 值 ,而在其他位 (稱為非活動(dòng)位

16、上則完全相同。亦即對(duì)任意 狀態(tài) , A B 有, , , , , , i ji j i j i j A B i j A B i j = 若(位置上是活動(dòng)位 若(位置上是非活動(dòng)位一個(gè)有 k 個(gè)活動(dòng)位的 集記為 k 集。定義 2 包含 110個(gè)狀態(tài)的集合 P 在某個(gè)位置 (i , j 上是平衡 的,當(dāng)且僅當(dāng)所有狀態(tài)該位置上的位模 10加結(jié)果為 0或 5,即位 (i , j 是平衡的 , A P 0(mod5 i j A =+。 顯然, 集的活動(dòng)位是平衡的,但某個(gè)位置上的位是平 衡的并不意味著該位是活動(dòng)的。改進(jìn)的 Square-4攻擊要求選擇 10個(gè)明文構(gòu)成一個(gè) 1集, 記為 0P 。經(jīng)過初始輪輪密

17、鑰運(yùn)算控制、第 1輪的 S 盒替換及 行移位后, 0P 經(jīng)運(yùn)算產(chǎn)生的中間結(jié)果仍舊構(gòu)成一個(gè) 1集。 但 由于列變換的擴(kuò)散性,列混合使活動(dòng)性擴(kuò)散到此列所有位單 元上,因此第 1輪變換的結(jié)果是一個(gè) 4集, 4個(gè)活動(dòng)位在同 一列上。第 2輪行移位后, 4個(gè)活動(dòng)位分散到 4列上,列混合的結(jié)果是一個(gè) 16集。因?yàn)榛顒?dòng)位的線性疊加結(jié)果并不意味 著是活動(dòng)的, 所以第 3輪列混合的結(jié)果可能不再是一個(gè) 集。但由于 S 盒替換和行移位都是一一映射,并且線性的列混合 和輪密鑰運(yùn)算控制都不影響平衡性。第 3輪結(jié)果 3P 即第 4輪 輸入的 16位狀態(tài)仍舊是平衡的。 經(jīng)過第 4輪 S 盒替換的非線性運(yùn)算,這些位的平衡性被

18、破壞了。這種平衡性的變化可用 于猜測(cè)第 4輪的輪密鑰?？梢?改進(jìn)的 Square 攻擊完全可以攻擊簡(jiǎn)化的 4輪、 5輪及 6輪短分組加密算法,并且攻擊的時(shí)間復(fù)雜度和數(shù)據(jù)復(fù) 雜度都遠(yuǎn)遠(yuǎn)低于 AES 的相應(yīng)攻擊,因此采用一位十進(jìn)制數(shù) S 盒的加密算法安全性受到一定的威脅。將新的 S 盒應(yīng)用于此短分組加密算法中能夠很好地提高 其安全性。由于新 S 盒是兩位十進(jìn)制數(shù)的 S 盒,因此 S 盒運(yùn) 算對(duì)狀態(tài)中的兩位十進(jìn)制數(shù)一起操作,即 S 盒替換的基本運(yùn) 算域是兩位十進(jìn)制數(shù)。而行移位、列混合及輪密鑰運(yùn)算控制 的基本運(yùn)算域是一位十進(jìn)制數(shù)。在第 1輪加密后,1P 狀態(tài)中 的某些位的活動(dòng)性和平衡性可能已經(jīng)遭到破壞

19、,這樣就無法 直接采用改進(jìn)的 Square 攻擊算法進(jìn)行攻擊, 從而大大增加了 Square 攻擊的難度, 提高了該短分組加密算法的抗 Square 攻 擊能力,安全性得到增強(qiáng)。通過研究發(fā)現(xiàn),改變 S 盒的大小 或者改變行移位的運(yùn)算域, Square攻擊所利用的平衡性將不 再存在,從而可以提高加密算法的抗 Square 攻擊能力,而該 結(jié)論同樣適用于 AES 。3.2 S盒改進(jìn)前后加密解密擴(kuò)散率比較將新的兩位十進(jìn)制 S 盒替換文獻(xiàn) 3中短分組加密算法 原有的 S 盒,并對(duì)替換前后的加密解密擴(kuò)散率進(jìn)行了軟件仿 真測(cè)試分析,分別以 12位、 16位、 20位、 32位十進(jìn)制數(shù)為 加密分組,進(jìn)行 2

20、到 15輪的加密解密運(yùn)算測(cè)試。下面是 20位十進(jìn)制數(shù)為加密分組所得測(cè)試比較結(jié)果。改進(jìn)前后加密過 程中明文對(duì)密文擴(kuò)散率比較結(jié)果如圖 2所示,密鑰對(duì)密文擴(kuò) 圖 2 明文對(duì)密文擴(kuò)散率比較結(jié)果圖 3 密鑰對(duì)密文擴(kuò)散率比較結(jié)果改進(jìn)前后解密過程中密文對(duì)明文擴(kuò)散率比較結(jié)果如圖 4所示,密鑰對(duì)明文擴(kuò)散率比較結(jié)果如圖 5所示?？梢钥闯?增大 S 盒后,加密解密擴(kuò)散率的各項(xiàng)指標(biāo)均 有 明 顯 提 高 。 其 中 加 密 過 程 中 明 文 對(duì) 密 文 擴(kuò) 散 率 提 高 了 3.3%,密鑰對(duì)密文擴(kuò)散率提高了 25%;解密過程中密文對(duì)明 文擴(kuò)散率提高了 1%,密鑰對(duì)明文擴(kuò)散率提高了 1.5%。由此 得出, 加密性能很大程度上取決于 S 盒的大小。 在存儲(chǔ)空間、 運(yùn)算速度等條件允許的情況下,適當(dāng)?shù)卦龃?S 盒使加解密過 圖 5 密鑰對(duì)明文擴(kuò)散率比較結(jié)果4 結(jié)論本文簡(jiǎn)要介紹了基于 AES 的短分組加密