臧鴻雁 黃慧芳

?

基于均勻化混沌系統(tǒng)生成S盒的算法研究

臧鴻雁①黃慧芳*②

①(北京科技大學(xué)數(shù)理學(xué)院 北京 100083)②(廈門(mén)大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院 漳州 363105)

該文給出了一個(gè)新的二次多項(xiàng)式混沌系統(tǒng)，并利用系統(tǒng)與Tent映射拓?fù)涔曹椀男再|(zhì)，給出了系統(tǒng)的概率密度函數(shù)，基于概率密度的形式，進(jìn)一步設(shè)計(jì)了一個(gè)變換函數(shù)，實(shí)現(xiàn)了系統(tǒng)的均勻化。針對(duì)均勻化前后的混沌系統(tǒng)構(gòu)造了S盒生成算法，對(duì)該算法產(chǎn)生的300個(gè)S盒進(jìn)行差分概率(DP)和線性概率(LP)的統(tǒng)計(jì)分析，結(jié)果表明均勻化后混沌系統(tǒng)產(chǎn)生的S盒的DP和LP略?xún)?yōu)于均勻化前的值。

混沌系統(tǒng)；均勻化；拓?fù)涔曹?；S盒

1 引言

1975年，Li等人[1]發(fā)表了著名的“周期三蘊(yùn)含混沌”一文，首次用數(shù)學(xué)定義描述了“混沌”一詞。通過(guò)研究混沌系統(tǒng)的復(fù)雜非線性動(dòng)力學(xué)現(xiàn)象能夠發(fā)現(xiàn)其具有偽隨機(jī)性、遍歷性和初值敏感性等特性。自1989年，Matthews[2]提出“混沌密碼”后，人們對(duì)混沌系統(tǒng)及其應(yīng)用的了解越來(lái)越深入。密碼學(xué)家分析得出一個(gè)好的密碼系統(tǒng)本質(zhì)上也是一個(gè)混沌系統(tǒng)的結(jié)論[3]。這一發(fā)現(xiàn)挖掘了混沌在密碼學(xué)領(lǐng)域內(nèi)的應(yīng)用潛力，自20世紀(jì)80年代以來(lái)該領(lǐng)域成為了日益熱門(mén)的研究方向[4]。

混沌系統(tǒng)具有各態(tài)歷經(jīng)的特性，利用混沌映射的概率密度可以描述系統(tǒng)長(zhǎng)期的統(tǒng)計(jì)特征。文獻(xiàn)[5]通過(guò)證明Logistic映射與Tent映射的拓?fù)涔曹楆P(guān)系以及Chebyshev映射與Tent映射的拓?fù)涔曹楆P(guān)系，推出了Logistic映射和Chebyshev映射的概率密度。通過(guò)混沌映射的概率密度函數(shù)可以發(fā)現(xiàn)大部分混沌序列不服從均勻分布。2011年，文獻(xiàn)[6]中給出了一個(gè)將Logistic混沌序列轉(zhuǎn)化為服從均勻分布的隨機(jī)序列生成方法。

S盒是多數(shù)分組密碼中的唯一非線性部件，設(shè)計(jì)具有良好性能的S盒是分組密碼算法設(shè)計(jì)的關(guān)鍵要素之一。一個(gè)S盒本質(zhì)上可以看作映射，或者可以寫(xiě)作：，它是將位輸入映射到位輸出的非線性映射。構(gòu)造動(dòng)態(tài)S盒的方法有很多[7]，利用混沌系統(tǒng)良好的偽隨機(jī)性質(zhì)來(lái)構(gòu)造動(dòng)態(tài)S盒已經(jīng)成為構(gòu)造S盒的一個(gè)重要方法[8]。

本文利用文獻(xiàn)[9]提出的一般二次多項(xiàng)式映射存在3-周期點(diǎn)的充分必要條件構(gòu)造了一個(gè)新的二次多項(xiàng)式混沌系統(tǒng)，并依據(jù)該系統(tǒng)與Tent映射拓?fù)涔曹椀男再|(zhì)，給出了系統(tǒng)的概率密度函數(shù)，在此概率密度的基礎(chǔ)上對(duì)該系統(tǒng)進(jìn)行了均勻化處理；分別利用均勻化前后的混沌系統(tǒng)設(shè)計(jì)了動(dòng)態(tài)S盒生成算法，對(duì)算法生成的300個(gè)S盒的性能指標(biāo)進(jìn)行統(tǒng)計(jì)分析，發(fā)現(xiàn)利用均勻化后系統(tǒng)能夠產(chǎn)生性能更好的S盒。

