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

摘 要：采用遺傳算法來構造S盒，并引入了啟發式變異策略。該策略既可以防止優良的基因受到破壞，又可以保證群體中個體的多樣性。基于該方法，給出了6×6的S盒構造的完整程序描述，并獲得了一批高非線性度和低差分均勻度的S盒。

關鍵詞：S盒； 非線性度； 差分均勻度； 遺傳算法； 啟發式

中圖分類號：TP301文獻標志碼：A

文章編號：1001—3695(2007)03—0091—03

S盒是許多分組密碼算法中唯一的非線性部件，因此其密碼強度決定了整個分組密

碼算法的安全強度。S盒主要提供了分組密碼算法所必需的混淆作用[1]。

一般地，可以將S盒的構造分成兩大類：一類是用數學方法構造，另一類是隨機生成構造。使用數學函數可以構造一些好的S盒，目前常用的此類S盒有指數函數、對數函數、有限域GF(2n)上的逆映射以及有限域上的冪函數[2]。隨機選取方法要求設計者有足夠的時間和計算能力。本文利用遺傳算法來構造S盒，該方法也是隨機構造方法中的一種。

1 遺傳算法原理

遺傳算法(Genetic Algorithm， GA)[3]是模擬自然界自然選擇遺傳機制進行搜索尋優的方法，它模擬生物在染色體層面的各種遺傳優化作用而設計人工尋優方法。GA本質是一個群體迭代過程，從一個隨機的初始群體出發，依據優勝劣汰原則，通過競爭、選擇、繁殖、變異等遺傳優化作用，產生性能更優的下一代群體，直到滿足環境約束的優良個體或合乎具體的應用準則為止。圖1給出了遺傳算法的一般操作過程。

2 基于遺傳算法的雙射S盒構造

2.1雙射S盒的編碼

對于任意n階的雙射S盒均可以看做是0—2n-1的所有整數的一個全排列。因此，染色體可以采用換位表達[3]。

2.2產生初始種群

傳統的遺傳算法均是采用隨機方法來生成初始種群的，這就必然會增加額外的計算量。筆者將預先生成的一批S盒存放在某個文件夾內，在執行遺傳算法時，首先到指定的文件夾內隨機選擇N個S盒作為初始種群。這種方法在一定程度上減少了算法的運行時間。

2.3適應值函數

自然界中，個體的適應值即是它繁殖的能力，它將直接關系到其后代的數量[4]。目前最有效的兩種攻擊方式是線性分析和差分分析，因此，在本文的適應值函數中將同時考慮S盒的非線性度和差分均勻度。

下面將給出6×6的雙射S盒的適應值函數。首先，假設在某個特定的應用背景下，S盒的性能由好到差的排列如下：(20，6)， (20，8)， (18，6)， (18，8)， (20，10)， (18，10)， (16，6)， (16，8)， (16，10)。適應值越大，組合越好，根據這一點將適應值函數定義為

表1顯示了非線性度和差分均勻度的各種組合適應值。從表1中可看出適應值的次序與上文中組合的排列是一致的。

2.4 選擇方法

算法的選擇方法采用基于局部競爭機制的選擇：μ+λ選擇，即從λ個后代與μ個父體中選取μ個最優的后代。這種選擇策略可以大大減少額外的計算量[4]。事實上，還可以將這種選擇方法稱為最佳個體保存法。

2.5 交叉策略

算法的交叉操作是：首先為當代群體中的所有個體分配雜交概率，選中滿足概率c的，然后將所有選中的個體進行兩兩雜交操作。本文采用算法1對兩個父體執行交叉操作。

2.6 變異規則

交叉完成后，新的子女個體并沒有直接進行變異操作，而是首先根據μ+λ選擇策略，從N個父體和所有子女個體中選出N適應值最高的S盒作為后面進行變異的候選個體，然后以概率1將子女個體進行變異。其中N是群體的規模。這種方法既可以避免遺漏掉好的個體，又有利于加快算法的收斂速度。

變異算子具有補償群體多樣性損失的重要作用，一方面可以在當前解附近尋找更優解，另一方面可以保持群體的多樣性，使群體能夠繼續進化。本文采用多次互換的變異技術，使得產生的子女個體有較大順序上的變化。為了防止優良的基因受到破壞，對于性質較好的染色體，只交換兩次；為了保證群體中個體的多樣性，對于性質較差的染色體，至少執行五次互換操作；為了體現遺傳算法的隨機性，用隨機方法來產生互換的次數m。實驗表明，本文所采用的這種啟發式變異規則能夠顯著提高算法的搜索效率，大大加快算法的收斂速度。

2.7 停止準則

以當代群體中最差個體或最佳個體的適應值達到預先設定的某個值作為停止準則。

2.8 算法描述

上面討論了算法的各個組成部分， 下面給出針對6×6的S盒構造的完整程序描述。

3 算法分析及實驗結果

3.1 算法的復雜性分析

3.2 實驗結果

在編程實現時將部分參數設置如下：N=20， Sbox_num=64。對于不同的交叉

概率和變異概率的組合，程序各執行了五次，初始S盒與迭代后的S盒分別有100個。表2—7分別顯示了對于不同交叉概率和變異概率，迭代前后的不同性能S盒的分布情況。

4 結束語

如果將S盒的雪崩準則和擴散特性等其他性能也作為演化的目標，那么可以對S盒的優化進行更為深入的研究。

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