趙耿，張森民，馬英杰，高世蕊

（北京電子科技學院 網(wǎng)絡(luò)空間安全系，北京 100070）

0 引言

S 盒是分組密碼的核心部件之一，也是眾多分組密碼唯一非線性部件，為分組密碼提供了置亂作用，其性能與分組密碼算法的安全性密切相關(guān)［1］，因此性能良好的S 盒對分組密碼至關(guān)重要。S 盒主要有三種設(shè)計方法：隨機構(gòu)造法、數(shù)學構(gòu)造法和將二者相結(jié)合的方法［2-4］。混沌系統(tǒng)具有偽隨機性、遍歷性和初值敏感性，與密碼學擴散和混亂的安全要求有天然相似性，近年來被廣泛應(yīng)用于S 盒的設(shè)計中［5-6］。

文獻［7］中提出了使用多個初始映射設(shè)計S盒，對S 盒做非線性操作，提高了S 盒的安全性能；但采用多重混沌映射會使系統(tǒng)運算效率降低。文獻［8］中利用系統(tǒng)與Tent 映射拓撲共軛的性質(zhì)，給出系統(tǒng)概率密度函數(shù)并進一步實現(xiàn)系統(tǒng)的均勻化；均勻化后構(gòu)造的S 盒性能更優(yōu)，但嚴格雪崩準則還有待提升。文獻［9］中提出了一種采用三維Baker 混沌映射獲取強S 盒的擴展方法，修正了二維Baker 混沌映射生成S 盒存在的缺陷，比二維Baker 映射具有更強的混沌特性；但混沌系統(tǒng)仍存在退化問題。文獻［10］中研究開發(fā)了一個基于隨機選擇的S 盒生成器工具箱，可以使用經(jīng)典隨機函數(shù)和混沌系統(tǒng)類作為熵源，提升了S 盒的生成效率。文獻［11］中提出了一種基于混沌驗證碼生成S 盒的方法，可用于驗證門戶網(wǎng)站和其他用戶界面多媒體人機交互的安全性。文獻［12］中提出了一種基于正弦映射構(gòu)造S 盒的有效方法，能夠產(chǎn)生高效非線性的隨機整數(shù)序列；但不能動態(tài)批量地生成S 盒。

上述方法均在一定程度上使混沌系統(tǒng)生成S 盒的密碼學性能更優(yōu)、效率更高，但均未考慮所使用混沌系統(tǒng)在有限精度條件下會退化的問題［13］?；煦缦到y(tǒng)的退化是指，在有限精度條件下迭代一定次數(shù)后會落入周期軌道或固定在某一值，從而導致生成的混沌序列容易被預(yù)測，使S 盒存在安全隱患。同時，這一原因也是混沌密碼走向?qū)嵱玫囊淮笳系K［14-16］。

本文采用抗退化混沌系統(tǒng)生成S 盒：一方面能有效解決混沌系統(tǒng)生成序列退化問題，使之在數(shù)字有限精度下持續(xù)產(chǎn)生非周期序列，避免存在安全風險；另一方面可通過隨機改變系統(tǒng)參數(shù)值批量動態(tài)地生成S盒，極大提升了S 盒生成效率。首先，設(shè)計了抗退化混沌系統(tǒng)部分，將量化的Lorenz 混沌系統(tǒng)擾動數(shù)字Chebyshev 混沌系統(tǒng)，使數(shù)字Chebyshev 系統(tǒng)生成的混沌序列周期大大延長。然后，設(shè)計了S 盒的生成，采用截取位數(shù)法和劃分區(qū)間法生成兩種初始S 盒S1、S2，再使用索引排序擾亂法生成最終S 盒。由于該方案可對抗退化混沌系統(tǒng)的參數(shù)在一定范圍內(nèi)隨機調(diào)節(jié)，故可以動態(tài)批量地生成S盒［17］。

1 抗退化混沌系統(tǒng)設(shè)計

