S盒密碼性質的測試與研究

范巍

（河南牧業經濟學院＜英才校區＞計算機應用系，河南 鄭州 450044）

S盒密碼性質的測試與研究

范巍

（河南牧業經濟學院＜英才校區＞計算機應用系，河南 鄭州 450044）

本文介紹了S盒的設計準則和構造方法，并利用程序實現了非線性度、擴散準則、雪崩效應、差分均勻性這幾個設計準則。利用上述程序對現代主流的幾個分組密碼進行了分析和測試，主要就非線性度、差分均勻度、雪崩效應、擴散特性以及可逆性對其中的S盒進行了分析和討論。此外，在上述基礎上，本文采用有限域上的冪函數和逆函數線性組合的方式構造S盒。對得到的S盒的密碼性質進行了分析和討論，并與現代主流密碼的S盒進行比較。

S盒；非線性度；差分均勻度；擴散特性；雪崩效應

1 緒論

分組密碼是現代密碼的一個重要分支，自從其誕生以來，三十多年間人們從未停止過對其的研究。不論是理論還是應用，密碼學家在這期間都取得了極大的進展。分組密碼的設計和安全性研究既相互對立又相互促進，從而也讓分組密碼有長足的進展。然而分組密碼設計原理的完善并沒有澆滅密碼學家對于分組密碼安全性的熱情，反而更加激發了密碼學家們的興趣。密碼學家們的興趣最終導致分組密碼攻擊方法的日趨多樣性。從差分分析到高階差分分析[1]，從線性攻擊到截斷差分-線性攻擊[2]，經典的攻擊方法之間的重組創造出了新的攻擊方法。大多數的分組密碼采用混淆加上迭代的結構，其中S盒是大多數分組密碼中混淆的關鍵。因此，從某種意義上講，分組密碼的安全性依賴于S盒的密碼特性。也正是由此，越來越多的攻擊方法被提出也給S盒帶來了越來越大的挑戰，這也使得對于S盒性質的研究獲得了密碼學家們的極大關注。

2 相關研究

從S盒的輸入輸出的角度來看，S盒可以看作是多輸出布爾函數，因此對于S盒的研究可以通過布爾函數的一些研究方法來實現。布爾函數的相關理論和結果能夠對S盒的研究提供很好地指引作用。因此，S盒的很多密碼性質是由布爾函數的相關性質推廣而來。

隨著S盒研究的深入，一個很現實有很重要的問題出現在密碼學家們的眼前，即如何全面的衡量S盒的優劣。于是很多密碼學家又致力于對于S盒設計準則的研究，發表了大量的文獻資料[6-10]，這些文獻中給出了S盒的一些設計準則。事實上可以發現，很多S盒的設計準則來源布爾函數的相關性質。線性攻擊的出現，使得非線性度這個概念對于分組密碼日益重要。由于這種攻擊方法的本質是用線性函數去逼近加密算法，而對于S盒的線性逼近是否有效直接關系到攻擊成功與否。

3 S盒構造設計與主流算法性質研究

3.1 S盒構造方法。S盒的設計準則較多，有些設計準則之間相互限制，因此滿足所有準則的S盒幾乎是不存在的。所以，可以根據實際情況對S盒某些指標的要求不需要那么嚴格。例如，對于采用SP結構的分組密碼，由于其良好的擴散性能，在這種情況下可以適當降低對S盒擴散性的要求。其一，隨機選取并測試。由于規模較小的S盒的安全性可能得不到保障，因此，在隨機生成S盒時往往生成規模較大的S盒，以確保S盒以較大的概率具有較好的密碼性質[8]。其二，按照一定規則構造并測試使用這種方法的一個重要前提是現有的性質良好的S盒，然后通過設計者設定的一些規則來改進S盒。其三，利用密碼結構。大多數情況下，這種方法以規模較小的S盒，通過特定的密碼結構，以構造性質優良的且規模較大的S盒。此種方法構造的S盒通常可以用較低的硬件代價實現，對于一些資源受限的應用此種方式構造的S盒更容易滿足要求。其四，利用遺傳算法構造并測試所謂的遺傳算法，就是利用兩個舊的S盒生成新的S盒，并對新產生的S盒進行淘汰：只選取性質更加優良的S盒，讓其有權力生成新的S盒。這樣可以使得好的性質一步步聚集起來，從而產生一些密碼特性良好的S盒。其五，數學函數。使用這種方法的好處是：S盒的性質可以從理論上證明。目前常用的此類S盒由指數函數、對數函數、有限域上的逆和冪函數、混沌映射。其六，不同群中數學函數的復合。不同群的數學函數的符合在抵抗差值攻擊和高階差分攻擊方面時有效地。按照一定的規律選取參數，例如選取是奇數和可以保證S盒是雙射。

