趙 耿 侯艷麗 馬英杰 李 紅

1(西安電子科技大學(xué)通信工程學(xué)院 陜西 西安 710071) 2(北京電子科技學(xué)院 北京 100070)

0 引 言

信息化時(shí)代科技快速發(fā)展，與此同時(shí)也伴隨著一些安全問題的出現(xiàn)。這推動(dòng)著密碼學(xué)領(lǐng)域不斷前進(jìn)，同時(shí)也使其成為信息研究領(lǐng)域的熱點(diǎn)之一。分組密碼作為密碼算法的一類分支，它的發(fā)展對(duì)信息安全有著重大影響。在分組密碼系統(tǒng)中，許多的密碼算法使用S盒來進(jìn)行替換操作，從而達(dá)到非線性功能，提高系統(tǒng)的非線性特性。因此增強(qiáng)S盒的性能也是間接地提升密碼算法安全性的有效途徑之一。

自20世紀(jì)“混沌密碼”被Matthews提出后，由于混沌系統(tǒng)的許多優(yōu)良特性，例如混沌系統(tǒng)自身的偽隨機(jī)性、遍歷性和對(duì)于某些參數(shù)的敏感特性，使其被許多學(xué)者應(yīng)用于新的密碼學(xué)系統(tǒng)的研究當(dāng)中。此外，例如通信[1-2]、圖像處理等領(lǐng)域也有因混沌的特性而將其引入進(jìn)行使用。由于混沌的這些特性與密碼學(xué)的特性有著天然的聯(lián)系，從而讓其在分組密碼系統(tǒng)中對(duì)S盒的改進(jìn)和研究成為了近些年來一直在研究的熱點(diǎn)之一。

Jakimoski等[3]給出一種用Logistic混沌系統(tǒng)設(shè)計(jì)S盒的方法，基于當(dāng)時(shí)對(duì)測(cè)試方法的研究背景，文獻(xiàn)僅在兩個(gè)方面對(duì)S盒進(jìn)行了測(cè)試。Tang等[4]提出對(duì)Logistic和二維離散混沌Baker映射進(jìn)行迭代計(jì)算。該方法生成的S盒雖然在性能上有一定提升但還不夠理想。Chen等[5]在文獻(xiàn)[4]的基礎(chǔ)上進(jìn)行改進(jìn)，并用三維Baker映射設(shè)計(jì)出新S盒。后來，?zkaynaka等[6]利用Lorenz混沌系統(tǒng)設(shè)計(jì)S盒。再后來有Khan等[7-9]研究了基于布爾函數(shù)、基于CAPTCHA和基于分?jǐn)?shù)階來構(gòu)造S盒，Belazi等[10]利用混沌正弦映射構(gòu)造S盒等。

基于對(duì)密碼理論知識(shí)的學(xué)習(xí)和S盒相關(guān)參考文獻(xiàn)的研究[11-17]，本文利用時(shí)空混沌模型構(gòu)造出一種新的S盒算法。針對(duì)時(shí)空混沌系統(tǒng)，經(jīng)特性比較后選用具有更加復(fù)雜動(dòng)力學(xué)行為的交叉耦合映像格子模型，這也是較為經(jīng)典的一個(gè)模型。隨后針對(duì)產(chǎn)生的S盒進(jìn)行了一系列與密碼學(xué)性能相關(guān)方面的測(cè)試分析。由于該構(gòu)造算法可以對(duì)初始值和控制參數(shù)以及迭代次數(shù)在一定范圍內(nèi)進(jìn)行隨機(jī)的改動(dòng)，故可以批量生成S盒。經(jīng)對(duì)測(cè)試結(jié)果的分析，本文生成的S盒符合設(shè)計(jì)標(biāo)準(zhǔn)的要求，因此可以將其應(yīng)用在分組密碼的設(shè)計(jì)中。

本文先針對(duì)批量S盒的測(cè)試結(jié)果進(jìn)行了分析，然后又從中篩選出一個(gè)S盒，并針對(duì)此盒進(jìn)行了詳細(xì)測(cè)試，還與經(jīng)典算法和已有算法中的S盒的各項(xiàng)測(cè)試數(shù)值進(jìn)行了比較。

