基于抗退化混沌系統的動態S盒設計與分析

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

（北京電子科技學院 網絡空間安全系，北京 100070）

0 引言

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

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

上述方法均在一定程度上使混沌系統生成S 盒的密碼學性能更優、效率更高，但均未考慮所使用混沌系統在有限精度條件下會退化的問題［13］。混沌系統的退化是指，在有限精度條件下迭代一定次數后會落入周期軌道或固定在某一值，從而導致生成的混沌序列容易被預測，使S 盒存在安全隱患。同時，這一原因也是混沌密碼走向實用的一大障礙［14-16］。

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

1 抗退化混沌系統設計

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

Lorenz 混沌系統的狀態方程為：

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

當系統參數為σ=16，b=4，r=45.92 時處于混沌狀態。

Chebyshev 混沌映射表達式為：

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

利用Lorenz 混沌系統擾動Chebyshev 混沌系統的數學表達式為：

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

2 動態S盒構造算法

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

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

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

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

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

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

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

3 抗退化混沌系統性能分析

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

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

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

4 S盒安全性能分析

4.1 非線性度

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

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

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

其中：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］給出了差分均勻性的計算方法，對于多輸出函數S(x)=(f1(x)，f2(x)，…，fm(x))：，差分均勻性計算公式如下：

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

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

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

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

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

4.3 嚴格雪崩準則

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

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

4.4 輸出比特間獨立性

范明慧等［14］提出了驗證系統是否滿足輸出比特間獨立性（Output Bits Independence Criterion，BIC）的方法，可通過計算S 盒的任意兩個輸出比特fj和fk異或的值fj⊕fk是否滿足嚴格雪崩準則來確定，運算結果越逼近于理論值0.500 0，說明一個輸入比特取反的情況下，越能保證輸出比特對相關系數越接近于0。本文構造S 盒的相關矩陣數值如圖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，對比發現本文方案的輸出比特間獨立性更強。

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

4.5 雙射特性

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

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

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

5 結語

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