混沌系統(tǒng)在模擬狀態(tài)下具有初值敏感性、遍歷性和不可預(yù)測性等良好的動力學特性，但被運用到計算機等有限精度設(shè)備上時會發(fā)生退化行為。具體表現(xiàn)為迭代一定次數(shù)后混沌會落入周期軌道或固定在某一值，從而導致基于混沌的密碼算法存在安全風險。為解決混沌退化問題，本文采用擾動法來抵抗數(shù)字混沌系統(tǒng)的退化：首先迭代模擬Lorenz 混沌映射1 000次，對1 000 次以后的數(shù)值進行離散采樣；然后將采樣后的值分別用于擾動Chebyshev 混沌映射的輸入、輸出和參數(shù)。系統(tǒng)結(jié)構(gòu)如圖1 所示，新構(gòu)建的混沌系統(tǒng)迭代若干次后可生成無周期混沌序列，以此達到抗退化目的。

Lorenz 混沌系統(tǒng)的狀態(tài)方程為：

Lorenz 系統(tǒng)原本是模擬的，但計算機無法處理模擬系統(tǒng)，所以需要將其進行離散化處理。采用Euler 算法進行離散采樣，取采樣時間為T=0.002，Lorenz 混沌映射采樣后的表達式為：

當系統(tǒng)參數(shù)為σ=16，b=4，r=45.92 時處于混沌狀態(tài)。

Chebyshev 混沌映射表達式為：

其中：β為系統(tǒng)參數(shù)，X(i)和X(i+1)為第i次迭代的輸入和輸出值。數(shù)值取值區(qū)間為［-1，1］。

利用Lorenz 混沌系統(tǒng)擾動Chebyshev 混沌系統(tǒng)的數(shù)學表達式為：

其中：x(i)、y(i)和z(i)分別為Lorenz 混沌映射采樣后的3 個輸出變量；Q(i)和W(i)分別為擾動輸入和參數(shù)的中間變量。首先對數(shù)字Chebyshev 混沌映射的輸入和參數(shù)進行擾動，如式（4）；然后，再對上一步的輸出X(i+1)進行擾動，X'(i+1)為擾動輸出后的結(jié)果，如式（5）。整體迭代式（4）～（5）即可生成抗退化數(shù)字混沌序列。

2 動態(tài)S盒構(gòu)造算法

本文通過抗退化數(shù)字混沌系統(tǒng)動態(tài)生成8×8 的S盒，能有效避免傳統(tǒng)數(shù)字混沌退化問題導致的安全風險，可使基于數(shù)字混沌系統(tǒng)生成的S 盒隨機性更好、安全性更高。詳細的S 盒生成方法如下所述：

步驟1 先對Chebyshev 混沌映射賦初值X(0)=0.25，系統(tǒng)參數(shù)β=8；再迭代Lorenz 混沌映射，對Lorenz 混沌映射設(shè)初值x(0)=1，y(0)=1，z(0)=1，系統(tǒng)參數(shù)設(shè)為σ=16，b=4，r=45.92，舍去前1 000 次迭代的數(shù)值后生成三組離散混沌序列｛x｝、｛y｝、｛z｝，分別用于擾動數(shù)字Chebyshev 混沌映射的輸入、輸出和參數(shù)；然后再將式（4）～（5）迭代5 000次，即可生成第一個混沌序列。

步驟2 步驟1 迭代完5 000 次后，改變系統(tǒng)參數(shù)可生成不同的混沌序列，對Lorenz 混沌系統(tǒng)的參數(shù)數(shù)值σ累加0.04，繼續(xù)迭代5 000 次則生成新的混沌序列，以此類推可生成500 個混沌序列{X1}，{X2}，…，{X500}，每個序列數(shù)值個數(shù)為5 000。

步驟3 采用截取位數(shù)法生成初始S 盒S1。準備長為256的空 S 盒 S1，對第一個混沌序列X1={X1(0)，X1(1)，…，X1(5 000)}的第一個值X1(0)截取小數(shù)點后的前4位，對X1(1)截取第5 至8位，對X1(2)截取第9～12位，依此類推，截取第13～16 位后返回截取前4 位。然后將截取的值分別模256，按順序?qū)⑺脭?shù)值存入S1 盒中，如果待存入值在S1 盒中已存在，則舍去該值繼續(xù)存下一個直至S1盒存滿。

步驟4 采用劃分區(qū)間法生成初始S 盒S2，準備一個長為256 的空S 盒S2，將［-1，1］等分為1 000 個小區(qū)間，并為每個小區(qū)間標上序號i(i=1，2，…，1 000)。判斷第一個混沌序列X1={X1(0)，X1(1)，…，X1(5 000)}中每一個值所在的區(qū)間，并將每一個區(qū)間號模256，然后將所得數(shù)值按順序存入S2 盒中，如果待存入值在S2 盒中已有，則舍去該值繼續(xù)存下一個直至S2 盒存滿。

