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

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

關(guān)鍵詞：S盒； 非線性度； 差分均勻度； 遺傳算法； 啟發(fā)式

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

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

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

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

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

1 遺傳算法原理

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

2 基于遺傳算法的雙射S盒構(gòu)造

2.1雙射S盒的編碼

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

2.2產(chǎn)生初始種群

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

2.3適應(yīng)值函數(shù)

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

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

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

2.4 選擇方法

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

2.5 交叉策略

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

2.6 變異規(guī)則

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

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

2.7 停止準(zhǔn)則

以當(dāng)代群體中最差個體或最佳個體的適應(yīng)值達(dá)到預(yù)先設(shè)定的某個值作為停止準(zhǔn)則。

2.8 算法描述

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

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

3.1 算法的復(fù)雜性分析

3.2 實驗結(jié)果

在編程實現(xiàn)時將部分參數(shù)設(shè)置如下：N=20， Sbox_num=64。對于不同的交叉

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

4 結(jié)束語

如果將S盒的雪崩準(zhǔn)則和擴散特性等其他性能也作為演化的目標(biāo)，那么可以對S盒的優(yōu)化進(jìn)行更為深入的研究。

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