1 時(shí)空混沌

1.1 模型介紹

時(shí)空混沌系統(tǒng)有一種典型模型是交叉耦合映像格子模型CCML (Cross Coupled Map Lattices)[18]。它相較于臨近耦合和全耦合其特性更為復(fù)雜，其數(shù)學(xué)表達(dá)形式為：

(1)

式中：n表示為離散化后的時(shí)間；i=1,2,…,L，代表系統(tǒng)的每個(gè)格子的坐標(biāo)值，L是格子的總個(gè)數(shù)；ε(0<ε<1)是耦合系數(shù)；xn(i+L)=xn(i)為其周期性邊界約束條件；函數(shù)f代表的是一個(gè)局部映射。通常情況下f會(huì)選自一維經(jīng)典混沌系統(tǒng)，但本文基于Chebyshev映射進(jìn)行改動(dòng)后來作為f函數(shù)。在上述系統(tǒng)模型中，每一時(shí)刻由標(biāo)記為偶數(shù)坐標(biāo)值的格子優(yōu)先進(jìn)行反應(yīng)和擴(kuò)散，而坐標(biāo)值是奇數(shù)的格子在前面的基礎(chǔ)之上再繼續(xù)相應(yīng)的反應(yīng)和擴(kuò)散操作。這樣相鄰格子間會(huì)相互影響，局部反應(yīng)和擴(kuò)散這兩個(gè)過程也會(huì)進(jìn)行混合。許多系統(tǒng)在反應(yīng)過程中會(huì)有周期短和慢慢趨近于不動(dòng)點(diǎn)的問題，但該系統(tǒng)能使自身周期和暫態(tài)時(shí)間增長(zhǎng)。

1.2 局部映射

在本文中，CCML的局部函數(shù)引入變形Chebyshev映射，改進(jìn)后的函數(shù)表達(dá)式為：

f(x)=(cos(k·arccosx)+1)mod

-1≤x≤1

(2)

該變形僅僅是利用數(shù)學(xué)上的移位特性和取余數(shù)特性，使得函數(shù)式值域處在[0,1]范圍內(nèi)，但并不影響原式的混沌特性，從而保證格子狀態(tài)值的選取仍然大于零且符合輸入?yún)?shù)的要求。式(2)中參數(shù)仍與未變形之前的原式含義相同，即k為變形之后Chebyshev映射的階數(shù)，以及映射也是在k≥2時(shí)才會(huì)出現(xiàn)混沌狀態(tài)。由變形Chebyshev映射作局部函數(shù)的時(shí)空混沌如圖1所示。

2 S盒構(gòu)造算法

本文通過擴(kuò)大格子數(shù)的CCML來生成分組密碼所需的8比特輸入和8比特輸出類型的S盒，具體的操作步驟如下所述。

(1) 將式(1)的函數(shù)式作為時(shí)空混沌模型，令格子個(gè)數(shù)L=512，耦合系數(shù)ε=0.2；局部函數(shù)選擇式(2)帶入系統(tǒng)，其中階數(shù)k=32；每個(gè)格子再把偽隨機(jī)數(shù)發(fā)生器產(chǎn)生的序列數(shù)作為初始值x0(i)。

(2) 將得到的初始狀態(tài)值x0(i)代入式(1)中，然后迭代所選模型d(d>2L)次，第n輪迭代(即n時(shí)刻)的參數(shù)ε取εn=με(1-ε)，μ∈(3.85,4]，即Logistic方程；參數(shù)k取kn=k(1+u)，u取自于[-0.001,0.001]區(qū)間隨機(jī)生成的數(shù)值，通過計(jì)算獲取d時(shí)刻元素個(gè)數(shù)等于512的狀態(tài)值序列{Sd(i)}，并將其中的元素依照自然數(shù)0,1,2,…,511的順序標(biāo)上序號(hào)。

