基于AES的短分組加密技術的改進

1、 157基于 AES 的短分組加密技術的改進劉連浩,崔 杰,胡睿達,劉上力(中南大學信息科學與工程學院,長沙 410083摘 要:介紹了基于 AES 的短分組加密算法,研究并指出算法中 S 盒的大小對加密性能有很大影響。通過求逆、作仿射變換構造了新的 十進制 S 盒,空間是原先的 10倍。將新 S 盒應用于短分組加密仿真系統(tǒng)中,分析發(fā)現(xiàn)其增強了算法的抗攻擊能力,提高了算法的安全性。 實驗仿真結果表明,新 S 盒使加解密的各項擴散率指標有明顯提高,加密過程中密鑰對密文的擴散率提高了 25%。 關鍵詞:短分組; 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計 算 機 工 程 Computer Engineering第 33卷 第 14期Vol.33 No.14 2007年 7月July 2007安全技術 文章編號:1000 3428(200714 0157 03文獻標識碼:A中圖分類號:TP301.6計算機適宜處理十六進制數(shù),即二進制,加密算法一般 針對十六進制數(shù)進行設計,加密通信中密文一般由通信線路 傳送,其加密技術已很成熟。但在國民經濟的某些應用中, 因為通信雙方沒有直接聯(lián)系,密文由人傳送,屬于免介質通 信,所以對密文的進制和分組長度有很

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

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

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

9、,第 1行移位 c 1位數(shù), 第 2行移位 c 2位數(shù),第 3行移位 c 3位數(shù)。對與小于 4列和大 于 7列的狀態(tài)移位要進行特殊處理。表 1 位移量與狀態(tài)列數(shù)的關系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 列混合中的按位異或加對于十進制數(shù)沒有可逆性, 文獻 3短分組加密算法的列混合采用線性列混合的加密方 法。加密時對每一列的數(shù)據(jù)進行列混合處理,得到的結果放 回到原來的矩陣中。記加密中列混合矩陣

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 輪密鑰運算控制 (ControlRoundKey由于異或運算對于十進制數(shù)沒有可逆性,因此該短分組

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

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

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

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

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

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

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

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

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

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