趙 耿，馬英杰，陳 磊，董有恒，侯艷麗

（1.北京電子科技學(xué)院，北京 100070；2.北京郵電大學(xué)，北京 100876；3.西安電子科技大學(xué)，陜西西安 710071）

1 引言

現(xiàn)代分組密碼中，置換和替換網(wǎng)絡(luò)是不可或缺的，如AES（Advanced Encryption Standard）算法.其中S 盒作為分組密碼中唯一的非線性部件，主要作用就是實(shí)現(xiàn)替換運(yùn)算［1］，構(gòu)造動(dòng)態(tài)S 盒的方法有很多，利用混沌系統(tǒng)良好的偽隨機(jī)性質(zhì)來構(gòu)造動(dòng)態(tài)S盒已經(jīng)成為構(gòu)造S盒的一個(gè)重要方法［2］.唐國坪等提出一種基于Logistic映射的兩步構(gòu)造S 盒的方法，盡管這種設(shè)計(jì)方法很有效、實(shí)用，但還是存在著隨機(jī)性和不可以測(cè)性不夠強(qiáng)的缺點(diǎn)［3，4］.陳果等用三維的Baker映射設(shè)計(jì)了一種S盒克服了這些缺點(diǎn)［5］.王永［6］等和Ozkaynak［7］等分別提出了利用帳篷映射和連續(xù)時(shí)間的Lorenz 混沌系統(tǒng)來構(gòu)造S盒.佟曉筠提出了一種新的超混沌系統(tǒng)，并將其用于生成置換和替代圖像像素的密鑰流，使用動(dòng)態(tài)S盒設(shè)計(jì)加密算法［8］.閔樂泉設(shè)計(jì)了基于分段非線性魯棒混沌映射的偽隨機(jī)數(shù)發(fā)生器，提出了批量生成S 盒的算法［9］.Akram Belazi提出了一種基于正弦映射的S盒構(gòu)造的有效方法［10］.Majid Khan 提出基于混沌布爾函數(shù)構(gòu)造S盒，并將其用于圖像加密［11］.這些構(gòu)造方法為得到抵抗差分密碼分析和線性密碼分析能力好的S 盒提供了思路.朱虹宏等基于多混沌系統(tǒng)及復(fù)合思想，引入Arnold映射置亂算法構(gòu)造了一種混沌S 盒［12］.Islam 等構(gòu)造了四維四翼超混沌系統(tǒng)，并以此設(shè)計(jì)了一種混沌S 盒［13］.然而上述方法所涉及到的混沌映射均在相空間或者回歸映射中存在固定結(jié)構(gòu)的吸引子，極易受到相空間重構(gòu)［14］或者回歸映射分析［15］的攻擊，而且當(dāng)混沌系統(tǒng)在有限精度的計(jì)算機(jī)中運(yùn)行時(shí)會(huì)出現(xiàn)退化顯現(xiàn)［16］，出現(xiàn)周期現(xiàn)象，嚴(yán)重威脅到混沌密碼系統(tǒng)的安全性.基于上述原因，Peizhao Zhou 等人提出了一種基于PWLCM（Piece Wise Linear Chaotic Map）-sin 映射的耦合映射格子的時(shí)空混沌系統(tǒng)［17］，并用其生成了S 盒，分析表明該系統(tǒng)生成的S 盒具有良好的非線性，然而，每個(gè)格子生成的序列在回歸映射中依然具有明顯的固定帳篷形狀，依然易受到回歸映射分析攻擊.王永［18］等人為了解決時(shí)空混沌系統(tǒng)中存在的概率分布不均以及回歸映射中形態(tài)結(jié)構(gòu)固定的弱點(diǎn)，向基于分段Logistic 映射的二維耦合映像格子模型添加了偏移量，使得結(jié)果更加均勻，然而該文僅僅對(duì)該系統(tǒng)的性能進(jìn)行了分析并未涉及到模型的應(yīng)用.

