范明慧，仰楓帆

(南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 210016)

?

分組密碼中基于混沌映射的動態(tài)S盒構(gòu)造

范明慧，仰楓帆

(南京航空航天大學(xué) 電子信息工程學(xué)院，江蘇 南京 210016)

摘要S盒是分組密碼算法的唯一非線性部件，為了產(chǎn)生更加安全的動態(tài)S盒，提出了一種基于Logistic混沌映射和Tent混沌映射構(gòu)造動態(tài)S盒的方法。在Logistic混沌映射的初值敏感性的基礎(chǔ)上，生成的動態(tài)S盒是與密鑰相關(guān)的。對S盒的雙射性、非線性度、嚴(yán)格雪崩準(zhǔn)則、輸出比特間獨(dú)立性、均勻差分性和靈敏度進(jìn)行了測試和分析。各項理論分析和實驗結(jié)果表明，該算法產(chǎn)生的動態(tài)S盒能夠較好地符合各項設(shè)計準(zhǔn)則，可以滿足密碼算法的安全性。

關(guān)鍵詞S盒；混沌映射；分組密碼；信息安全

A Method to Construct Dynamic S-box Based on Chaotic Map in Block Cipher

FAN Ming-hui,YANG Feng-fan

(CollegeofElectronicandInformationEngineering,NanjingUniversityofAeronauticsandAstronautics,NanjingJiangsu210016,China)

AbstractS-box is the only nonlinear component for block cipher algorithm.To generate more secure dynamic S-box,a method is proposed to construct S-box dynamically by two chaotic maps(Logistic and Tent chaotic maps).On the basis of the sensitivity to initial condition of Logistic chaotic map,the generated dynamic S-box is key dependent.Then the performance indices of S-box are summarized.Six properties,such as bijective property,nonlinearity,strict avalanche criterion,output bits independence criterion,equiprobable input/output XOR distribution and sensitivity,are tested and analyzed.Simulation tests show that the criterion for designing good S-box can be met approximately.The S-box can satisfy the security of the cryptography.

Key wordsS-box;chaotic map;block cipher;information security

0引言

在分組密碼中，S盒為分組密碼算法提供了混亂的作用，是分組密碼設(shè)計的關(guān)鍵。近年來的研究表明，由于混沌理論系統(tǒng)具有很好的安全特性，如對初值和參數(shù)的敏感性、類隨機(jī)性等特點(diǎn)，利用混沌映射構(gòu)造的S盒取代傳統(tǒng)S盒成為主流。

2001年，Jakimosk和Kocarev[1]首次提出了利用混沌映射構(gòu)造出S盒的方法。該方法給出了一種基于離散化Logistic映射的混沌S盒。但是文獻(xiàn)[1]僅僅分析了S盒的非線性度和差分均勻度。2009年，文獻(xiàn)[2]中提出了一種新的基于連續(xù)混沌映射的動態(tài)S盒。由于混沌映射是連續(xù)的，因此需要進(jìn)行離散采樣。

本文提出一種新的基于離散混沌映射的算法構(gòu)造動態(tài)S盒。以密鑰作為Logistic映射的初值生成初始S盒，再以Tent映射生成的整數(shù)對對S盒進(jìn)行置亂。由于該S盒由混沌映射的初值和控制參數(shù)決定，可以通過改變混沌映射的初值和控制參數(shù)產(chǎn)生不同的S盒。

1混沌原理

Logistic混沌映射[3]的數(shù)學(xué)表達(dá)式為:

xn+1=μxn(1-xn)。

(1)

雖然Logistic映射是簡單的一維混沌映射，但是卻能產(chǎn)生非常好的混沌行為，所以在相關(guān)研究中經(jīng)常選取Logistic映射為研究對象。

Tent混沌映射是分段式一維映射，數(shù)學(xué)描述為:

xn+1=μmin(xn,1-xn)。

(2)

(3)

在不同的控制參數(shù)a下，斜Tent映射均處于混沌狀態(tài)。

2基于Logistic-Tent映射的S盒構(gòu)造

將混沌函數(shù)應(yīng)用于8×8動態(tài)S盒的生成，總體流程分為2部分：

第1部分：首先將Logistic映射的參數(shù)設(shè)置為4，再以密鑰作為Logistic映射的初始值。對于不同的密鑰，生成的混沌序列是不同的，由此實現(xiàn)了動態(tài)S盒的產(chǎn)生。具體的算法步驟如下：