(3) 將狀態(tài)值序列{Sd(i)}中的各個(gè)元素按照由小到大的規(guī)則排列，若存在相等的狀態(tài)值，則按序號(hào)值由小到大依次排列。然后把狀態(tài)值對(duì)應(yīng)的序號(hào)順序放進(jìn)空序列{S}中，即將排完序后的第一個(gè)元素對(duì)應(yīng)的序號(hào)放入空序列{S}的第一個(gè)位置，第二個(gè)元素對(duì)應(yīng)的序號(hào)放入第二個(gè)位置，最后一個(gè)元素對(duì)應(yīng)的序號(hào)放入新序列{S}的最后一個(gè)位置，按此規(guī)則可得新的序列{S}。

(4) 依次判斷新序列{S}中的每個(gè)元素是小于還是大于等于256，若小于則按順序依次放入新序列{S1}中，若大于等于則將值分別模256以后再按照順序依次放入另一個(gè)新序列{S2}中。

(5) 將新的空序列{S3}按照0,1,2,…,255的順序標(biāo)上序號(hào)，然后把序列{S2}的每個(gè)元素作為序列{S1}的每個(gè)元素的序號(hào)值進(jìn)行排序，即將{S1}中的第一個(gè)元素放在{S2}中第一個(gè)元素所示序號(hào)對(duì)應(yīng)于新序列的位置上，按此規(guī)則排序得到新的序列{S3}。

(6) 制作一個(gè)16×16的空表格，將所得序列{S3}中的元素按順序依次從表格首行開始從左到右填入，可得出一個(gè)8×8的S盒。

3 S盒測(cè)評(píng)準(zhǔn)則

3.1 雙射特性

S盒在設(shè)計(jì)時(shí)一般被規(guī)定要符合雙射特性，特別對(duì)含有SPN網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)的S盒嚴(yán)格要求要符合這一特性，因?yàn)檫@關(guān)系到后續(xù)的解密問題。文獻(xiàn)[19]中敘述了滿足要求的充分必要條件為S盒的各分量布爾函數(shù)的線性運(yùn)算之和為128，即：

(3)

式中：ai∈{0,1}，(a1,a2,…,an)≠(0,0,…,0)；wt(·)表示漢明重量。如果式(3)能夠成立，那么每個(gè)fi都是0/1平衡且雙射的。

3.2 非線性度

一個(gè)密碼算法其自身的非線性結(jié)構(gòu)在某種程度上能夠決定整個(gè)算法的安全性，因此非線性度這一特性是能夠成為衡量系統(tǒng)或S盒安全性的一個(gè)指標(biāo)。

有多種方法可以用來計(jì)算非線性度，其中用Walsh譜計(jì)算的表達(dá)式如下：

(4)

f(x)的Walsh譜表示為：

(5)

式中：ω∈GF(2n)，GF表示有限域；x·ω表示x與ω的點(diǎn)積，其定義為x·ω=x1·ω1⊕x2·ω2⊕…⊕xn·ωn，⊕表示有限域中加法。針對(duì)密碼系統(tǒng)或是S盒而言，通過計(jì)算得出的數(shù)值越大，說明抵抗線性密碼分析的能力越強(qiáng)。

3.3 差分均勻性

差分密碼分析的出現(xiàn)給許多密碼算法造成了嚴(yán)重的攻擊，使它們安全性受到了威脅，因此為估測(cè)某個(gè)算法抗擊此種攻擊的性能就出現(xiàn)了差分均勻性這一測(cè)試準(zhǔn)則。在經(jīng)過數(shù)據(jù)測(cè)試得出的差分分布表中，元素都為正整數(shù)，其中的最大值則是數(shù)據(jù)的差分均勻度。

另外，對(duì)輸入或是輸出的“異或”分布情況也可以使用DPf即差分逼近概率來表示，計(jì)算表達(dá)式如下：

(6)

式中：X是全部輸入情況的一個(gè)集合；2n則代表這個(gè)集合中一共存在多少個(gè)元素。實(shí)際上，DPf代表著取一個(gè)值是Δx的輸入差分而輸出則等于Δy的最大概率。

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