為了改進(jìn)上述缺點(diǎn)，本文提出基于初等元胞自動(dòng)機(jī)（Elementary Cellular Automata，ECA）的新型擾動(dòng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)，并進(jìn)行了分布圖、分岔圖和相圖的數(shù)值仿真，結(jié)果表明擾動(dòng)系統(tǒng)能夠改善原系統(tǒng)的均勻性，提高系統(tǒng)的動(dòng)力學(xué)復(fù)雜性.采用均勻化的擾動(dòng)時(shí)空混沌系統(tǒng)設(shè)計(jì)了動(dòng)態(tài)S盒生成算法，并進(jìn)行了非線性度、嚴(yán)格雪崩準(zhǔn)則和差分均勻性的統(tǒng)計(jì)分析，結(jié)果表明均勻化擾動(dòng)時(shí)空混沌系統(tǒng)產(chǎn)生的動(dòng)態(tài)S 盒具有更高的安全性.

2 基于初等元胞自動(dòng)機(jī)擾動(dòng)的時(shí)空混沌系統(tǒng)構(gòu)造

2.1 單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)及其數(shù)值仿真

單向耦合映像網(wǎng)絡(luò)是一類時(shí)空混沌系統(tǒng)，具有易于產(chǎn)生、支持并行計(jì)算等優(yōu)點(diǎn)，其定義為

式中n=0，1，2，…和i=1，2，3，…，L分別代表時(shí)間維度（迭代次數(shù)）和空間維度（格點(diǎn)索引），xn（i）表示在時(shí)刻n時(shí)，第i個(gè)格點(diǎn)的狀態(tài)值，L表示格點(diǎn)的總數(shù)，ε（ε∈（0，1））代表耦合強(qiáng)度.該系統(tǒng)的邊界條件可以表示為xn（i－1）=xn（L），底層映射?為Logistic映射，即

當(dāng)參數(shù)ε=0.625，u=4，L=100 時(shí)，式（1）所示單向耦合映像網(wǎng)絡(luò)的分布圖如圖1（a）所示，當(dāng)參數(shù)ε=0.875，u=4，L=100 時(shí)，單向耦合映像網(wǎng)絡(luò)的分布圖如圖1（b）所示.從圖1 可以看出，參數(shù)ε的取值能夠影響單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)的分布情況，該系統(tǒng)存在均勻性較差的缺點(diǎn).

圖1 單向耦合映像網(wǎng)絡(luò)的分布圖

當(dāng)參數(shù)u=4，改變參數(shù)ε的取值，式（1）所示系統(tǒng)的相圖如圖2 所示.從圖2 可以看出，參數(shù)ε的取值能夠影響單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)的相圖，該系統(tǒng)存在動(dòng)力學(xué)特性不夠復(fù)雜的缺點(diǎn).

圖2 相圖u=4（ε=0.125,ε=0.625,ε=875）

2.2 初等元胞自動(dòng)機(jī)

元胞自動(dòng)機(jī)是由數(shù)學(xué)家Stanislaw M Ulam和John von Neumann 于1948 年提出的［19，20］.初等元胞自動(dòng)機(jī)是一種特殊的一維元胞自動(dòng)機(jī).初等元胞自動(dòng)機(jī)的構(gòu)成如圖3所示.

圖3 初等元胞自動(dòng)機(jī)

圖3 中元胞Cn?1和Cn+1是元胞Cn的鄰居，其中C1和CL互為鄰居.在ECA中，每次迭代的當(dāng)前元胞狀態(tài)值由當(dāng)前元胞和其鄰居的前次狀態(tài)值決定，如式（3）所示

其中代表了元胞Ci在t時(shí)刻的狀態(tài)值，t代表時(shí)間維度，即迭代次數(shù)，i代表空間維度，即元胞編號(hào).此處f為布爾函數(shù)并由局部轉(zhuǎn)換規(guī)則決定，其本質(zhì)上是一個(gè)由集合｛000，001，010，011，…，111｝到集合｛0，1｝的映射.顯然對(duì)于初等元胞自動(dòng)機(jī)，共有256 個(gè)轉(zhuǎn)換規(guī)則.其中以第105號(hào)轉(zhuǎn)換規(guī)則為例，其轉(zhuǎn)換表如表1所示.

表1 第105號(hào)ECA轉(zhuǎn)換規(guī)則

根據(jù)W Li 等人的研究［21］，具有不同轉(zhuǎn)換規(guī)則的ECA，其在迭代過程中所表現(xiàn)出的動(dòng)態(tài)特性也互不相同.任意一個(gè)具有全局混沌規(guī)則的ECA 均能夠用來構(gòu)建本文所提出的時(shí)空混沌系統(tǒng).這些全局混沌規(guī)則已在表2 中給出.其中具有110 號(hào)轉(zhuǎn)換規(guī)則的ECA，我們簡(jiǎn)稱為110號(hào)ECA，以此類推.

