分組密碼中基于混沌映射的動態S盒構造

范明慧，仰楓帆

(南京航空航天大學 電子信息工程學院，江蘇 南京 210016)

?

分組密碼中基于混沌映射的動態S盒構造

范明慧，仰楓帆

(南京航空航天大學 電子信息工程學院，江蘇 南京 210016)

摘要S盒是分組密碼算法的唯一非線性部件，為了產生更加安全的動態S盒，提出了一種基于Logistic混沌映射和Tent混沌映射構造動態S盒的方法。在Logistic混沌映射的初值敏感性的基礎上，生成的動態S盒是與密鑰相關的。對S盒的雙射性、非線性度、嚴格雪崩準則、輸出比特間獨立性、均勻差分性和靈敏度進行了測試和分析。各項理論分析和實驗結果表明，該算法產生的動態S盒能夠較好地符合各項設計準則，可以滿足密碼算法的安全性。

關鍵詞S盒；混沌映射；分組密碼；信息安全

A Method to Construct Dynamic S-box Based on Chaotic Map in Block Cipher

FAN Ming-hui,YANG Feng-fan

(CollegeofElectronicandInformationEngineering,NanjingUniversityofAeronauticsandAstronautics,NanjingJiangsu210016,China)

AbstractS-box is the only nonlinear component for block cipher algorithm.To generate more secure dynamic S-box,a method is proposed to construct S-box dynamically by two chaotic maps(Logistic and Tent chaotic maps).On the basis of the sensitivity to initial condition of Logistic chaotic map,the generated dynamic S-box is key dependent.Then the performance indices of S-box are summarized.Six properties,such as bijective property,nonlinearity,strict avalanche criterion,output bits independence criterion,equiprobable input/output XOR distribution and sensitivity,are tested and analyzed.Simulation tests show that the criterion for designing good S-box can be met approximately.The S-box can satisfy the security of the cryptography.

Key wordsS-box;chaotic map;block cipher;information security

0引言

在分組密碼中，S盒為分組密碼算法提供了混亂的作用，是分組密碼設計的關鍵。近年來的研究表明，由于混沌理論系統具有很好的安全特性，如對初值和參數的敏感性、類隨機性等特點，利用混沌映射構造的S盒取代傳統S盒成為主流。

2001年，Jakimosk和Kocarev[1]首次提出了利用混沌映射構造出S盒的方法。該方法給出了一種基于離散化Logistic映射的混沌S盒。但是文獻[1]僅僅分析了S盒的非線性度和差分均勻度。2009年，文獻[2]中提出了一種新的基于連續混沌映射的動態S盒。由于混沌映射是連續的，因此需要進行離散采樣。

本文提出一種新的基于離散混沌映射的算法構造動態S盒。以密鑰作為Logistic映射的初值生成初始S盒，再以Tent映射生成的整數對對S盒進行置亂。由于該S盒由混沌映射的初值和控制參數決定，可以通過改變混沌映射的初值和控制參數產生不同的S盒。

1混沌原理

Logistic混沌映射[3]的數學表達式為:

xn+1=μxn(1-xn)。

(1)

雖然Logistic映射是簡單的一維混沌映射，但是卻能產生非常好的混沌行為，所以在相關研究中經常選取Logistic映射為研究對象。

Tent混沌映射是分段式一維映射，數學描述為:

xn+1=μmin(xn,1-xn)。

(2)

(3)

在不同的控制參數a下，斜Tent映射均處于混沌狀態。

2基于Logistic-Tent映射的S盒構造

將混沌函數應用于8×8動態S盒的生成，總體流程分為2部分：

第1部分：首先將Logistic映射的參數設置為4，再以密鑰作為Logistic映射的初始值。對于不同的密鑰，生成的混沌序列是不同的，由此實現了動態S盒的產生。具體的算法步驟如下：

① 將密鑰映射為混沌函數的初值：x0=K。其中x0為Logistic映射的初值，K為128 bit的初始密鑰；

② 將x0帶入混沌函數，其混沌函數為Logistic映射轉化為大整數的形式。其數學表達式為：

(4)

式中，0

③ 將128 bit的值xn+1按字節分組，共16 byte，xn+1=xn+1(0)xn+1(1)...xn+1(15)；

④ 將上述16 byte按位異或，得到1 byte的輸出Y(i)，其中0≤i≤255，Y(i)=xn+1(0)⊕...⊕xn+1(15)，Y(i)∈(0,255)；

⑥ 依次將Y(i)放入S盒中，若Y(i)=Y(j)，j>i，i,j為自然數，則舍去Y(j)，若S盒的256個數值尚未填滿，返回步驟②；若S盒已填滿，則S盒生成結束。

第2部分：使用斜Tent映射對初始S盒進行置亂，得到滿足一定非線性指標和差分均勻度的動態S盒。具體步驟如下：

① 設置斜Tent映射的參數a∈(0,1)和初始值x0∈(0,1)；