嚴(yán)格雪崩準(zhǔn)則(SAC)由Webster等最先發(fā)現(xiàn)，若所給序列的一個(gè)輸入比特被改變，而其輸出比特必定有1/2發(fā)生變化的可能，將其稱之為滿足SAC。通常驗(yàn)證這種準(zhǔn)則的方法是采取文獻(xiàn)[20]給出的構(gòu)造相關(guān)矩陣的方法進(jìn)行的。實(shí)際中，若相關(guān)矩陣中的值都與0.5較接近，就可稱其滿足SAC。

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

針對(duì)輸出比特間獨(dú)立性(BIC)性能的測(cè)試，Adams等[21]提出了一個(gè)方案，可以使用S盒的任意兩輸出比特fj和fk(j≠k)進(jìn)行fj⊕fk的運(yùn)算來驗(yàn)證特性。若運(yùn)算得出的值的非線性較好且距離SAC的理論值0.5非常近，這就能保證若存在一個(gè)輸入比特取反的情況，那么每個(gè)輸出比特對(duì)的相關(guān)系數(shù)與零非常接近，也就是幾乎為零。故能夠通過該方法來檢測(cè)S盒的這一特性。

4 S盒性能分析

4.1 批量S盒性能分析

根據(jù)第3節(jié)提到的非線性度、差分均勻性、嚴(yán)格雪崩準(zhǔn)則(SAC)、輸出比特間獨(dú)立性(BIC)和雙射特性作為本節(jié)批量生成S盒的測(cè)試準(zhǔn)則。本節(jié)將基于變形Chebyshev映射的CCML的格子個(gè)數(shù)擴(kuò)大為512，設(shè)置混沌系統(tǒng)迭代的次數(shù)為1 524，取出迭代完后[1 025,1 524]區(qū)間500次迭代模型的狀態(tài)值，然后對(duì)這500個(gè)序列按上述步驟進(jìn)行運(yùn)算可以得出500個(gè)S盒。針對(duì)這500個(gè)S盒，它們的各準(zhǔn)則測(cè)試數(shù)據(jù)分別如圖2-圖6所示。

由圖2可得，每個(gè)S盒的非線性度經(jīng)平均計(jì)算后的均值全部在100及以上，并且500個(gè)中有超過一半的S盒的平均值是在103以上；由圖3可得，差分均勻性有近一半的值為10；由圖4可得，SAC性能的值幾乎都在[0.490,0.515]之間，與理論值0.5的差距僅在[0.010,0.015]區(qū)間；由圖5可得，BIC的非線性度平均值除去兩個(gè)在[101.5,102.0]之間的值以外，其余全部大于102；由圖6可得，BIC的相關(guān)矩陣的均值全部是處于[0.494,0.510]之間，其與理論值0.5的差距僅在[0.006,0.010]區(qū)間內(nèi)。而雙射這一特性根據(jù)第3節(jié)的定義進(jìn)行相關(guān)計(jì)算后，得出的每個(gè)S盒的各個(gè)分量布爾函數(shù)經(jīng)線性求和都是128，故這些批量生成的S盒可以滿足雙射這一特性。

4.2 單盒性能分析

利用4.1節(jié)的檢測(cè)結(jié)果，經(jīng)過篩選可以得出一個(gè)優(yōu)質(zhì)的S盒，該盒的256個(gè)數(shù)據(jù)的排列順序如圖7所示。

4.2.1雙射特性

按照相關(guān)定義可以算出這個(gè)S盒的每個(gè)分量布爾函數(shù)fi在經(jīng)過線性求和后的值全部等于128，顯然符合雙射特性。

4.2.2非線性度

一個(gè)函數(shù)經(jīng)非線性度測(cè)試后得到的數(shù)值越高，說明其對(duì)于線性攻擊的抗擊能力越大，否則抵抗能力越小。經(jīng)過測(cè)試，圖7中S盒的各個(gè)函數(shù)的非線性度數(shù)值在表1中被詳細(xì)列出。

表1 非線性度

可以看出，該算法生成的S盒的每一個(gè)函數(shù)的非線性度數(shù)值都大于或者等于104，而平均值經(jīng)過計(jì)算為106。這表明此S盒在抗擊線性攻擊時(shí)具有不錯(cuò)的防御能力。

