基于抗退化混沌系統(tǒng)的動(dòng)態(tài)S盒設(shè)計(jì)與分析

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

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

0 引言

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

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

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

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

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

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

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

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

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

Chebyshev 混沌映射表達(dá)式為：

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

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

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

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

本文通過抗退化數(shù)字混沌系統(tǒng)動(dòng)態(tài)生成8×8 的S盒，能有效避免傳統(tǒng)數(shù)字混沌退化問題導(dǎo)致的安全風(fēng)險(xiǎn)，可使基于數(shù)字混沌系統(tǒng)生成的S 盒隨機(jī)性更好、安全性更高。詳細(xì)的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｝，分別用于擾動(dòng)數(shù)字Chebyshev 混沌映射的輸入、輸出和參數(shù)；然后再將式（4）～（5）迭代5 000次，即可生成第一個(gè)混沌序列。

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

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

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

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

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

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

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

在低有限精度情況下，如果系統(tǒng)的輸入初值有很小改變，迭代一定次數(shù)后運(yùn)動(dòng)軌跡會(huì)完全不一樣，則說明系統(tǒng)具有初值敏感性。在保持兩個(gè)系統(tǒng)其余參數(shù)不變的情況下分別使初始值為0.250 000 00 和0.250 000 03，圖5 是兩個(gè)系統(tǒng)的軌跡圖?？梢钥闯觯词馆斎氩顒e很小迭代若干次后二者軌跡截然不同，說明系統(tǒng)具備初值敏感性。

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

4 S盒安全性能分析

4.1 非線性度

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

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

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

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

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

4.2 差分均勻性

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

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

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

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

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

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

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

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

表3 不同方案的嚴(yán)格雪崩準(zhǔn)則對比Tab.3 Strict avalanche criterion comparison among different schemes

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

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

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

4.5 雙射特性

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

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

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

5 結(jié)語

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