基于遺傳算法的S?box設(shè)計(jì)方法研究

摘 要： S?box是分組密碼中惟一的非線(xiàn)性部件，它的密碼強(qiáng)度決定了整個(gè)分組密碼的安全強(qiáng)度。提出了一種基于遺傳算法的S?box設(shè)計(jì)方法，并對(duì)S?box的雙射性、非線(xiàn)性度、嚴(yán)格雪崩準(zhǔn)則、輸出比特間獨(dú)立性和差分均勻性進(jìn)行了測(cè)試和分析。分析結(jié)果表明，利用該算法產(chǎn)生的S?box具有良好的密碼學(xué)特性，適合用于開(kāi)發(fā)新的分組密碼算法。

關(guān)鍵詞： S?box； 遺傳算法； 密碼學(xué)； 性能分析

中圖分類(lèi)號(hào)： TN918.4?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2013）07?0101?04

0 引 言

隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)的不斷應(yīng)用和發(fā)展，各種安全問(wèn)題也越來(lái)越多地受到人們的重視。密碼學(xué)作為信息安全領(lǐng)域的內(nèi)容之一，已成為研究的熱點(diǎn)問(wèn)題。在分組密碼系統(tǒng)中，S?box（Substitution box）是惟一非線(xiàn)性部件，因DES的使用廣為流傳。S?box為分組密碼算法提供了所需的混淆作用[1]。S?box的構(gòu)成可以分為兩大類(lèi)，直接用數(shù)學(xué)方法構(gòu)造和采用人工智能的算法進(jìn)行演化。AES、Camellia的S?box是基于有限域上的逆函數(shù)，還有一部分是基于m?序列[2]和正型置換，這樣構(gòu)造出來(lái)的S?box在差分均勻度，非線(xiàn)性度等性質(zhì)都表現(xiàn)良好，但其代數(shù)結(jié)構(gòu)簡(jiǎn)單，存在線(xiàn)性冗余等缺點(diǎn)，易受到代數(shù)攻擊[3]。采用演化方法[4]構(gòu)造的S?box，能夠生成隨機(jī)性和密碼學(xué)性能良好的S?box，本文研究的重點(diǎn)就是利用演化算法中的遺傳算法構(gòu)造S?box。

1 遺傳算法基本原理

遺傳算法[[5]]（Genetic Algorithm）是一種模擬生物種群進(jìn)化的優(yōu)化方法，它的思想來(lái)源于自然界中的進(jìn)化過(guò)程，其運(yùn)算過(guò)程如下：

（1）確定染色體編碼方案和適應(yīng)值計(jì)算方法；

（2）隨機(jī)生成一個(gè)初始群體；

（3）計(jì)算群體中每個(gè)個(gè)體的目標(biāo)函數(shù)和其他相關(guān)函數(shù)，根據(jù)目標(biāo)函數(shù)和適應(yīng)值函數(shù)的關(guān)系計(jì)算出每個(gè)個(gè)體的適應(yīng)值，并按大小進(jìn)行排列；

（4）選取適應(yīng)值較大的兩個(gè)個(gè)體進(jìn)行交叉和變異產(chǎn)生新的個(gè)體；

（5）滿(mǎn)足一定迭代次數(shù)算法停止。

給出了遺傳算法的流程圖。

基本遺傳算法的流程圖

2 S?box設(shè)計(jì)方法

本文最初的個(gè)體（S?box）由兩個(gè)混沌映射迭代產(chǎn)生，然后利用遺傳算法優(yōu)化個(gè)體，遺傳算法中的所有控制參數(shù)由混沌映射迭代產(chǎn)生，具體方法如下：

第1步：公式（1）和公式（2）分別定義了混沌Logistic映射和Tent映射，用于生成遺傳算法的控制參數(shù)。

[xn+1=λxn（1-xn）， λ∈（0，4）， xn∈0，1] （1）