本文其余部分安排如下：在第2節(jié)中提出了一個(gè)新的混沌系統(tǒng)，并基于概率密度函數(shù)對(duì)系統(tǒng)進(jìn)行了均勻化處理。在第3節(jié)中，對(duì)均勻化前后的混沌系統(tǒng)進(jìn)行了統(tǒng)計(jì)直方圖和熵的對(duì)比分析。第4節(jié)中設(shè)計(jì)了一個(gè)動(dòng)態(tài)S盒的生成方法，利用均勻化前后的混沌系統(tǒng)分別產(chǎn)生了300個(gè)S盒，并進(jìn)行了S盒性能的對(duì)比。第5節(jié)總結(jié)全文。

2 二次多項(xiàng)式混沌系統(tǒng)的均勻化處理

文獻(xiàn)[9]提出了一般非線性二次多項(xiàng)式的3-周期點(diǎn)的等價(jià)命題。

引理1[9]二次多項(xiàng)式有實(shí)的3-周期點(diǎn)的充分必要條件是。

定義1[10]設(shè)和為兩個(gè)映射，如果存在一個(gè)可逆映射，使得成立，則稱(chēng)和是拓?fù)涔曹椀摹４颂幈硎緝蓚€(gè)映射的復(fù)合。

拓?fù)涔曹検莿?dòng)力系統(tǒng)中的重要理論。如果兩個(gè)系統(tǒng)滿足拓?fù)涔曹楆P(guān)系，則它們具有相同的動(dòng)力行為。

基于引理1，本文構(gòu)造了新的1維混沌系統(tǒng)為

將系統(tǒng)表示為

(2)

定理1 混沌系統(tǒng)

與Tent映射是拓?fù)涔曹椀摹?/p>

令Tent映射

和連續(xù)可逆函數(shù)

(5)

定理2 混沌系統(tǒng)

的概率密度函數(shù)為

(7)

(8)

由系統(tǒng)式(1)的概率密度函數(shù)可知，該二次多項(xiàng)式混沌系統(tǒng)產(chǎn)生的序列不是均勻分布的，意味著其產(chǎn)生的混沌序列容易具有明顯的統(tǒng)計(jì)特性，不利于推廣應(yīng)用。為了使其服從均勻分布，以下對(duì)式(1)進(jìn)行均勻化處理。

則隨機(jī)變量為

(10)

(12)

以上是利用原混沌系統(tǒng)的概率密度函數(shù)對(duì)其進(jìn)行均勻化處理的方法。由證明過(guò)程可知，在文中給定區(qū)間內(nèi)，均勻分布的隨機(jī)變量與原隨機(jī)變量滿足一一對(duì)應(yīng)關(guān)系，因?yàn)槭鞘?1)混沌系統(tǒng)的變量，從而系統(tǒng)

必是混沌系統(tǒng)，并且與式(1)系統(tǒng)有著相同的Lyapunov指數(shù)。

3 二次多項(xiàng)式混沌系統(tǒng)的熵分析

以下針對(duì)均勻化前混沌系統(tǒng)式(1)和均勻化后系統(tǒng)式(13)產(chǎn)生的序列從直方圖統(tǒng)計(jì)、信息熵和離散熵等方面進(jìn)行了分析，驗(yàn)證均勻化方法的有效性。

3.1 統(tǒng)計(jì)分析

圖1(a)是均勻化前混沌系統(tǒng)生成的序列的統(tǒng)計(jì)直方圖，圖1(b)是均勻化后反三角函數(shù)生成的序列的統(tǒng)計(jì)直方圖。由對(duì)比圖可見(jiàn)，處理后的混沌序列均勻性明顯增強(qiáng)。

3.2 信息熵分析

信息熵是信息論中用以度量信源不確定性程度的概念，最早由香農(nóng)提出。以下是本文中均勻化前后系統(tǒng)產(chǎn)生的混沌序列的信息熵檢測(cè)。令離散混沌序列長(zhǎng)度為，將式(13)迭代得到的離散混沌序列，將序列值域等分成個(gè)區(qū)間，統(tǒng)計(jì)落在每個(gè)區(qū)間內(nèi)的值的個(gè)數(shù)，記為。計(jì)算每個(gè)區(qū)間的統(tǒng)計(jì)概率，有。根據(jù)最大信息熵原理，信息熵最大值為，其中表示統(tǒng)計(jì)區(qū)間個(gè)數(shù)，對(duì)應(yīng)通信系統(tǒng)中的信源符號(hào)數(shù)。下面選定序列長(zhǎng)度，分別測(cè)試時(shí)均勻化前后序列的信息熵與最大熵，比較結(jié)果如表1。

