基于遺傳蟻群算法的Ｓ盒構造

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

關鍵詞：蟻群算法;遺傳算法;S盒;構造準則

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

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

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



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

1基本蟻群算法

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

3算法分析與實驗結果

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

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

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

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

4結束語

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

參考文獻：

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

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

[3]殷新春，楊潔.基于快速收斂遺傳算法的S盒的優化算法[J].計算機應用，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]段海濱.蟻群算法原理及其應用[M].北京:科學出版社，2005.

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

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

[8]陳華，馮登國，吳文玲.一種改善雙射S盒密碼特性的有效算法[J].計算機研究與發展，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，FENG 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].計算機研究與發展，2003，40(9): 1351－1356.

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