① 將密鑰映射為混沌函數(shù)的初值：x0=K。其中x0為Logistic映射的初值，K為128 bit的初始密鑰；

② 將x0帶入混沌函數(shù)，其混沌函數(shù)為Logistic映射轉(zhuǎn)化為大整數(shù)的形式。其數(shù)學(xué)表達(dá)式為：

(4)

式中，0

③ 將128 bit的值xn+1按字節(jié)分組，共16 byte，xn+1=xn+1(0)xn+1(1)...xn+1(15)；

④ 將上述16 byte按位異或，得到1 byte的輸出Y(i)，其中0≤i≤255，Y(i)=xn+1(0)⊕...⊕xn+1(15)，Y(i)∈(0,255)；

⑥ 依次將Y(i)放入S盒中，若Y(i)=Y(j)，j>i，i,j為自然數(shù)，則舍去Y(j)，若S盒的256個數(shù)值尚未填滿，返回步驟②；若S盒已填滿，則S盒生成結(jié)束。

第2部分：使用斜Tent映射對初始S盒進(jìn)行置亂，得到滿足一定非線性指標(biāo)和差分均勻度的動態(tài)S盒。具體步驟如下：

① 設(shè)置斜Tent映射的參數(shù)a∈(0,1)和初始值x0∈(0,1)；

② 計算斜Tent映射的混沌迭代方程，得到長度為n的實數(shù)序列x1,x2,...,xn；

④ 根據(jù)G(i)交換S盒Yi和Yi+n/2位置上的元素，得到新的S盒，計算該S盒的非線性度和差分均勻度，若滿足所設(shè)置的門限要求，則S盒生成結(jié)束；否則令i=i+1，繼續(xù)步驟④；

至此，整個動態(tài)S盒的構(gòu)造結(jié)束。

取Logistic映射的初值

x0=9C2B2E74D242D-8279398B9719E5AF043，

每輪運(yùn)算中Logistic混沌映射迭代200次，經(jīng)過1 511輪運(yùn)算之后生成初始S盒；設(shè)置Tent映射初值x0=0.235 6，控制參數(shù)a=0.423 53，迭代步長n=2 000。設(shè)置門限要求：非線性度平均值不小于105，差分均勻度最大值為10，根據(jù)這1 000組隨機(jī)整數(shù)，對初始S盒進(jìn)行置亂，經(jīng)過32次置換后得到8×8的S盒。下面給出S盒的部分?jǐn)?shù)值：

3動態(tài)S盒性能分析與驗證

S盒設(shè)計通常有5個準(zhǔn)則：雙射性、非線性度、嚴(yán)格雪崩準(zhǔn)則、輸出比特間獨(dú)立性和差分均勻性。本文還對S盒進(jìn)行了靈敏度分析，通過改變Logistic混沌映射的初值，即改變系統(tǒng)的密鑰，判斷S盒對密鑰的敏感性。

3.1雙射性

通常要求S盒是可逆的，尤其在代替置換網(wǎng)絡(luò)中所使用的S盒必須是雙射的。文獻(xiàn)[4]給出了滿足雙射的充分必要條件：各分量布爾函數(shù)fi的線性運(yùn)算之和為2n-1，即

(5)

式中，ai∈{0,1},(a1,a2,...,an)≠(0,0,...,0)；wt()表示漢明權(quán)重。如果式(5)成立，則f是平衡的，且是雙射的。

本文中n=8，根據(jù)式(5)，滿足雙射性的標(biāo)準(zhǔn)值是128。該S盒的8個布爾向量共有255種線性組合形式。通過計算每種組合形式下向量異或值的漢明重量，可以發(fā)現(xiàn)結(jié)果均為28-1=128。因此該S盒滿足雙射性。

3.2非線性度

線性密碼分析的目的是尋找密文、明文和密鑰之間的有效線性表達(dá)式。S盒必須具有較高的非線性以抵御線性密碼分析。

在實際運(yùn)算時，通常將布爾函數(shù)f(x)轉(zhuǎn)換成Walsh譜：

(6)

式中，ω∈GF(2n)；x·ω表示x和ω的點(diǎn)積，定義為x·ω=x1·ω1⊕...⊕xn·ωn。

則Walsh譜表示的非線性度為：

(7)

根據(jù)式(7)，S盒的非線性度輸出為104、106、104、108、104、106、104和104。S盒和其他經(jīng)典S盒[1,2,5,6]的非線性比較如表1所示。