表1 均勻化前后混沌序列的信息熵對(duì)比

3.3 離散熵分析

2007年Amigo等人[11]基于排列熵(PE)定義，提出了有限集合上的離散熵(DE)的概念，可替代拓?fù)潇睾饬肯到y(tǒng)的混沌程度。該定義為

從圖2(a)、圖2(c)、圖2(e)中式(1)系統(tǒng)的熵和離散熵圖像可以看出，系統(tǒng)離散熵近似于熵偏移固定長(zhǎng)度后的圖像，這也從某種程度說(shuō)明，離散熵能夠有效衡量系統(tǒng)的混沌程度；圖2(b)、圖2(d)、圖2(f)顯示均勻化前后系統(tǒng)的離散熵完全相同，圖2表明，經(jīng)過(guò)本文中的均勻化方法處理之后，混沌系統(tǒng)的混沌特性不會(huì)被破壞，同時(shí)均勻性得到了有效的改善。

4 基于均勻化混沌系統(tǒng)構(gòu)造S盒

本文分別利用均勻化前后的兩個(gè)混沌系統(tǒng)式(1)和式(13)設(shè)計(jì)動(dòng)態(tài)S盒生成算法，并對(duì)兩組S盒進(jìn)行統(tǒng)計(jì)分析和性能檢測(cè)。具體的算法和分析結(jié)果如下。

圖1 統(tǒng)計(jì)直方圖

圖2 均勻化前后系統(tǒng)K熵與離散熵分析對(duì)比圖

4.1 S盒算法構(gòu)造

(4)從前往后依次取位置序列中不相等的256個(gè)變量作為最終的S盒序列。

在保持算法中參數(shù)一致的情況下，將步驟(2)中產(chǎn)生置亂效果的混沌系統(tǒng)分別用均勻化前的式(1)系統(tǒng)和均勻化后的式(13)系統(tǒng)替換，基于不同的初始值動(dòng)態(tài)生成S盒序列。

檢測(cè)生成的300個(gè)混沌S盒的差分概率(DP)和線性概率(LP)，并統(tǒng)計(jì)各個(gè)指標(biāo)值對(duì)應(yīng)的S盒的個(gè)數(shù)，作直方圖如下，其中圖3為利用均勻化前混沌系統(tǒng)生成的S盒的統(tǒng)計(jì)。圖4為利用均勻化后混沌系統(tǒng)生成的S盒的統(tǒng)計(jì)。

差分概率(DP)用以度量S盒抵抗差分密碼攻擊的能力，DP越小，S盒越能夠抵抗差分攻擊。而線性概率(LP)用來(lái)度量S盒對(duì)于線性密碼攻擊的抵抗能力，LP越小，抵抗能力越強(qiáng)。從兩個(gè)圖的對(duì)比中可以看出，基于均勻化后混沌系統(tǒng)生成的DP, LP指標(biāo)值較好的S盒數(shù)量相對(duì)更多，進(jìn)一步說(shuō)明本文提出的均勻化方法可以有效地改善混沌系統(tǒng)的均勻性，并保持良好的混沌特性。

4.2 S盒性能分析

下面從均勻化后的混沌系統(tǒng)構(gòu)造生成的S盒中選取出一個(gè)DP, LP指標(biāo)值良好的進(jìn)行其他密碼學(xué)性能分析，并且與近兩年內(nèi)發(fā)表的文獻(xiàn)中構(gòu)造的混沌S盒進(jìn)行對(duì)比，檢驗(yàn)本文構(gòu)造生成的S盒是否適用于分組密碼算法設(shè)計(jì)中。

表2為選取的均勻化后混沌系統(tǒng)生成的S盒序列。對(duì)該S盒的雙射特性，非線性度，嚴(yán)格雪崩準(zhǔn)則，輸出比特間獨(dú)立性，差分概率，線性概率和Lyapunov指數(shù)等指標(biāo)依次進(jìn)行分析。

圖3 均勻化前系統(tǒng)生成S盒數(shù)

圖4 均勻化后系統(tǒng)生成S盒數(shù)

表2 均勻化混沌系統(tǒng)式(13)生成的S盒序列