4.2.3差分均勻性

差分均勻性是S盒針對(duì)抗擊差分密碼攻擊水平的一個(gè)衡量標(biāo)準(zhǔn)，若計(jì)算出的值越小則說明該S盒對(duì)于此種攻擊的抗擊力度越大，反之越小。圖8所示即是它的差分分布，其中最大值是10。

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

若存在一個(gè)輸入序列，且該序列中有一個(gè)比特發(fā)生改變，而它的各輸出比特也隨之發(fā)生了改變且變化概率是1/2，則稱其為嚴(yán)格雪崩準(zhǔn)則。在相關(guān)測(cè)試檢測(cè)完成后可得出此S盒的相關(guān)矩陣并將其在圖9中列出。

圖9中所有數(shù)值經(jīng)過計(jì)算后的平均值為0.497 3，而這一特性的理論值是0.5，兩者僅相差0.002 7，還可看出最大值和最小值分別為0.625 0和0.406 3。綜上該S盒相關(guān)矩陣的平均值幾乎近似于0.5，這足以顯示它是可以符合SAC的。

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

根據(jù)相關(guān)參考文獻(xiàn)給出的測(cè)試BIC的方法，可以得出S盒中的任意輸出比特fj⊕fk的非線性度和相關(guān)矩陣的數(shù)值分別如圖10和圖11所示。由圖10可以得出，非線性度都在100以上，且均值為104.9。由圖11的數(shù)據(jù)可以得出，S盒比特間相關(guān)矩陣的各個(gè)數(shù)值和理論上的值0.5特別接近，而相關(guān)矩陣的均值為0.500 7與0.5僅相差0.000 7。因此可以說明任意兩個(gè)的輸出比特fj⊕fk是能夠符合非線性以及SAC的，換而言之該盒能滿足BIC的特性。

4.3 性能對(duì)比

根據(jù)4.2節(jié)的測(cè)試結(jié)果，本節(jié)將其進(jìn)行歸納并與經(jīng)典算法AES中的S盒和現(xiàn)有的一些S盒作比較，詳細(xì)數(shù)據(jù)在表2中列出?？梢钥闯鍪褂帽疚乃惴ㄉ傻腟盒在非線性度方面僅次于AES且差分均勻性與文獻(xiàn)[22]和文獻(xiàn)[23]的最大值相同并都為10。而SAC均值優(yōu)于AES的S盒次于文獻(xiàn)[22]，BIC的相關(guān)矩陣均值是最好的，且它的非線性度的均值僅次于AES的值。綜合各項(xiàng)數(shù)據(jù)，通過上述測(cè)試結(jié)果能夠表明使用本文算法生產(chǎn)的S盒在整體上是擁有較好的密碼學(xué)特性，能夠在一些新型的密碼算法中進(jìn)行使用。

表2 本文S盒與其他文獻(xiàn)S盒性能對(duì)比

5 結(jié) 語

本文基于時(shí)空混沌提出一種將模型的格子個(gè)數(shù)擴(kuò)大為512，并利用排序分類后所得序列的一部分作為索引再次排序的S盒構(gòu)造算法。而且此種算法還可以應(yīng)用于時(shí)空混沌的其他模型并進(jìn)一步對(duì)測(cè)試結(jié)果進(jìn)行研究。根據(jù)S盒的一些測(cè)評(píng)準(zhǔn)則如雙射特性、非線性度、差分均勻性。SAC、BIC對(duì)所得序列進(jìn)行測(cè)試分析后，可得各項(xiàng)數(shù)據(jù)都滿足要求。然后將其與一些其他算法生成的S盒在性能方面進(jìn)行對(duì)比，由結(jié)果可見經(jīng)由該算法構(gòu)造出的S盒是具備較為優(yōu)良的密碼學(xué)性能，并且通過對(duì)系統(tǒng)函數(shù)的一些參數(shù)或是總迭代次數(shù)進(jìn)行改變還可以使S盒批量產(chǎn)生進(jìn)行動(dòng)態(tài)使用，因此可以在新型分組密碼的設(shè)計(jì)中進(jìn)行應(yīng)用。