表1　本文S盒非線性度與其他經(jīng)典S盒比較

從表1中可以看出，S盒的非線性度平均值為105，優(yōu)于其他幾個經(jīng)典的S盒生成方案。這說明該S盒能抵擋最佳線性逼近的進(jìn)攻。

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

為抵抗以輸入的改變導(dǎo)致輸出有相對較大改變?yōu)榛A(chǔ)的攻擊方法，Webster和Tavare首次提出嚴(yán)格雪崩準(zhǔn)則。如果函數(shù)滿足嚴(yán)格雪崩準(zhǔn)則，則意味著一個輸入比特的改變，將有一半的輸出結(jié)果發(fā)生改變。

在實際運(yùn)用中通過構(gòu)造相關(guān)矩陣來驗證布爾函數(shù)f是否滿足SAC。在文獻(xiàn)[7]給出相關(guān)矩陣的構(gòu)造方法，對于相關(guān)矩陣A，如果其每個元素的值都接近0.5，則表明S滿足SAC。

通過計算，得到該S盒的相關(guān)矩陣：

矩陣的均值為0.501 22，非常接近于理想值0.5。而Jakimoski的相關(guān)矩陣的平均值為0.497 2，Tang的相關(guān)矩陣的平均值為0.499 3，Chen的相關(guān)矩陣的平均值為0.499 9，?zkaynak的相關(guān)矩陣的平均值為0.504 8。進(jìn)行對比，可發(fā)現(xiàn)該S盒的相關(guān)矩陣優(yōu)于其余經(jīng)典的S盒，說明該S盒能夠很好地滿足嚴(yán)格雪崩準(zhǔn)則。

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

文獻(xiàn)[8]中指出，對于其中任意2個布爾函數(shù)fj,fk(j≠k)，如果fj⊕fk高度非線性且盡可能地滿足嚴(yán)格雪崩準(zhǔn)則，則可以保證當(dāng)一個輸入比特取反時，每個輸出比特對的相關(guān)性接近于0。因此，可以通過驗證S盒的任意2個輸出異或fj⊕fk是否滿足嚴(yán)格雪崩效應(yīng)，來校驗S盒的BIC特性。

通過計算，可得fj⊕fk(1≤j≤8,1≤k≤8)的非線性度矩陣：

其均值為103.643。而Jakimoski的BIC-非線性度的平均值為104.25，Tang的BIC-非線性度的平均值為102.96，Chen的BIC-非線性度的平均值為103.36，?zkaynak的BIC-非線性度的平均值為103.82?？梢园l(fā)現(xiàn)S盒在BIC-非線性度與經(jīng)典的S盒不相上下。

計算輸入序列中一個比特取反前后，輸出序列y的任意2個比特異或值yj⊕yk變化的概率可得BIC-SAC：

BIC-SAC的均值為0.5000 7，非常接近理想值0.5。而Jakimoski的BIC-SAC的平均值為0.503 2，Tang的BIC-SAC的平均值為0.504 4，Chen的BIC-SAC的平均值為0.502 4，?zkaynak的BIC-SAC的平均值為0.500 7。對比發(fā)現(xiàn)，S盒的BIC-SAC平均值優(yōu)于其他的經(jīng)典S盒，說明該S盒具有較好的輸出比特間獨(dú)立性。

3.5差分均勻性

(8)

式中，α∈GF(2n)；β∈GF(2n)。

在實際計算中，也可以用差分逼近概率[10]來表示輸入輸出的異或分布狀況：

(9)

式中，x∈GF(2n)。式(9)即表示給定輸入差分為Δx，輸出差分為Δy的最大可能性。

根據(jù)式(9)得到S盒的差分分布表，如表2所示。從表2中可以發(fā)現(xiàn)，輸出差分的最大值為10。與經(jīng)典S盒進(jìn)行比較，Jakimoski的差分均勻度為10，Tang的差分均勻度為10，Chen的差分均勻度為12，?zkaynak的差分均勻度為10。由于差分表中的最大值越小，S盒的抗差分攻擊能力越好。對比其他S盒的差分均勻度，可以發(fā)現(xiàn)該S盒與Tang和?zkaynak的方案同樣具有很好的抗差分攻擊能力。

表2本文S盒的輸入輸出差分分布表

3.6靈敏度分析