對(duì)雙射特性進(jìn)行檢測(cè)，S盒8個(gè)分量布爾函數(shù)的線性運(yùn)算之和都為128，充分滿足雙射特性。

檢測(cè)S盒的嚴(yán)格雪崩準(zhǔn)則和輸出比特獨(dú)立性時(shí)，直接看相關(guān)矩陣對(duì)比可能不能直觀看出差距。為了比較滿足嚴(yán)格雪崩效應(yīng)的程度，利用公式估計(jì)了相關(guān)矩陣與理論值0.5的偏移量，將第1個(gè)相關(guān)矩陣的偏移量記為，第2個(gè)相關(guān)矩陣與0.5理論值的偏移量記為。本文構(gòu)造的S盒與現(xiàn)有S盒的兩個(gè)偏移量的比較如表3所示。我們希望S盒的相關(guān)矩陣元素與理論值越接近越好，也就是偏移量越小越好。從表3的對(duì)比結(jié)果可見(jiàn)，本文S盒較好地滿足嚴(yán)格雪崩準(zhǔn)則和輸出比特間獨(dú)立性。

表3 S盒的對(duì)比

表3 S盒的對(duì)比

S盒 均勻化后系統(tǒng)生成的S盒0.033453130.01692857 文獻(xiàn)[12]中的S盒0.060421870.01771428 文獻(xiàn)[13]中的S盒0.039156250.01664286 文獻(xiàn)[14]中的S盒0.034718750.01546429

利用文獻(xiàn)[15]中提出的S盒的Lyapunov指數(shù)定義，映射的離散Lyapunov指數(shù)揭示的是雙射映射中自變量改變1 bit時(shí)，狀態(tài)值變化位數(shù)的情況[15]。因而 Lyapunov指數(shù)越大，說(shuō)明自變量改變引起的函數(shù)值變化越大，混亂程度越高。本文構(gòu)造S盒的DP, LP及其Lyapunov指數(shù)結(jié)果與文獻(xiàn)中結(jié)果的對(duì)比見(jiàn)表4。

表4 S盒的指數(shù)對(duì)比

表4 S盒的指數(shù)對(duì)比

S盒DPLP 均勻化后系統(tǒng)生成的S盒0.039062500.054931641.79624435 文獻(xiàn)[12]中的S盒0.062500000.129150391.60528688 文獻(xiàn)[13]中的S盒0.039062500.054931641.76551996 文獻(xiàn)[14]中的S盒0.039062500.062500001.82665493

5 結(jié)論

本文提出了一個(gè)新的二次多項(xiàng)式混沌系統(tǒng)，利用拓?fù)涔曹椑碚摻o出了系統(tǒng)的概率密度函數(shù)，進(jìn)一步提出一個(gè)變換函數(shù)對(duì)系統(tǒng)進(jìn)行了均勻化處理。為了驗(yàn)證均勻化方法的效果，對(duì)均勻化前后系統(tǒng)生成的混沌序列進(jìn)行了直方圖統(tǒng)計(jì)、信息熵分析和離散熵分析。分析結(jié)果表明了均勻化方法的有效性。本文基于混沌系統(tǒng)設(shè)計(jì)了一個(gè)新的構(gòu)造S盒的算法，利用均勻化前后的混沌系統(tǒng)分別生成兩組各300個(gè)S盒并對(duì)其DP, LP指標(biāo)進(jìn)行統(tǒng)計(jì)分析。通過(guò)差分及線性攻擊的分析對(duì)比可見(jiàn)，本文均勻化方法處理的混沌系統(tǒng)能夠產(chǎn)生密碼性更好的S盒。這些S盒可以為進(jìn)一步設(shè)計(jì)分組密碼算法提供良好的非線性資源。

[1] LI Tienyien and YORKE J A. Period three implies chaos[J]., 1975(82): 985-992.

[2] MATTHEWS R. On the serivation of a “chaotic” encryption algorithm[J]., 1989, 13(1): 29-42.

[3] GOTZ M, KELBER K, and SCHWARZ W. Discrete-time chaotic coders for information encryption--Part 1: Systematic structural design[C]. Workshop on Nonlinear Dynamics of Electronic Systems, Moscow, Russia, 1997: 21-26.

[4] KOCAREV L, JAKIMOSKI G, STOJANOVSKI T,. From chaotic maps to encryption schemes[C]. IEEE International Symposium on Circuits, & Systems. Monterey, USA, 1998: 514-517.