步驟5 采用索引排序擾亂法生成最終S 盒S3，準備長為256 的空S 盒S3，令S2 盒的256 個值作為S3 盒的索引序號，按順序把S1 盒中的256 個值分別放入S3 盒中對應(yīng)索引序號的位置，從而完成初始S 盒的擾亂，可有效增強其隨機性。

步驟6 對步驟2 生成的其余混沌序列重復步驟3～5，即可動態(tài)生成500 個8×8 的S 盒。圖2 為生成的一個S 盒的示例。

3 抗退化混沌系統(tǒng)性能分析

本文對改進后系統(tǒng)的軌跡圖、初值敏感圖和吸引子圖進行分析，以驗證是否具有遍歷性、初值敏感性和不可預(yù)測性。原始數(shù)字Chebyshev 混沌系統(tǒng)在迭代一定次數(shù)后會成為周期序列，如圖3；改進后系統(tǒng)生成的序列周期被極大延長，迭代500 次以上仍保持無規(guī)則的軌跡，說明生成的數(shù)值不可預(yù)測，系統(tǒng)是無退化的，如圖4。

在低有限精度情況下，如果系統(tǒng)的輸入初值有很小改變，迭代一定次數(shù)后運動軌跡會完全不一樣，則說明系統(tǒng)具有初值敏感性。在保持兩個系統(tǒng)其余參數(shù)不變的情況下分別使初始值為0.250 000 00 和0.250 000 03，圖5 是兩個系統(tǒng)的軌跡圖。可以看出，即使輸入差別很小迭代若干次后二者軌跡截然不同，說明系統(tǒng)具備初值敏感性。

數(shù)字混沌系統(tǒng)的吸引子呈點狀分布。數(shù)字混沌系統(tǒng)的吸引子分布得越隨機、越均勻，說明混雜效果越好。數(shù)字Chebyshev 混沌系統(tǒng)的吸引子只分布在幾個固定的點上，改進系統(tǒng)的吸引子均勻分布，如圖6 所示，說明系統(tǒng)混雜效果好，具有遍歷性。

4 S盒安全性能分析

4.1 非線性度

令f：→F2為n元布爾函數(shù)，則f(x)的非線性度為：

其中：dH(f，l)為f與l的漢明距離；Ln為仿射函數(shù)集。

本文通過Walsh 譜計算函數(shù)的非線性度，表達式為：

其中：x·ω為x與ω的點積，即x·ω=x1ω1⊕x2ω2⊕…⊕xnωn。在S 盒安全分析中，非線性度越高說明抵抗線性分析的能力越強。表1 是本文S 盒非線性度值與其他方案的比較，每一種方案共有8 個非線性度值，求出各自均值后比較可以看出本文S 盒的非線性度平均值達到106.00，高于文獻［9，14-15］的平均值，因此其抵抗線性分析的能力更強。

表1 不同方案的非線性度對比Tab.1 Nonlinearity comparison among different schemes

4.2 差分均勻性

差分均勻性是衡量S 盒抵抗差分分析能力的重要指標，文獻［14］給出了差分均勻性的計算方法，對于多輸出函數(shù)S(x)=(f1(x)，f2(x)，…，fm(x))：，差分均勻性計算公式如下：

其中：?∈GF(2n)，β∈GF(2n)，#表示計數(shù)。

差分逼近概率［2］也可用來衡量差分分布的性能：

其中：DP表示輸入差分確定情況下，輸出差分Δy的最大可能性；X表示全部可能輸入情況的集合；2n為集合中的元素個數(shù)。

最大差分值越小表明S 盒的差分均勻性越好，抗差分攻擊能力越強。表2 展示了與其他文獻方案的對比結(jié)果，文獻［10］最大差分值為10，文獻［10-13］最大差分值為12，本文方案的S 盒最大差分值為10，具有更好的抗差分攻擊能力。

表2 不同方案的最大差分值對比Tab.2 Maximum difference comparison among different schemes

4.3 嚴格雪崩準則

