范巍

（河南牧業(yè)經(jīng)濟學(xué)院＜英才校區(qū)＞計算機應(yīng)用系，河南 鄭州 450044）

S盒密碼性質(zhì)的測試與研究

范巍

（河南牧業(yè)經(jīng)濟學(xué)院＜英才校區(qū)＞計算機應(yīng)用系，河南 鄭州 450044）

本文介紹了S盒的設(shè)計準則和構(gòu)造方法，并利用程序?qū)崿F(xiàn)了非線性度、擴散準則、雪崩效應(yīng)、差分均勻性這幾個設(shè)計準則。利用上述程序?qū)ΜF(xiàn)代主流的幾個分組密碼進行了分析和測試，主要就非線性度、差分均勻度、雪崩效應(yīng)、擴散特性以及可逆性對其中的S盒進行了分析和討論。此外，在上述基礎(chǔ)上，本文采用有限域上的冪函數(shù)和逆函數(shù)線性組合的方式構(gòu)造S盒。對得到的S盒的密碼性質(zhì)進行了分析和討論，并與現(xiàn)代主流密碼的S盒進行比較。

S盒；非線性度；差分均勻度；擴散特性；雪崩效應(yīng)

1 緒論

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

2 相關(guān)研究

從S盒的輸入輸出的角度來看，S盒可以看作是多輸出布爾函數(shù)，因此對于S盒的研究可以通過布爾函數(shù)的一些研究方法來實現(xiàn)。布爾函數(shù)的相關(guān)理論和結(jié)果能夠?qū)盒的研究提供很好地指引作用。因此，S盒的很多密碼性質(zhì)是由布爾函數(shù)的相關(guān)性質(zhì)推廣而來。

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

3 S盒構(gòu)造設(shè)計與主流算法性質(zhì)研究

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

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

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

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

表 1 逆函數(shù)和冪函數(shù)線性組合生成S盒密碼性質(zhì)

表 2 AES算法S盒和兩個冪函數(shù)線性組合生成S盒密碼性質(zhì)

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

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

上述的測試說明按照上述設(shè)計準則，利用有限域冪函數(shù)和逆函數(shù)通過異或運算組合的構(gòu)造方法確實能夠產(chǎn)生性質(zhì)良好的S盒。

4 結(jié)論

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

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

[2]賀也平，吳文玲，卿斯?jié)h.截斷差分-現(xiàn)行密碼分析[J].軟件學(xué)報，2000（10）：94-98.

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

[4]溫巧燕，鈕心忻，楊義先.現(xiàn)代密碼學(xué)中的布爾函數(shù)[M].北京:科學(xué)出版社，2000.

[5]馮登國，吳文玲.分組密碼的設(shè)計與分析[M].北京:清華大學(xué)出版社，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

范?。?982-），男，碩士研究生，助教，研究方向：計算機科學(xué)技術(shù)與應(yīng)用。