② 計算斜Tent映射的混沌迭代方程，得到長度為n的實數序列x1,x2,...,xn；

④ 根據G(i)交換S盒Yi和Yi+n/2位置上的元素，得到新的S盒，計算該S盒的非線性度和差分均勻度，若滿足所設置的門限要求，則S盒生成結束；否則令i=i+1，繼續步驟④；

至此，整個動態S盒的構造結束。

取Logistic映射的初值

x0=9C2B2E74D242D-8279398B9719E5AF043，

每輪運算中Logistic混沌映射迭代200次，經過1 511輪運算之后生成初始S盒；設置Tent映射初值x0=0.235 6，控制參數a=0.423 53，迭代步長n=2 000。設置門限要求：非線性度平均值不小于105，差分均勻度最大值為10，根據這1 000組隨機整數，對初始S盒進行置亂，經過32次置換后得到8×8的S盒。下面給出S盒的部分數值：

3動態S盒性能分析與驗證

S盒設計通常有5個準則：雙射性、非線性度、嚴格雪崩準則、輸出比特間獨立性和差分均勻性。本文還對S盒進行了靈敏度分析，通過改變Logistic混沌映射的初值，即改變系統的密鑰，判斷S盒對密鑰的敏感性。

3.1雙射性

通常要求S盒是可逆的，尤其在代替置換網絡中所使用的S盒必須是雙射的。文獻[4]給出了滿足雙射的充分必要條件：各分量布爾函數fi的線性運算之和為2n-1，即

(5)

式中，ai∈{0,1},(a1,a2,...,an)≠(0,0,...,0)；wt()表示漢明權重。如果式(5)成立，則f是平衡的，且是雙射的。

本文中n=8，根據式(5)，滿足雙射性的標準值是128。該S盒的8個布爾向量共有255種線性組合形式。通過計算每種組合形式下向量異或值的漢明重量，可以發現結果均為28-1=128。因此該S盒滿足雙射性。

3.2非線性度

線性密碼分析的目的是尋找密文、明文和密鑰之間的有效線性表達式。S盒必須具有較高的非線性以抵御線性密碼分析。

在實際運算時，通常將布爾函數f(x)轉換成Walsh譜：

(6)

式中，ω∈GF(2n)；x·ω表示x和ω的點積，定義為x·ω=x1·ω1⊕...⊕xn·ωn。

則Walsh譜表示的非線性度為：

(7)

根據式(7)，S盒的非線性度輸出為104、106、104、108、104、106、104和104。S盒和其他經典S盒[1,2,5,6]的非線性比較如表1所示。

表1　本文S盒非線性度與其他經典S盒比較

從表1中可以看出，S盒的非線性度平均值為105，優于其他幾個經典的S盒生成方案。這說明該S盒能抵擋最佳線性逼近的進攻。

3.3嚴格雪崩準則(SAC)

為抵抗以輸入的改變導致輸出有相對較大改變為基礎的攻擊方法，Webster和Tavare首次提出嚴格雪崩準則。如果函數滿足嚴格雪崩準則，則意味著一個輸入比特的改變，將有一半的輸出結果發生改變。

在實際運用中通過構造相關矩陣來驗證布爾函數f是否滿足SAC。在文獻[7]給出相關矩陣的構造方法，對于相關矩陣A，如果其每個元素的值都接近0.5，則表明S滿足SAC。

通過計算，得到該S盒的相關矩陣：

矩陣的均值為0.501 22，非常接近于理想值0.5。而Jakimoski的相關矩陣的平均值為0.497 2，Tang的相關矩陣的平均值為0.499 3，Chen的相關矩陣的平均值為0.499 9，?zkaynak的相關矩陣的平均值為0.504 8。進行對比，可發現該S盒的相關矩陣優于其余經典的S盒，說明該S盒能夠很好地滿足嚴格雪崩準則。

3.4輸出比特間獨立性(BIC)

文獻[8]中指出，對于其中任意2個布爾函數fj,fk(j≠k)，如果fj⊕fk高度非線性且盡可能地滿足嚴格雪崩準則，則可以保證當一個輸入比特取反時，每個輸出比特對的相關性接近于0。因此，可以通過驗證S盒的任意2個輸出異或fj⊕fk是否滿足嚴格雪崩效應，來校驗S盒的BIC特性。

通過計算，可得fj⊕fk(1≤j≤8,1≤k≤8)的非線性度矩陣：

其均值為103.643。而Jakimoski的BIC-非線性度的平均值為104.25，Tang的BIC-非線性度的平均值為102.96，Chen的BIC-非線性度的平均值為103.36，?zkaynak的BIC-非線性度的平均值為103.82。可以發現S盒在BIC-非線性度與經典的S盒不相上下。

計算輸入序列中一個比特取反前后，輸出序列y的任意2個比特異或值yj⊕yk變化的概率可得BIC-SAC：