[xn+1=xna， 0xn<0.5（1-xn）（1-a）， 0.5xn<1] （2）

式中：[xn][（n=0，1，2，…）]是兩個(gè)混沌映射的狀態(tài)值；[λ]和[a]是參數(shù)值，設(shè)[λ=4]，[a=0.5]。

給定初始值[x0]。Logistic映射迭代50次，去掉瞬間狀態(tài)，用Logistic映射迭代值作為T(mén)ent映射的初始值，Tent映射迭代50次。

第2步：根據(jù)初始種群描述的方法，通過(guò)混沌映射迭代產(chǎn)生初始種群。

第3步：根據(jù)非線(xiàn)性度公式（見(jiàn)式（13））計(jì)算當(dāng)前S?box的非線(xiàn)性度。S?box非線(xiàn)性度最小值作為個(gè)體的適應(yīng)值。如果種群中最大適應(yīng)值大于等于一個(gè)預(yù)定值F，或者種群數(shù)達(dá)到最大值，轉(zhuǎn)到第8步。

第4步：當(dāng)前個(gè)體按照適應(yīng)值從小到大排列。如果兩個(gè)個(gè)體有相同的適應(yīng)值，那么非線(xiàn)性度的平均值按從小到大排列。

第5步：根據(jù)選擇算子，選出下一代個(gè)體。

第6步：根據(jù)交叉算子，對(duì)新生個(gè)體進(jìn)行重組。

第7步：根據(jù)變異算子，對(duì)新生個(gè)體進(jìn)行變異。

第8步：產(chǎn)生適應(yīng)值最大的個(gè)體，操作結(jié)束。

2.1 初始種群

兩個(gè)混沌映射進(jìn)行迭代產(chǎn)生初始種群。初始個(gè)體的產(chǎn)生描述如下：

第1步：Logistic映射迭代10次，Tent映射迭代10次。[x]表示當(dāng)前Tent映射狀態(tài)值。通過(guò)公式（3）得到整數(shù)值[X]：

[X=256×x] （3）

第2步：定義序列S，最初為空序列。添加[X]到[S]中。

第3步：如果[S]中數(shù)值不大于256，轉(zhuǎn)到第1步。否則，輸出的[S]作為初始種群的個(gè)體。

重復(fù)操作第1～3步，直到所有種群都被初始化。

2.2 選擇算子

選擇數(shù)量由式（4）計(jì)算產(chǎn)生。

[NE=p1×C] （4）

式中：[NE]是選擇數(shù)量；[C]是種群大小；[p1]是選擇概率。由于個(gè)體是按適應(yīng)值排序的，很容易找到適應(yīng)值大的個(gè)體選擇數(shù)量。被選擇的個(gè)體直接成為下一代。

2.3 交叉算子

交叉算子可以避免局部極小值，并從父染色體里獲得基因片段。交叉過(guò)程描述如下：

第1步：通過(guò)公式（5）計(jì)算交叉所產(chǎn)生的個(gè)體總數(shù)。

[NC=p2×C] （5）

式中[p2]為交叉概率。

第2步：通過(guò)公式（1）Logistic映射迭代10次，通過(guò)公式（6）產(chǎn)生整數(shù)[l]：

[l=8×x] （6）

式中[x]是Logistic映射當(dāng)前狀態(tài)值。

第3步：通過(guò)公式（2）Tent映射迭代10次，通過(guò)式（7）和式（8）分別產(chǎn)生整數(shù)[m]和[i]：

[m=8×x] （7）

[i=C×x] （8）

第4步：選擇適應(yīng)值最大的個(gè)體作為[父1]，當(dāng)前種群中第[i]個(gè)個(gè)體作為[父2]。然后，兩個(gè)交叉子代產(chǎn)生于Exchg函數(shù)[（父1，l，父2，m）]。添加到交叉種群。