3.2 現代主流分組密碼的S盒性質研究。分組密碼中大多數用到了S盒，而S盒的一個重要作用是對明文進行混淆。混淆的程度也在一定程度上影響著這些分組算法的加密強度和安全性。因此，對于現有S盒的密碼性質的研究將為設計出更好地S盒提供重要的依據。其一，AES算法。AES算法的S盒是由限域上逆映射并加上仿射變換得到的，這種方法設計充分保證了S盒的差分均勻度、線性偏差以及較高的代數次數。因為AES算法的S盒是一個置換，因此其一定是平衡的。對其輸入改變1比特來觀察其輸出的改變比特的概率，可以看出AES算法的S盒并不符合完全雪崩效應和一階擴散準則，其完全雪崩距離為432，但是可以看出關于任何一個元素其與符合雪崩效應的差距并不是很大，也即當輸入改變1比特時輸入每一比特取反的概率都很接近0.5。非線性度一定程度上反映了S盒抵抗線性密碼分析攻擊的能力，而bent函數具有最高的非線性度，計算可以得到AES算法S盒的非線性度為112已經十分接近bent函數。AES S盒的差分均勻度為4，說明AES算法S盒對于差分攻擊具有良好的抵抗能力。其二，Camellia算法。Camellia算法對其他較為復雜的攻擊方法也具有很好地抵抗能力。此外，Camellia算法有一個很大的特點：每隔一定的輪數使用不同的函數以增加不確定性。Camellia算法中的S盒并不滿足完全雪崩效應和一階擴散準則，但是在輸入改變1比特的情況下輸出比特改變的比例都比較接近0.5，因此其也具有較好的雪崩效應。Camellia算法的S盒的完全雪崩距離為308，比AES算法S盒更優。S盒的非線性度和差分均勻度分別是112和4，這和AES算法S盒是一致的。其三，SMS4算法。SMS4算法是一個典型的分組密碼算法，具有128比特的分組長度，而且其密鑰長度與之相同。SMS4算法采用的迭代輪數比一般的分組密碼都多：32輪。SMS4算法 S盒并不滿足完全雪崩效應和一階擴散準則，但是在輸入改變1比特的情況下輸出比特改變的概率都比較接近0.5，因此其也具有較好的雪崩效應。SMS4算法的S盒的完全雪崩距離為492，較AES算法S盒和camellia算法S盒都差。SMS4算法S盒的非線性度和差分均勻度分別是112和4，這和AES算法、Camellia算法S盒是一致的。其四，ARIA算法。ARIA算法的明文分組長度以及密鑰比特的長度均與AES算法一致。算法迭代的輪數根據密鑰長度不同而不同分別為：12、14和16。ARIA算法的整體結構為SP結構，每一輪由加輪密鑰、混淆層和擴散層構成。

ARIA算法中的S盒并不滿足完全雪崩效應和一階擴散準則但是在輸入改變1比特的情況下輸出比特改變的概率都比較接近0.5，因此其也具有較好的雪崩效應。ARIA算法的S盒的完全雪崩距離為400，較AES算法S盒和Camellia算法S盒都差，但是優于SMS4算法S盒。ARIA算法S盒的非線性度和差分均勻度分別是112和4，這和AES算法S盒、Camellia算法S盒以及SMS4算法S盒是一致的。