除上述5種準(zhǔn)則外，動態(tài)S盒還需要具有對初始密鑰有較高敏感性的特性。對于上述的128 bit密鑰K改變最低位，得到新的初值K1，此時初值為x0=9C2B2E74D242D8279398B9719E5AF042，產(chǎn)生新的S盒。下面給出了與本文生成的S盒相應(yīng)位置的部分?jǐn)?shù)值：

通過比較這些相應(yīng)數(shù)值可以看出，即使初始密鑰的改變是微小的，所生成的S盒的變化很大。128 bit的密鑰對應(yīng)的密鑰空間為2128，那么窮舉攻擊在理論上是不可行的。如果以子密鑰作為動態(tài)S盒算法的初值，則隨著每一輪子密鑰的不同，將產(chǎn)生不同的S盒，更加增加了密碼系統(tǒng)的加密強(qiáng)度。

4結(jié)束語

本文提出了依據(jù)系統(tǒng)密鑰的動態(tài)S盒構(gòu)造方法。該方法利用混沌映射的偽隨機(jī)性，解決了S盒的固定結(jié)構(gòu)問題，產(chǎn)生了對密鑰敏感的動態(tài)S盒。而該算法主要的優(yōu)點(diǎn)是通過改變系統(tǒng)的密鑰可以產(chǎn)生許多不同的S盒，并且本文產(chǎn)生的動態(tài)S盒通過了評判標(biāo)準(zhǔn)。經(jīng)過與經(jīng)典S盒進(jìn)行對比分析，發(fā)現(xiàn)該S盒具有最大的非線性度平均值，最接近0.5的SAC和BIC-SAC，最大值為10的輸出差分。說明S盒可以有效地抵抗線性分析盒差分分析，具有優(yōu)良的性能，適用于開發(fā)新的分組密碼算法。

參考文獻(xiàn)

[1]JAKIMOSKI G,KOCAREV L.Chaos and Cryptography:Block Encryption Ciphers Based on Chaotic Maps[J].Circuits & Systems I Fundamental Theory & Applications IEEE Transactions on,2001,48(2):163-169.

[2]?ZKAYNAK F,?ZER A B.A Method for Designing Strong Sboxes Based on Chaotic Lorenz System[J].Physis Letters A,2010(374):3 733-3 738.

[3]宋春艷.基于混沌理論的信息加密技術(shù)研究[D].哈爾濱：哈爾濱工程大學(xué)，2013.

[4]ADAM C,TAVARES S.The Structured Design of Cryptographically Good S-boxes[J].JCryptol,1990,3(1):27-41.

[5]CHEN G,CHEN Y,LIAO X F.An Extended Method for Obtaining S-boxes Based on Three-dimentional Chaotic Baker Maps[J].Chaos,Solitons and Fractals,2007,31(3):571-579.

[6]TANG G P,LIAO X F,CHEN Y.A Novel Method for Designing S-boxes Based on Chaotic Maps[J].Chaos,Solitons& Fractals,2005(23):413-419.

[7]WEBSTER A F,TAVARES S E.On the Design of S-Boxes[C]∥Advances in Cryptology CRYPTO ’85 Proceedings.Springer Berlin Heidelberg,1986:523-534.

[8]劉強(qiáng)，方錦清，趙耿，等.基于FPGA技術(shù)的混沌加密系統(tǒng)研究[J].物理學(xué)報，2012，61(13)：130508-1-5.

[9]BIHAM E,SHAMIR A.Differential Cryptanalysis of DES-like Cryptosystems[J].Journal of Cryptology,1991,4(1):63-72.

[10]HALE J K,VERDYNLUNEL S M.Introduction to Functional Differential Equations[M].New York:Springer-Verlag,1993.

范明慧女，(1989—)，碩士。主要研究方向：數(shù)字通信、信道編碼和密碼學(xué)。

仰楓帆男，(1966—)，教授，博士生導(dǎo)師。主要研究方向：信道編碼理論和應(yīng)用、信息論和協(xié)作通信等。

作者簡介

收稿日期：2015-12-02

中圖分類號TN918

文獻(xiàn)標(biāo)識碼A

文章編號1003-3106(2016)03-0033-04

doi:10.3969/j.issn.1003-3106.2016.03.10

引用格式：范明慧,仰楓帆.分組密碼中基于混沌映射的動態(tài)S盒構(gòu)造[J].無線電工程,2016,46(3):33-36,40.