表2 全局混沌規(guī)則

為了進(jìn)一步說明具有這些混沌規(guī)則的ECA 在迭代過程中所表現(xiàn)的偽隨機(jī)性.我們?cè)趫D4中展示了60號(hào)，105號(hào)以及150號(hào)的迭代結(jié)果.

圖4 全局混沌的ECA迭代結(jié)果

圖4 中黑色（白色）的方格代表本方格上的元胞其狀態(tài)值為“1”（“0”），縱坐標(biāo)代表迭代次數(shù)，由上至下遞增，橫坐標(biāo)代表元胞索引.顯然，三種ECA 均顯示出偽隨機(jī)性.本文選擇105號(hào)ECA用來構(gòu)造時(shí)空混沌系統(tǒng).

2.3 基于初等元胞自動(dòng)機(jī)擾動(dòng)的時(shí)空混沌系統(tǒng)構(gòu)造及其數(shù)值仿真

針對(duì)式（1）所示傳統(tǒng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)存在均勻性較差以及動(dòng)力學(xué)特性不夠復(fù)雜的問題，本文基于初等元胞自動(dòng)機(jī)構(gòu)造了新型擾動(dòng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)，即

式中，Sn為初等元胞自動(dòng)機(jī)的迭代結(jié)果，為初等元胞自動(dòng)機(jī)第i個(gè)元胞的迭代結(jié)果，其中p(Sn)=

當(dāng)參數(shù)ε=0.625，u=4，L=100 時(shí)，式（4）所示擾動(dòng)時(shí)空混沌系統(tǒng)的分布圖如圖5（a）所示，當(dāng)參數(shù)ε=0.875，u=4，L=100 時(shí)，擾動(dòng)時(shí)空混沌系統(tǒng)的分布圖如圖5（b）所示.

從圖1、圖5的對(duì)比可以看出，提出的基于初等元胞自動(dòng)機(jī)構(gòu)造的新型擾動(dòng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)均勻性明顯優(yōu)于傳統(tǒng)時(shí)空混沌系統(tǒng).

圖5 擾動(dòng)時(shí)空混沌系統(tǒng)的分布圖

當(dāng)參數(shù)u=4，改變參數(shù)ε的取值，式（4）所示系統(tǒng)的相圖如圖6所示.

圖6 相圖u=4（ε=0.125,ε=0.625,ε=0.875）

從圖2、圖6的對(duì)比可以看出，提出的基于初等元胞自動(dòng)機(jī)構(gòu)造的新型擾動(dòng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)的動(dòng)力學(xué)復(fù)雜性明顯優(yōu)于傳統(tǒng)時(shí)空混沌系統(tǒng).

3 基于擾動(dòng)時(shí)空混沌系統(tǒng)的動(dòng)態(tài)S盒設(shè)計(jì)

3.1 擾動(dòng)時(shí)空混沌系統(tǒng)產(chǎn)生序列

處理函數(shù)：Mseq=chaosGenFun（K，n0，n）

輸入：密鑰K，輸出長度n0，n.

描述：①密鑰K由8 個(gè)長度相等的子密鑰構(gòu)成，可表示為（K（0），K（1），K（2），…，K（7））.②n0為要舍去的混沌系統(tǒng)初始迭代次數(shù)，n是后續(xù)的迭代次數(shù).

輸出：擾動(dòng)時(shí)空混沌序列Mseq.

描述：Mseq是一個(gè)矩陣，大小為n×8，生成的混沌序列中的元素以64位雙精度浮點(diǎn)數(shù)型進(jìn)行儲(chǔ)存.

3.2 生成密鑰流

處理函數(shù)：［KS］=ksGenFun（Mseq，nks）

輸入：Mseq，輸出長度nks.

描述：nks為后續(xù)步驟中所需密鑰流的總長度.

輸出：密鑰流KS.

描述：KS是一個(gè)長度為nks的向量.

3.3 生成動(dòng)態(tài)S盒

處理函數(shù)：［S1，S2］=SboxGenFun（KS）輸入：KS.

描述：KS由上一個(gè)處理函數(shù)產(chǎn)生，要求其長度8n≥512+nks.