嚴格雪崩準則（Strict Avalanche Criterion，SAC）是指當輸入變量改變1 比特時，會導致輸出有一半的比特發(fā)生改變。通常構(gòu)造相關(guān)矩陣來驗證布爾函數(shù)是否滿足嚴格雪崩準則，若每個元素的值越接近0.5，則說明越滿足嚴格雪崩準則。本文S 盒的SAC 相關(guān)矩陣如圖7 所示。最大值和最小值分別為0.593 8、0.406 3，平均值為0.499 3，與0.500 0 只相差0.000 7。與其他文獻的對比結(jié)果如表3 所示，本文SAC 值比文獻［10-13］的S 盒更接近理論值0.500 0，表明該系統(tǒng)滿足嚴格雪崩準則，具有相對更好的安全性能。

表3 不同方案的嚴格雪崩準則對比Tab.3 Strict avalanche criterion comparison among different schemes

4.4 輸出比特間獨立性

范明慧等［14］提出了驗證系統(tǒng)是否滿足輸出比特間獨立性（Output Bits Independence Criterion，BIC）的方法，可通過計算S 盒的任意兩個輸出比特fj和fk異或的值fj⊕fk是否滿足嚴格雪崩準則來確定，運算結(jié)果越逼近于理論值0.500 0，說明一個輸入比特取反的情況下，越能保證輸出比特對相關(guān)系數(shù)越接近于0。本文構(gòu)造S 盒的相關(guān)矩陣數(shù)值如圖8 所示，平均值為0.499 9，與理論值0.500 0 僅相差0.000 1；與其他文獻方案的對比如表4 所示，文獻［10］方案的平均值為0.497 2，文獻［11］方案的平均值為0.507 8，文獻［12］方案的平均值為0.498 8，文獻［13］方案的平均值為0.501 3，對比發(fā)現(xiàn)本文方案的輸出比特間獨立性更強。

表4 不同方案的輸出比特間獨立性對比Tab.4 Comparison of output bits independence criterion among different schemes

4.5 雙射特性

在實際的加密運用中，S 盒通常要求可逆，在代換-置換網(wǎng)絡(luò)（Substitution Permutation Network，SPN）型分組密碼結(jié)構(gòu)中，S 盒必須滿足此條件。S 盒滿足雙射的充分必要條件為各分量條件的布爾函數(shù)之和為2n-1，即

其中 ：fi為 S 盒的第i個分量的布爾函數(shù)ai∈{0，1}(a1，a2，…，an) ≠(0，0，…，0)；ωt(·)表示漢明重量。若式（10）成立，說明每個fi滿足0/1 平衡，且滿足雙射條件。

由式（10）可知，當n=8，滿足雙射性的標準值是128，通過計算，本文S 盒所有分量的布爾函數(shù)之和均為28-1=128，因此該S 盒是雙射的。

5 結(jié)語

本文首先提出抗退化混沌系統(tǒng)的構(gòu)造方案，使用Lorenz混沌系統(tǒng)擾動數(shù)字Chebyshev 混沌系統(tǒng)，使生成混沌序列的周期大幅延長；然后，在此基礎(chǔ)上，采用截取位數(shù)法和劃分區(qū)間法生成兩種8×8 的初始S 盒；最后，通過索引排序擾亂法生成最終S 盒。由于Lorenz 混沌系統(tǒng)的參數(shù)可在一定范圍內(nèi)隨機切換，故可批量生成S 盒。最終對抗退化混沌系統(tǒng)和生成的S 盒進行分析與對比，實驗結(jié)果表明，該混沌系統(tǒng)具有遍歷性、初值敏感性和不可預(yù)測性，并且數(shù)據(jù)具有比模擬狀態(tài)下更好的隨機性。S 盒的非線性度、差分均勻性、嚴格雪崩準則、比特間獨立性等性能優(yōu)于近年來文獻的方案，具備較為優(yōu)秀的密碼學性能。而且相較于其他數(shù)字混沌方法生成的S盒，采用的混沌序列不僅不存在短周期行為、隨機性更好，能消除生成源上的安全隱患，而且還能批量動態(tài)地生成S盒，所以該方案生成的S 盒運用于分組密碼具備更優(yōu)的安全性能。下一步計劃將本文S 盒用于分組密碼算法設(shè)計和圖像加密相關(guān)領(lǐng)域的研究。