第5步：如果交叉算子產(chǎn)生的當(dāng)前個(gè)體數(shù)量不大于[NC]，重復(fù)該操作的第2～4步，直到所有選擇產(chǎn)生交叉子代。

2.4 變異算子

變異算子只發(fā)生在交叉?zhèn)€體，步驟如下：

第1步：定義[NM]為需要變異的個(gè)體數(shù)量。[NM=p3×C] （9）

式中[p3]為變異概率。

第2步：公式（1）中Logistic映射迭代10次。

第3步：公式（2）中Tent映射迭代10次。

第4步：根據(jù)公式（10）生成整數(shù)[I]：

[I=NM×x] （10）

式中[x]為T(mén)ent映射當(dāng)前狀態(tài)值。交叉種群中第[I]個(gè)個(gè)體被選擇執(zhí)行變異操作。

第5步：重復(fù)第2步操作，通過(guò)公式（11）得到整數(shù)[P1]：

[P1=NM×x] （11）

第6步：重復(fù)第3步操作，通過(guò)公式（12）得到整數(shù)[P2]：

[P2=NM×x] （12）

第7步：交換第[（P1+j）]項(xiàng)和第[（P2+j）]項(xiàng)個(gè)體，其中，[j=0，1，???，9]。生成了一個(gè)變異個(gè)體。

第8步：如果變異個(gè)體數(shù)量不大于[NM]，回到第2步，否則，停止變異算子。

3 S?box性能分析

設(shè)[x0=0.1]，[p1=0.2]，[p2=0.5]，[p3=0.3]，[C=5 000]，[F=100]。通過(guò)2.1節(jié)的方法首先得到5 000個(gè)初始個(gè)體。初始個(gè)體用來(lái)生成下一代個(gè)體。2.2～2.4節(jié)分別描述了選擇，交叉，變異生成下一代個(gè)體的過(guò)程。通過(guò)式（1）和式（2）中兩種混沌映射的迭代生成控制參數(shù)，用于產(chǎn)生下一代個(gè)體。第500代種群形成的S?box如圖2所示。

文獻(xiàn)[6?8]給出了具有代表性的混沌S?box構(gòu)造方法，用于和本文S?box進(jìn)行性能比較。文獻(xiàn)[9]給出了S?box演化算法，也用于和本文S?box進(jìn)行性能比較。

3.1 雙射性

文獻(xiàn)[6]提出了雙射性檢驗(yàn)方法。當(dāng)[m=n]時(shí)，S?box滿(mǎn)足雙射的充分必要條件為：各分量布爾函數(shù)[fi]的線(xiàn)性運(yùn)算之和為[2n-1]，[ωti=1naifi=2n-1，][ai∈0，1，（a1，a2，…，an）≠][（0，0，…，0）；][ωt]為漢明重量。[fi]滿(mǎn)足[01]平衡，說(shuō)明S?box滿(mǎn)足雙射性。本文S?box滿(mǎn)足雙射性要求。

3.2 非線(xiàn)性度

用Walsh譜表示的非線(xiàn)性度為：

[Nf=2n-11-2-nmaxSfω] （13）

在線(xiàn)性密碼分析中，關(guān)鍵一步是構(gòu)造單輪有效線(xiàn)性逼近，單輪線(xiàn)性逼近和S?box的線(xiàn)性逼近有關(guān)，S?box的非線(xiàn)性度越大越好。表1給出了本文S?box和文獻(xiàn)[6?9]中S?box的非線(xiàn)性度值，本文S?box非線(xiàn)性度值為107.2，好于其他方法構(gòu)造的S?box。

非線(xiàn)性度值比較

[S?box＼非線(xiàn)性度值＼平均值＼本文＼108 108 106 108 106 106 106 108＼107.2＼文獻(xiàn)[6]＼104 106 104 108 98 100 100 106＼103.3＼文獻(xiàn)[7]＼103 109 104 105 105 106 104 103＼104.9＼文獻(xiàn)[8]＼107 103 100 102 96 108 104 108＼103.5＼文獻(xiàn)[9]＼105 102 109 106 102 105 105 108＼105.3＼]

