一種基于交叉耦合映像格子的S盒構造算法

趙 耿 侯艷麗 馬英杰 李 紅

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

0 引 言

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

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

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

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

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

1 時空混沌

1.1 模型介紹

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

(1)

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

1.2 局部映射

在本文中，CCML的局部函數引入變形Chebyshev映射，改進后的函數表達式為：

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

-1≤x≤1

(2)

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

2 S盒構造算法

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

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

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

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

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

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

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

3 S盒測評準則

3.1 雙射特性

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

(3)

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

3.2 非線性度

一個密碼算法其自身的非線性結構在某種程度上能夠決定整個算法的安全性，因此非線性度這一特性是能夠成為衡量系統或S盒安全性的一個指標。

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

(4)

f(x)的Walsh譜表示為：

(5)

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

3.3 差分均勻性

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

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

(6)

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

3.4 嚴格雪崩準則

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

3.5 輸出比特間獨立性

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

4 S盒性能分析

4.1 批量S盒性能分析

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

由圖2可得，每個S盒的非線性度經平均計算后的均值全部在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的相關矩陣的均值全部是處于[0.494,0.510]之間，其與理論值0.5的差距僅在[0.006,0.010]區(qū)間內。而雙射這一特性根據第3節(jié)的定義進行相關計算后，得出的每個S盒的各個分量布爾函數經線性求和都是128，故這些批量生成的S盒可以滿足雙射這一特性。

4.2 單盒性能分析

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

4.2.1雙射特性

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

4.2.2非線性度

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

表1 非線性度

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

4.2.3差分均勻性

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

4.2.4嚴格雪崩準則

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

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

4.2.5輸出比特間獨立性

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

4.3 性能對比

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

表2 本文S盒與其他文獻S盒性能對比

5 結 語

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