因此，我們采用與AES算法相同的方式構造一個有限域GF（28），記作GF并首先研究GF上的單獨一個冪函數f（x）=xe的性質，主要包括可逆性、平衡性、非線性度、雪崩效應、擴散特性。單獨一個冪函數的形式并不能很好地滿足加密算法對于S盒密碼性質的要求，于是采取逆函數和冪函數相異或的形式來構造S盒，即S（X）=x-1+xe。這有以下好處：首先這樣可以使得S盒的代數表達式更加復雜，其次異或運算可以提高S盒的非線性程度。由于S盒在具體的分組算法中要求是可逆的，通過計算具有上述形式且可逆的S盒的非線性度、雪崩效應以及擴散特性的指標如表1：

表 1 逆函數和冪函數線性組合生成S盒密碼性質

表 2 AES算法S盒和兩個冪函數線性組合生成S盒密碼性質

通過上述方法仍然無法獲得性質較好的S盒并且可逆S盒的數量過少，于是采取逆函數與兩個冪函數相異或的構造方法，并將原來的逆函數變換成AES中經過仿射變換后的S盒，可以一些性質更為良好的S盒，具體情況如表2：

該S盒并不滿足完全雪崩效應但是在輸入改變1比特的情況下輸出比特改變的概率都比較接近0.5，因此其也具有較好的雪崩效應。S盒的完全雪崩距離為380，優于AES算法、SMS4算法和ARIA算法的S盒，并且與Camellia算法S盒的差距也不是很大。該S盒的非線性度和差分均勻度分別是112和4，這和AES 算法S盒、ARIA算法S盒、Camellia算法S盒以及SMS4算法S盒是一致的。

上述的測試說明按照上述設計準則，利用有限域冪函數和逆函數通過異或運算組合的構造方法確實能夠產生性質良好的S盒。

4 結論

本文對S盒的設計準則和構造方法進行了總結和討論，并對現有主流分組密碼中的S盒就非線性度、雪崩效應以及擴散特性等性質做了分析與研究。然后在通過本原多項式構造的有限域的基礎上，采用逆函數與冪函數線性組合的方式構造S盒。最后研究這些S盒的平衡性、可逆性、非線性度、雪崩效應以及擴散特性等性質，并與現有的主流分組密碼中的S盒進行對比。最終得到密碼特性比較理想的S盒。

[1]胡豫濮，蔡勉，肖國鎮.一類高階差分密碼分析[J].電子學報，1999（10）：74-78.

[2]賀也平，吳文玲，卿斯漢.截斷差分-現行密碼分析[J].軟件學報，2000（10）：94-98.

[3]張麗瓊，呂述望.插值攻擊中的多項式表示[J].通信技術，2003（4）：80-81.

[4]溫巧燕，鈕心忻，楊義先.現代密碼學中的布爾函數[M].北京:科學出版社，2000.

[5]馮登國，吳文玲.分組密碼的設計與分析[M].北京:清華大學出版社，2009.

[6]A.F.Webster and S.E.Tavares，On the Design of S-Boxes. Advances in Cryptology-CRYPTO'85，LNCS 218，pp:523-524. Springer-Verlag，1986.

[7]S.Fischer and W.Meier，Algebraic Immunity of S-Boxes and Augmented Functions.Fast Software Encryption-FSE 2007 LNCS 4593，pp:366-381.Springer-Verlag，2007.

[8]J.A.Gordon and H.Retkin，Are Big S-Boxes Best?IEEE Workshop on Computer Security，pp:257-262，1981.

[9]L.O’Connor，Enumerating Nondegenerate Permutations，Ad?vances in Cryptoogy-EUROCRYPT’91，LNCS 547，pp:368-377.

[10]C.Adams and S.Tavares，The Structured Design of De?sign of Cryptographically Good S-Boxes，Journal of Cryptology，Vol.3，No.1，pp:27-41，1990.

[11]J.Dettombe and S.Tavares，Constructing large cryptograph?ically strong S-Boxes.Advances in Cryptology-Auscrypto’92，LNCS 718，pp:165-181.Springer-Verlag，1993.

[12]Ross J.Anderson，Eli Biham，Lars R.Knudsen.The Case for Serpent.AESCondidate Conference 2000:349-354.

TN918

A

1671-0037（2014）12-86-2

范巍（1982-），男，碩士研究生，助教，研究方向：計算機科學技術與應用。