基于遺傳蟻群算法的Ｓ盒構(gòu)造

摘要：提出一種基于遺傳蟻群算法的S盒構(gòu)造方法，算法中兩次插入遺傳算法，利用遺傳算法前期收斂速度較快及交叉變異操作避免陷入局部最優(yōu)的特性，加快蟻群算法的收斂速度，提高求解的效率。基于該方法，給出了構(gòu)造S盒的完整算法流程圖，并獲得一批高非線性度和低差分均勻度的S盒。實驗結(jié)果表明，與利用遺傳算法構(gòu)造S盒的方法相比，該構(gòu)造方法能有效地減少冗余計算量、加快收斂速度。

關(guān)鍵詞：蟻群算法;遺傳算法;S盒;構(gòu)造準則

中圖分類號：TP309．7文獻標志碼：A

文章編號：1001-3695(2008)05-1553-03

在多數(shù)分組密碼算法中，S盒都是惟一的非線性部件，其密碼學(xué)特性直接決定密碼算法的安全性。構(gòu)造安全有效的S盒是分組密碼設(shè)計中的重點和難點，常用的構(gòu)造方法有隨機選擇測試、人為構(gòu)造、數(shù)學(xué)方法構(gòu)造[1]。雖然全局搜索可以得到所有好的S盒，但是對于指數(shù)增長的搜索空間來說是不現(xiàn)實的。采用啟發(fā)式算法構(gòu)造S盒可謂不錯的折中方法。張煥國等人[2]提出演化密碼的概念，利用演化算法構(gòu)造分組密碼算法中的S盒，取得了較好的實驗結(jié)果。殷新春等人[3]則利用快速收斂遺傳算法對S盒進行優(yōu)化，給出了一批非線性度較高和差分均勻度較低的6×6的S盒。雖然遺傳算法具有快速隨機的全局搜索能力，但對于系統(tǒng)中反饋信息很難高效地利用，當求解到一定范圍時，往往存在大量無為的冗余迭代，求最優(yōu)解效率較低。



蟻群算法是基于生物界群體啟發(fā)行為的一種隨機搜索尋優(yōu)方法，通過信息素的累積和更新收斂于最優(yōu)路徑上，在解決組合優(yōu)化問題上具有良好的適應(yīng)性。其很強的正反饋能力在算法的后期能夠加快算法的進化速度，促使算法迅速收斂；但在初期信息素匱乏，求解速度慢，而且搜索時間長，易于陷入局部最優(yōu)解。而利用遺傳算法的交叉、變異機制，可以有效地提高蟻群算法跳出局部最優(yōu)的能力[4]。本文提出的算法利用蟻群算法良好的耦合能力，將蟻群算法與遺傳算法相融合。首先采用遺傳算法生成初始信息素分布，再利用蟻群算法和遺傳算法的交叉、變異算子求最優(yōu)解，充分發(fā)揮兩種算法的優(yōu)勢，并將該算法應(yīng)用于分組密碼中S盒的構(gòu)造，對于蟻群算法在密碼學(xué)上的應(yīng)用是一個嶄新的嘗試。

1基本蟻群算法

研究表明：螞蟻在覓食途中，能在所經(jīng)過的路徑上留下一種揮發(fā)性分泌物——信息素，并能感知這種物質(zhì)的存在及其強度，朝著這種物質(zhì)強度高的方向移動；強度越高的路徑，選擇它的螞蟻越多，越發(fā)增加該路徑的信息素強度，這樣又將吸引更多的螞蟻，從而形成一種正反饋，螞蟻最終可以發(fā)現(xiàn)蟻巢與食物之間的最短路徑。蟻群算法首先成功應(yīng)用于旅行商問題，以下以Ant－cycle系統(tǒng)為例簡要介紹其基本原理[5]。

3算法分析與實驗結(jié)果

