趙 耿 侯艷麗 馬英杰 李 紅

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

0 引 言

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

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

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

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

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

1 時空混沌

1.1 模型介紹

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

(1)

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

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時才會出現(xiàn)混沌狀態(tài)。由變形Chebyshev映射作局部函數(shù)的時空混沌如圖1所示。

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

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

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

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

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

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

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

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

3 S盒測評準(zhǔn)則

3.1 雙射特性

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

(3)

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

3.2 非線性度

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

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

(4)

f(x)的Walsh譜表示為：

(5)

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

3.3 差分均勻性

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

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

(6)

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

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

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

3.5 輸出比特間獨立性

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

4 S盒性能分析

4.1 批量S盒性能分析

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

由圖2可得，每個S盒的非線性度經(jīng)平均計算后的均值全部在100及以上，并且500個中有超過一半的S盒的平均值是在103以上；由圖3可得，差分均勻性有近一半的值為10；由圖4可得，SAC性能的值幾乎都在[0.490,0.515]之間，與理論值0.5的差距僅在[0.010,0.015]區(qū)間；由圖5可得，BIC的非線性度平均值除去兩個在[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)計算后，得出的每個S盒的各個分量布爾函數(shù)經(jīng)線性求和都是128，故這些批量生成的S盒可以滿足雙射這一特性。

4.2 單盒性能分析

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

4.2.1雙射特性

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

4.2.2非線性度

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

表1 非線性度

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

4.2.3差分均勻性

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

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

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

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

4.2.5輸出比特間獨立性

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

4.3 性能對比

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

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

5 結(jié) 語

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