輸出：S盒S1，S2.

描述：雙S 盒S1，S2均是大小為16×16 的替換表，且滿足雙射條件.S 盒和密鑰流是由所生成KS的不同部分構(gòu)成.

（1）初始化S盒S1和S2.按順序賦值為0～255：

（2）構(gòu)造兩個(gè)16×16 的隨機(jī)矩陣R1，R2.分別取KS的256 個(gè)元素，RV1=KS（nks，nks+255），RV2=KS（nks+256，nks+511），然后逐行將RV1和RV2 分別轉(zhuǎn)換為兩個(gè)隨機(jī)矩陣R1，R2，大小為16×16.

（3）利用R1，R2，對(duì)S盒S1和S2進(jìn)行隨機(jī)化處理.對(duì)S1，S2的元素進(jìn)行如下操作：

其中，i，j=0，2，3，…，15代表S1中元素的索引，分別表示行和列.函數(shù)(x)MSB和(x)LSB分別代表取x的最高四位和最低四位.的作用就是根據(jù)R1（i，j）的值，得到與S1中位置（i，j）上的元素進(jìn)行交換的元素索引（k，l），并將兩元素進(jìn)行交換.按順序?qū)1中的所有元素即位置（1，1）至（16，16）按照式（6）進(jìn)行交換亂序后得到隨機(jī)化后的S1盒.具體過程如圖7 所示.同理，利用隨機(jī)矩陣R2對(duì)S2盒進(jìn)行上述亂序操作.

圖7 構(gòu)造S盒S1的示意圖

4 動(dòng)態(tài)S盒的安全性分析

4.1 非線性度

本文S 盒的非線性度如表3 所示，其平均值為105.75，略優(yōu)于文獻(xiàn)［4，11，12］的非線性度，說明該S 盒抵抗線性分析的能力更強(qiáng).

表3 S盒非線性度對(duì)比

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

嚴(yán)格雪崩準(zhǔn)則是指若某個(gè)輸入比特發(fā)生改變，那么對(duì)應(yīng)的輸出比特發(fā)生改變的概率為1/2.通過計(jì)算，該S盒的數(shù)據(jù)如表4所示.

表4 S盒嚴(yán)格雪崩準(zhǔn)則對(duì)比

表4 中列出了平均值與理論值0.5 的差距.根據(jù)表4可以得出，由本文算法得出的S盒僅與理論值0.5相差0.002 5，優(yōu)于文獻(xiàn)［11］和文獻(xiàn)［12］，僅次于文獻(xiàn)［4］提出的算法，可見該S盒能較好滿足嚴(yán)格雪崩準(zhǔn)則.

4.3 差分均勻性

通過計(jì)算可以得出本文S 盒的差分均勻度與其他文獻(xiàn)的S 盒的差分均勻度的對(duì)比如表5 所示，根據(jù)表5可以看出本文S 盒的差分均勻度為10 與文獻(xiàn)［12］的相同，同樣優(yōu)于另外兩個(gè)文獻(xiàn)的數(shù)據(jù).由此說明本文S 盒針對(duì)差分線性分析的抵抗能力較強(qiáng).

表5 S盒差分均勻性對(duì)比

4 總結(jié)

本文基于初等元胞自動(dòng)機(jī)構(gòu)造了新型擾動(dòng)單向耦合映像網(wǎng)絡(luò)時(shí)空混沌系統(tǒng)，并進(jìn)行了分布圖、分岔圖和相圖的數(shù)值仿真，結(jié)果表明擾動(dòng)系統(tǒng)能夠改善原系統(tǒng)的均勻性，提高系統(tǒng)的動(dòng)力學(xué)復(fù)雜性.采用均勻化的擾動(dòng)時(shí)空混沌系統(tǒng)設(shè)計(jì)了動(dòng)態(tài)S盒生成算法，并進(jìn)行了非線性度、嚴(yán)格雪崩準(zhǔn)則和差分均勻性的統(tǒng)計(jì)分析，結(jié)果表明均勻化擾動(dòng)時(shí)空混沌系統(tǒng)產(chǎn)生的動(dòng)態(tài)S 盒具有更高的安全性.故本文方案可產(chǎn)生大量性能優(yōu)秀的S 盒，在分組密碼設(shè)計(jì)等方面擁有良好的應(yīng)用前景.