BIC-SAC的均值為0.5000 7，非常接近理想值0.5。而Jakimoski的BIC-SAC的平均值為0.503 2，Tang的BIC-SAC的平均值為0.504 4，Chen的BIC-SAC的平均值為0.502 4，?zkaynak的BIC-SAC的平均值為0.500 7。對比發現，S盒的BIC-SAC平均值優于其他的經典S盒，說明該S盒具有較好的輸出比特間獨立性。

3.5差分均勻性

(8)

式中，α∈GF(2n)；β∈GF(2n)。

在實際計算中，也可以用差分逼近概率[10]來表示輸入輸出的異或分布狀況：

(9)

式中，x∈GF(2n)。式(9)即表示給定輸入差分為Δx，輸出差分為Δy的最大可能性。

根據式(9)得到S盒的差分分布表，如表2所示。從表2中可以發現，輸出差分的最大值為10。與經典S盒進行比較，Jakimoski的差分均勻度為10，Tang的差分均勻度為10，Chen的差分均勻度為12，?zkaynak的差分均勻度為10。由于差分表中的最大值越小，S盒的抗差分攻擊能力越好。對比其他S盒的差分均勻度，可以發現該S盒與Tang和?zkaynak的方案同樣具有很好的抗差分攻擊能力。

表2本文S盒的輸入輸出差分分布表

3.6靈敏度分析

除上述5種準則外，動態S盒還需要具有對初始密鑰有較高敏感性的特性。對于上述的128 bit密鑰K改變最低位，得到新的初值K1，此時初值為x0=9C2B2E74D242D8279398B9719E5AF042，產生新的S盒。下面給出了與本文生成的S盒相應位置的部分數值：

通過比較這些相應數值可以看出，即使初始密鑰的改變是微小的，所生成的S盒的變化很大。128 bit的密鑰對應的密鑰空間為2128，那么窮舉攻擊在理論上是不可行的。如果以子密鑰作為動態S盒算法的初值，則隨著每一輪子密鑰的不同，將產生不同的S盒，更加增加了密碼系統的加密強度。

4結束語

本文提出了依據系統密鑰的動態S盒構造方法。該方法利用混沌映射的偽隨機性，解決了S盒的固定結構問題，產生了對密鑰敏感的動態S盒。而該算法主要的優點是通過改變系統的密鑰可以產生許多不同的S盒，并且本文產生的動態S盒通過了評判標準。經過與經典S盒進行對比分析，發現該S盒具有最大的非線性度平均值，最接近0.5的SAC和BIC-SAC，最大值為10的輸出差分。說明S盒可以有效地抵抗線性分析盒差分分析，具有優良的性能，適用于開發新的分組密碼算法。

參考文獻

[1]JAKIMOSKI G,KOCAREV L.Chaos and Cryptography:Block Encryption Ciphers Based on Chaotic Maps[J].Circuits & Systems I Fundamental Theory & Applications IEEE Transactions on,2001,48(2):163-169.

[2]?ZKAYNAK F,?ZER A B.A Method for Designing Strong Sboxes Based on Chaotic Lorenz System[J].Physis Letters A,2010(374):3 733-3 738.

[3]宋春艷.基于混沌理論的信息加密技術研究[D].哈爾濱：哈爾濱工程大學，2013.

[4]ADAM C,TAVARES S.The Structured Design of Cryptographically Good S-boxes[J].JCryptol,1990,3(1):27-41.

[5]CHEN G,CHEN Y,LIAO X F.An Extended Method for Obtaining S-boxes Based on Three-dimentional Chaotic Baker Maps[J].Chaos,Solitons and Fractals,2007,31(3):571-579.

[6]TANG G P,LIAO X F,CHEN Y.A Novel Method for Designing S-boxes Based on Chaotic Maps[J].Chaos,Solitons& Fractals,2005(23):413-419.

[7]WEBSTER A F,TAVARES S E.On the Design of S-Boxes[C]∥Advances in Cryptology CRYPTO ’85 Proceedings.Springer Berlin Heidelberg,1986:523-534.

[8]劉強，方錦清，趙耿，等.基于FPGA技術的混沌加密系統研究[J].物理學報，2012，61(13)：130508-1-5.

[9]BIHAM E,SHAMIR A.Differential Cryptanalysis of DES-like Cryptosystems[J].Journal of Cryptology,1991,4(1):63-72.

[10]HALE J K,VERDYNLUNEL S M.Introduction to Functional Differential Equations[M].New York:Springer-Verlag,1993.

范明慧女，(1989—)，碩士。主要研究方向：數字通信、信道編碼和密碼學。

仰楓帆男，(1966—)，教授，博士生導師。主要研究方向：信道編碼理論和應用、信息論和協作通信等。

作者簡介

收稿日期：2015-12-02

中圖分類號TN918

文獻標識碼A

文章編號1003-3106(2016)03-0033-04

doi:10.3969/j.issn.1003-3106.2016.03.10

引用格式：范明慧,仰楓帆.分組密碼中基于混沌映射的動態S盒構造[J].無線電工程,2016,46(3):33-36,40.