3.3 嚴(yán)格雪崩準(zhǔn)則

Webster和Tavares首次提出了嚴(yán)格雪崩準(zhǔn)則[[10]]。文獻(xiàn)[11]提出了一種有效的方法檢驗(yàn)S?box是否滿(mǎn)足嚴(yán)格雪崩準(zhǔn)則。如果函數(shù)滿(mǎn)足這一標(biāo)準(zhǔn)，說(shuō)明一個(gè)輸入比特的改變，將有一半的輸出結(jié)果發(fā)生變化。一般情況下，S?box的嚴(yán)格雪崩性是通過(guò)矩陣計(jì)算測(cè)試出來(lái)的。如果每個(gè)元素值和矩陣平均值都接近0.5，說(shuō)明S?box滿(mǎn)足嚴(yán)格雪崩準(zhǔn)則。圖3給出了本文S?box的相關(guān)矩陣，平均值為0.505 9，接近理想值0.5。

3.4 輸出比特間獨(dú)立性

Webster和Tavares首次提出了這個(gè)標(biāo)準(zhǔn)。這是安全密碼系統(tǒng)另一個(gè)基本屬性。對(duì)由一個(gè)明文比特的反碼所產(chǎn)生的雪崩向量集而言，所有雪崩變量應(yīng)該是成對(duì)獨(dú)立的。通過(guò)計(jì)算兩個(gè)雪崩向量的相關(guān)系數(shù)可以測(cè)量其獨(dú)立程度。

Adams C.和Tavares S.給出了另一種測(cè)量輸出比特獨(dú)立的方法[12]：對(duì)于給定的布爾函數(shù)[fi]，[fk（j≠k）]是S盒的兩個(gè)輸出比特，如果[fi⊕fk]高度非線(xiàn)性且盡可能的滿(mǎn)足嚴(yán)格雪崩效應(yīng)，則它們可以確保當(dāng)一個(gè)輸入比特取反時(shí)，每個(gè)輸出比特對(duì)的相關(guān)系數(shù)接近0。可以通過(guò)驗(yàn)證S盒的任意兩個(gè)輸出比特間[fi⊕fk]是否滿(mǎn)足嚴(yán)格雪崩準(zhǔn)則來(lái)證明S盒是否滿(mǎn)足輸出比特間獨(dú)立性準(zhǔn)則。

給出了計(jì)算結(jié)果，本文S?box輸出比特間獨(dú)立性—非線(xiàn)性度最小值為100，平均值大于100。輸出比特間獨(dú)立性—嚴(yán)格雪崩準(zhǔn)則平均值為0.502 1，接近理想值0.5。本文S?box滿(mǎn)足該準(zhǔn)則。

[-104102106102-106104102106-106104102106-100104106104104102104102100102106100102102104104106104100102104102102102106106100104104102100104-104100104104-102100100102-106104100108-]

輸出比特間獨(dú)立性—非線(xiàn)性度計(jì)算結(jié)果

[-0.531 30.476 60.531 30.498 0-0.501 90.498 00.476 60.501 9-0.502 00.515 60.478 50.502 0-0.501 90.484 40.478 50.498 00.529 30.531 30.517 60.507 80.498 00.476 60.470 70.515 60.498 00.515 60.470 70.501 90.503 90.529 30.498 00.498 00.498 00.531 30.476 60.515 60.478 50.515 60.470 70.529 30.498 00.501 90.515 60.501 9-0.531 30.529 30.501 90.531 3-0.484 40.478 50.529 30.484 4-0.501 90.501 90.478 50.501 9-]

輸出比特間獨(dú)立性—嚴(yán)格雪崩準(zhǔn)則計(jì)算結(jié)果

3.5 差分均勻性