本文首次將蟻群算法應(yīng)用于S盒的構(gòu)造，證明了利用蟻群算法構(gòu)造S盒是可行的。由于蟻群算法存在的不足，本文兩次利用遺傳算法，其思想基于：a)遺傳算法在前期收斂速度較快，先利用遺傳算法生成一批性能較優(yōu)的S盒，將這批S盒作為螞蟻的初始哈密頓回路，并利用式(8)獲取初始信息量。b）將遺傳算法的交叉、變異算子引入到蟻群算法的每輪循環(huán)遍歷中。如圖2，以蟻群算法每代的優(yōu)化解作為遺傳算法的初始種群，然后用遺傳算法的優(yōu)化子代作為蟻群算法的父代，可以加快蟻群算法的收斂速度，改善其陷入局部最優(yōu)解的不足。

參數(shù)設(shè)置為M=1 024，Q=120，pc=0.35，pm=0.000 5，α=2.8，β=5.2，ρ=0，3，Nmax=1 000。迭代結(jié)果如表2所示。

改變蟻群算法的部分參數(shù)組合，會對本文算法所生成S盒的性能產(chǎn)生一定的影響，結(jié)果如表3所示。

利用本文的算法、基本遺傳和基本蟻群算法分別生成S盒，從這三批S盒中選擇各自性能最優(yōu)的512個S盒。表4顯示了它們以及DES的S盒的平均性能比較。

4結(jié)束語

本文首次提出了基于遺傳蟻群算法構(gòu)造S盒的方法。該方法將螞蟻群體的正反饋機制與生物繁衍的進化思想有機地融合，與文獻[12]的遺傳蟻群算法融合不同在于，本文所提算法起始就先采用遺傳算法來生成初始信息素分布，給出了首批符合正交性待優(yōu)化的S盒，再利用蟻群算法和遺傳算法的交叉、變異算子求最優(yōu)解；與利用遺傳算法構(gòu)造S盒的方法相比，有效地減少冗余計算量、加快收斂速度，充分發(fā)揮了兩種算法的優(yōu)勢。本文還給出了基于該方法的S盒的模型，以及構(gòu)造S盒的完整算法流程圖，并獲得了一批高非線性度和低差分均勻度的S盒。本文是蟻群算法在密碼學(xué)上的一種嘗試，從仿真結(jié)果來看，基于蟻群算法構(gòu)造S盒是有效可行的，無疑這種模仿自然生物的尋優(yōu)算法在密碼學(xué)上具有較好的應(yīng)用前景，但還有很多深入的工作有待進一步展開。

參考文獻：

［1］王育民，劉建偉.通信網(wǎng)的安全—理論與技術(shù)[M].西安:西安電子科技大學(xué)出版社，1999.

[2]張煥國，馮秀濤，覃中平，等.演化密碼與DES的演化研究[J].計算機學(xué)報，2003，26(12):1678－1684.

[3]殷新春，楊潔.基于快速收斂遺傳算法的S盒的優(yōu)化算法[J].計算機應(yīng)用，2006，26(4)：803-805.

[4]MARCIN L P，TONY W.Using genetic algorithm to optimize ACS－TSP[C]//Proc of the 3rd Int Workshop on Ant Algorithms.London:Springer－Verlag，2002:282-287.

[5]段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社，2005.

[6]劉景偉，韋寶典，呂繼強，等.AES S盒的密碼特性分析[J].西安電子科技大學(xué)學(xué)報，2004，31(2):255-259.

[7]李俊全，徐釗，劉志平.S盒的性質(zhì)和構(gòu)造方法[J].密碼與信息，1994，47(1): 26-31.

[8]陳華，馮登國，吳文玲.一種改善雙射S盒密碼特性的有效算法[J].計算機研究與發(fā)展，2004，41(8):1410－1414.

[9]NYBERG K.Perfect nonlinear S－boxes[C]//Proc of EUROCRYPTO’91.Berlin:Springer－Verlag，1991:378-386.

[10]CHEN H，F(xiàn)ENG D.An effective evolutionary strategy for bijective S－boxes[J].Evolutionary Computation，2004，2:2120-2123.

[11]NYBERG K.On the construction of highly nonlinear permutations[M].Advances in Cryptology －EUROCYPT’92.Berlin: Springer－Verlag，1993:92-98.

[12]丁建立， 陳增強， 袁著祉.遺傳算法與蟻群算法的融合[J].計算機研究與發(fā)展，2003，40(9): 1351－1356.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”