[5] 何振亞, 李克, 楊綠溪. 具有良好安全性能的混沌映射二進(jìn)制序列[J]. 電子與科學(xué)學(xué)刊, 1999, 21(5): 646-651.

HE Zhenya, LI Ke, and YANG Luxi. Chaotic Map Binary Sequences with Good Security[J]., 1999, 21(5): 646-651.

[6] 曹光輝, 胡凱, 佟維. 基于Logistic均勻分布圖像置亂方法[J]. 物理學(xué)報(bào), 2011, 60(11): 125-132.

CAO Guanghui, HU Kai, and TONG Wei. Image scrambling based on logistic uniform distribution[J]., 2011, 60(11): 125-132.

[7] TERRY R. Substitution cipher with pseudo-random shuffling: The dynamic substitution combiner[J]., 1990, 14(4): 289-303.

[8] WONG K W, HO S W, and YUNG C K. A chaotic cryptography scheme for generating short cipher text[J]., 2003, 310(1): 67-73.

[9] 周海玲, 宋恩彬. 二次多項(xiàng)式映射的3-周期點(diǎn)判定[J]. 四川大學(xué)學(xué)報(bào)(自然科學(xué)版), 2009, 46(3): 561-564. doi: 103969/j. issn. 0490-6756.2009.03-009.

ZHOU H L and SONG E B. Discrimination of the 3-periodic points of a quadratic polynomial[J].(), 2009, 46(3): 561-564. doi: 103969/j.issn.0490-6756.2009.03-009.

[10] 郝柏林. 從拋物線談起--混沌動(dòng)力學(xué)引論[M]. 第2版, 北京: 北京大學(xué)出版社, 2013, 114-118.

HAO B L. Starting with Parabola: An Introduction to Chaotic Dynamics[M]. 2nd Edition, Beijing: Peking University Press, 2013, 114-118.

[11] AMIGO J M, KOCAREV L, and TOMOVSKI I. Discrete entropy[J]., 2007, 228(1): 77-85.

[12] KHAN M, SHAH T, and BATOOL S I. Construction of S-box based on chaotic Boolean functions and its application in image encryption[J].&, 2016, 27(3): 677-685.

[13] 韓丹丹, 閔樂(lè)泉, 趙耿, 等. 一維魯棒混沌映射及S盒的設(shè)計(jì)[J]. 電子學(xué)報(bào), 2015, 43(9): 1770-1775. doi: 10.3969/j.issn. 0372-2112.2015.09.014.

HAN D, MIN L, ZHAO G,. One-dimensional robust chaotic map and the construction of S-box[J]., 2015, 43(9): 1770-1775. doi: 10.3969/j. issn.0372-2112.2015.09.014.

[14] LIU G, YANG W, LIU W,. Designing S-boxes based on 3-D four-wing autonomous chaotic system[J]., 2015, 82(4): 1867-1877. doi: 10.1007/s11071-015- 2283-y.

[15] 臧鴻雁, 范修斌, 閔樂(lè)泉, 等. S-盒的 Lyapunov 指數(shù)研究[J]. 物理學(xué)報(bào), 2012, 61(20): 200508.

ZANG H, FAN X, MIN L,. Research of Lyapunov exponent of S-boxes[J]., 2012, 61(20): 200508.

Research on Algorithm of Generating S-box Based on Uniform Chaotic System

ZANG Hongyan①HUANG Huifang②

①(,,100083,)②(,,363105,)

A new quadratic polynomial chaotic system is given and homogenized based on its probability density function. Then, based on the chaotic systems before and after homogenization, an S-box generation algorithm is constructed. By numerical simulation, the algorithm dynamically generates 300 S-boxes and then analyses their Differential Probability (DP) and Linear Probability (LP). The statistical results show that the uniform chaotic system can produce better performance of S-boxes.

Chaotic system; Homogenization; Topological conjugation; S-box

TN918. 1

A

1009-5896(2017)03-0575-07

10.11999/JEIT160535

2016-05-26；改回日期：2016-10-27；

2016-12-20

黃慧芳 13661363592@163.com

國(guó)家自然科學(xué)基金(61170037)

The National Natural Science Foundation of China (61170037)

臧鴻雁： 女，1973年生，副教授，研究方向?yàn)榉蔷€性系統(tǒng)同步理論與混沌密碼學(xué).

黃慧芳： 女，1991年生，助教，研究方向?yàn)榛煦缑艽a學(xué).