差分均勻性是針對(duì)差分密碼分析而引入的，用來(lái)度量一個(gè)密碼函數(shù)抗擊差分密碼分析的能力。S盒的差分均勻性越小越好。

用差分逼近概率[[13]]表示輸入輸出的異或分別情況：[DPf=maxΔx≠0，Δy#x∈X|f（x）⊕f（x⊕Δx）=Δy2n] （14）

式中：[x]為所有可能輸入的集合；[2n]是集合的元素個(gè)數(shù)；[DPf]表示給定一個(gè)輸入差分[Δx]，輸出為[Δy]的最大可能性。

給出了計(jì)算結(jié)果，最大值為10，本文S?box差分逼近概率為3.906%，說(shuō)明本文S?box具有良好的抵抗差分攻擊能力。

S?box差分分布

4 結(jié) 語(yǔ)

本文提出了分組密碼算法中一種新的S?box設(shè)計(jì)方法，此方法首先通過(guò)混沌映射迭代生成初始的S?box，在初始S?box的基礎(chǔ)上通過(guò)遺傳算法，得到性能更好的S?box。遺傳算法進(jìn)化過(guò)程中的控制參數(shù)由混沌映射迭代產(chǎn)生。本算法產(chǎn)生的S?box不僅具有混沌映射的隨機(jī)分布特性，還具有遺傳算法的優(yōu)化特性。通過(guò)測(cè)試可以看出，本文S?box具有良好的密碼學(xué)特性，適合開(kāi)發(fā)新的分組密碼算法。

參考文獻(xiàn)

[1] CHEN Hua， FENG Deng?guo. An effective evolutionary strategy for bijective s?boxes [C]// 2004 IEEE Congress on Evolutionary Computation. Oregon： IEEE， 2004， 2： 2120?2123.

[2] 劉曉晨，馮登國(guó).滿(mǎn)足若干密碼學(xué)性質(zhì)的S盒的構(gòu)造[J].軟件學(xué)報(bào)，2000（10）：15?17.

[3] FREDERIK A， MATTHIAC K. Algebraic attacks on combiners with memory [C]// 23rd Annual International Cryptology Conference. Santa Barbara， California， USA： 2003： 162?175.

[4] 張煥國(guó)，馮秀濤，覃中平，等.演化密碼與DES的演化研究[J].計(jì)算機(jī)學(xué)報(bào)，2003（12）：23?25.

[5] 玄光南，程潤(rùn)偉.遺傳算法與工程設(shè)計(jì)[M].北京：科學(xué)出版社，2000.

[6] JAKIMOSKI G， KOCAREV L. Chaos and cryptography： block encryption ciphers based on chaotic maps [J]. IEEE Transactions on Circuits and Systems?I， 2001， 48（2）： 163?169.

[7] TANG G， LIAO X， CHEN Y. A method for designing dynamical S?boxes based on discretized chaotic map [J]. Chaos Solitons Fractals 2005， 23： 413?416.

[8] ASIM M， JEOTI V. Efficient and simple method for designing chaotic S?boxes [J]. Etri J.， 2008， 30（1）： 170?176.

[9] BHATTACHARYA D， BANSAL N， BANERJEE A， et al. A near optimal S?box design [J]. Lecture Notes in Computer Science， 2012， 4812： 7?90.

[10] WEBSTER A F， TAVARES S. On the design of S?boxes [J]. Lecture Notes in Computer Science， 1986， 218： 523?534.

[11] PIEPRZYK J， FINKELSTEN G. Towards effective nonlinear cryptosystem design [J]. IEEE Proc. Part E： Computers and Digital Techniques. 1988， 135（6）： 325?335.

[12] ADAMS C， TAVARES S. The structured design of cryptographically good S?boxes [J]. Journal of Cryptology， 1990， 3（1）： 27?41.

[13] HALE J K，VERDYN LUNEL S M. Introduction to functional differential equations [M]. New York： Springer? verlag， 1993.