基于高維混沌系統(tǒng)的偽隨機(jī)序列生成器

馬 旭 炯， 于 加 武， 楊 飛 飛， 牟 俊

( 大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 大連 116034 )

0 引 言

偽隨機(jī)序列是具有某種隨機(jī)特性的確定序列，由于其優(yōu)良的隨機(jī)性和接近于白噪聲的統(tǒng)計(jì)特性，在許多科學(xué)技術(shù)和工程領(lǐng)域中有著十分廣泛的應(yīng)用，如衛(wèi)星、飛船軌道、雷達(dá)技術(shù)、保密通信、數(shù)字信息處理系統(tǒng)和擴(kuò)頻通信等[1-3]。使用計(jì)算機(jī)系統(tǒng)并不能得到真正意義上的隨機(jī)序列[4-6]。目前常見的由計(jì)算機(jī)系統(tǒng)迭代產(chǎn)生的基于線性同余理論的m-序列[7-8]、Gold-序列[9-10]等傳統(tǒng)偽隨機(jī)序列，因其復(fù)雜度較低，導(dǎo)致所產(chǎn)生的偽隨機(jī)序列在信息安全中的應(yīng)用存在隱患。同時(shí)，傳統(tǒng)偽隨機(jī)序列在密碼學(xué)設(shè)計(jì)中密碼生成速度也會(huì)受到限制[11]。因此，性能優(yōu)良且安全可靠的偽隨機(jī)序列發(fā)生器的設(shè)計(jì)成為信息安全領(lǐng)域的研究熱點(diǎn)。

混沌系統(tǒng)分為連續(xù)混沌系統(tǒng)和離散混沌系統(tǒng)，不同種類的混沌系統(tǒng)的動(dòng)力學(xué)行為表現(xiàn)不同，所以各自生成的混沌偽隨機(jī)序列的隨機(jī)特性也不同，因此混沌系統(tǒng)的選擇對于偽隨機(jī)序列的生成非常重要[12-13]。連續(xù)混沌系統(tǒng)很多基于此類系統(tǒng)的偽隨機(jī)序列已經(jīng)被證明具有良好的統(tǒng)計(jì)特性，但常用于連續(xù)混沌系統(tǒng)的定步長積分方法在求解微分方程時(shí)易導(dǎo)致其混沌動(dòng)力學(xué)行為退化，而序列復(fù)雜度卻不會(huì)因?yàn)槲又袦u卷數(shù)的增多而提高[14]。離散混沌系統(tǒng)多采用低維混沌系統(tǒng)或在其基礎(chǔ)上改進(jìn)的低維混沌系統(tǒng)來生成偽隨機(jī)序列。Dabal等[15]設(shè)計(jì)了一個(gè)基于一維Logistic映射的偽隨機(jī)序列生成器。李孟婷等[16]基于一維Logistic映射和二維Henon映射提出了一種多級(jí)混沌映射交替變參數(shù)的偽隨機(jī)序列產(chǎn)生方法。張麗姣等[17]設(shè)計(jì)了一個(gè)基于二維離散混沌系統(tǒng)的偽隨機(jī)數(shù)生成器等。這類方法計(jì)算速度快，形式簡單，且系統(tǒng)動(dòng)力學(xué)特性不會(huì)退化。缺點(diǎn)是復(fù)雜度低，易被破譯。而超混沌系統(tǒng)具有兩個(gè)或兩個(gè)以上正李雅普諾夫指數(shù)[18-23]，一般而言其序列隨機(jī)性比普通混沌系統(tǒng)好，所以目前解決這些問題的有效途徑之一就是采用超混沌系統(tǒng)生成偽隨機(jī)序列，可有效提高生成的偽隨機(jī)序列的安全性。

基于上述原因，本研究采用高維離散超混沌系統(tǒng)設(shè)計(jì)高性能的偽隨機(jī)序列，基于修正版Marotto定理構(gòu)造四維離散超混沌映射系統(tǒng)，首先分析其動(dòng)力學(xué)特性，以便選定合適的系統(tǒng)參數(shù)，使得偽隨機(jī)序列生成器產(chǎn)生的混沌偽隨機(jī)序列在理論上具有最好的隨機(jī)性能；其次采用重復(fù)量化算法設(shè)計(jì)出偽隨機(jī)序列生成器；最后對生成的偽隨機(jī)序列進(jìn)行性能測試。

1 四維離散超混沌映射系統(tǒng)及其動(dòng)力學(xué)特性

1.1 四維離散超混沌映射系統(tǒng)

四維離散超混沌映射系統(tǒng)方程：

(1)

式中：令參數(shù)a=4，b=4，c=3.5，d=2，t=4，系統(tǒng)初值[x0，y0，z0，w0]=[0.7，0.8，1.5，0.8]，仿真步長為0.000 1。此時(shí)系統(tǒng)的李雅普諾夫指數(shù)分別為[0.866 5，0.694 1，0.624 8，0.199 3]，表明系統(tǒng)此時(shí)存在不止一個(gè)正的李雅普諾夫指數(shù)，系統(tǒng)為超混沌態(tài)。其超混沌吸引子相圖如圖1所示。

1.2 動(dòng)力學(xué)特性分析

1.2.1 分岔圖和李雅普諾夫指數(shù)譜

取b∈[0，5]，令a=4，c=3.5，d=2，t=4，系統(tǒng)初值[x0，y0，z0，w0]=[0.7，0.8，1.5，0.8]，計(jì)算得系統(tǒng)李雅普諾夫指數(shù)譜和分岔圖，如圖2所示。系統(tǒng)的分岔圖和李雅普諾夫指數(shù)譜的結(jié)果吻合。當(dāng)0≤b≤0.88、1.75≤b≤2.19和2.47≤b≤5時(shí)，系統(tǒng)存在4個(gè)正的李雅普諾夫指數(shù)，系統(tǒng)處于超混沌態(tài)；當(dāng)b∈[1.248，1.252]，b∈[1.556，1.573] 時(shí)，系統(tǒng)中存在兩個(gè)明顯的周期窗口，因此選取混沌序列時(shí)，b的取值應(yīng)盡量避免該周期窗口范圍的值。

(a) x-y平面

(b) x-z平面

(c) x-w平面

圖1 四維離散超混沌系統(tǒng)相圖

Fig.1 Phase diagrams of four-dimensional discrete hyperchaotic system

當(dāng)d∈[0，2.5]時(shí)，其余系統(tǒng)參數(shù)保持不變，仿真得系統(tǒng)李雅普諾夫指數(shù)譜和分岔圖，如圖3所示。系統(tǒng)的分岔圖和李雅普諾夫指數(shù)譜相對應(yīng)。當(dāng)1.19≤d≤1.38和1.53≤d≤5時(shí)，系統(tǒng)的4個(gè)李雅普諾夫指數(shù)均為正值，說明系統(tǒng)狀態(tài)為超混沌態(tài)，但系統(tǒng)在d∈[0.586，0.594]時(shí)存在周期窗口，因此參數(shù)d的選取也應(yīng)避免該周期窗口范圍內(nèi)的值。

(a) 分岔圖(b∈[0，5])

(b) 分岔圖(b∈[1.23，1.27])

(c) 分岔圖(b∈[1.54，1.6])

(d) LE (b∈[0，5])

(e) LE (b∈[1.23，1.27])

(f) LE (b∈[1.54，1.60])

圖2 系統(tǒng)隨b變化的分岔圖和李雅普諾夫指數(shù)譜
Fig.2 Bifurcation diagrams and Lyapunov exponent spectra of the system asbchanges

(a) 分岔圖(d∈[0，2.5])

(b) 分岔圖(d∈[0.58，0.6])

(c) LE (d∈[0，2.5])

(d) LE (d∈[0.58，0.6])

圖3 系統(tǒng)隨d變化時(shí)的分岔圖和李雅普諾夫指數(shù)譜

Fig.3 Bifurcation diagrams and Lyapunov exponent spectra of the system asdchanges

1.2.2 混沌序列復(fù)雜度分析

為了度量和分析混沌序列的復(fù)雜性，采用排列熵復(fù)雜度算法進(jìn)行分析，該算法計(jì)算簡便，易于實(shí)現(xiàn)[24]。取混沌序列長度為10 000，其他系統(tǒng)參數(shù)不變，取b∈[0，5]和d∈[0，2.5]時(shí)，得到混沌序列的排列熵復(fù)雜度，如圖4所示。可以明顯地看出，在b和d變化時(shí)，系統(tǒng)的動(dòng)力學(xué)特性的變化趨勢與分岔圖和李雅普諾夫指數(shù)譜一致。

(a) 排列熵復(fù)雜度(b∈[0，5])

(b) 排列熵復(fù)雜度(d∈[0，2.5])

圖4 排列熵復(fù)雜度

Fig.4 Permutation entropy complexity

在采用超混沌映射設(shè)計(jì)偽隨機(jī)序列生成器時(shí)，為確保系統(tǒng)具有多個(gè)正的李雅普諾夫指數(shù)，選取a=4，b=4，c=3.5，d=2，t=4，使系統(tǒng)具有4個(gè)正的李雅普諾夫指數(shù)，用以設(shè)計(jì)超混沌偽隨機(jī)序列生成器。

1.2.3 概率密度

如經(jīng)典Logistic映射所生成的混沌序列，其概率密度函數(shù)分布近似于切比雪夫型，特點(diǎn)是中間均勻，兩頭稠密，這樣的概率密度分布能減少盲目搜索，加快搜索效率[25]。四維離散超混沌映射系統(tǒng)生成的4個(gè)離散序列Xn、Yn、Zn、Wn的概率密度，如圖5所示。其概率密度均相似于切比雪夫型分布，說明其概率密度分布符合需求，生成的混沌序列隨機(jī)性能良好。

(a) 概率密度測試(Xn序列)

(b) 概率密度測試(Yn序列)

(c) 概率密度測試(Zn序列)

(d) 概率密度測試(Wn序列)

圖5 概率密度測試

Fig.5 Probability density test

2 偽隨機(jī)序列生成器設(shè)計(jì)

混沌偽隨機(jī)序列是將混沌系統(tǒng)產(chǎn)生的序列進(jìn)行量化后所得的二進(jìn)制序列，這個(gè)二進(jìn)制序列包含混沌系統(tǒng)的隨機(jī)性。在生成偽隨機(jī)序列的過程中，量化是一個(gè)重要的環(huán)節(jié)，量化算法的選擇直接影響到生成的偽隨機(jī)序列的隨機(jī)性、復(fù)雜性以及使用安全性[26]。因此，為保證偽隨機(jī)序列生成器的性能，必須選取合適的量化方法。取a=4，b=4，c=3.5，d=2，t=4，系統(tǒng)初值[x0，y0，z0，w0]=[0.7，0.8，1.5，0.8]，將系統(tǒng)生成的4個(gè)超混沌序列采用重復(fù)量化算法進(jìn)行量化，具體步驟如下：

步驟1設(shè)定系統(tǒng)參數(shù)和初值后，迭代N次用以消除暫態(tài)效應(yīng)保證系統(tǒng)進(jìn)入混沌態(tài)。繼續(xù)迭代超混沌系統(tǒng)得到4個(gè)實(shí)數(shù)值xn、yn、zn、wn，通過式(2)得到4個(gè)新的實(shí)數(shù)值x′n、y′n、z′n、w′n。

k′=πl(wèi)nk，k=xn，yn，zn，wn

(2)

步驟2通過式(3)去掉x′n、y′n、z′n、w′n4個(gè)實(shí)數(shù)值的整數(shù)部分，保留實(shí)數(shù)值的小數(shù)部分A=(Ax，Ay，Az，Aw)。

A=abs(k′)-floor(abs(k′))

(3)

其中abs和floor分別是Matlab軟件中的絕對值函數(shù)和取整函數(shù)。

步驟3采用乘二取整法，將小數(shù)A用二進(jìn)制表示出來。

A′=a1a2…am

(4)

其中A′=(A′x，A′y，A′z，A′w)，am可取0或1，m為計(jì)算精度。

步驟4將所得4個(gè)二值序列按式(5)進(jìn)行異或運(yùn)算得到一個(gè)新的序列S。

S=A′x⊕A′y⊕A′z⊕A′w

(5)

步驟5繼續(xù)迭代超混沌系統(tǒng)，重復(fù)上述4個(gè)步驟直至獲得所需長度的超混沌偽隨機(jī)序列。

上述算法中，超混沌系統(tǒng)的初值產(chǎn)生的序列x0、y0、z0、w0和迭代次數(shù)N可以作為密鑰，如果計(jì)算機(jī)的精度是16，則算法的密鑰空間可達(dá)2212，所以本算法密鑰空間對一般的窮舉攻擊有足夠的抵御能力。

3 偽隨機(jī)序列性能分析

3.1 NIST SP800-22測試

檢測偽隨機(jī)數(shù)隨機(jī)性能的標(biāo)準(zhǔn)有很多，如美國聯(lián)邦信息處理標(biāo)準(zhǔn)FIPS 140-2，Marsaglia制定的Diehard Battery檢測以及美國國家標(biāo)準(zhǔn)技術(shù)研究所(NIST)制定的隨機(jī)序列測試標(biāo)準(zhǔn)SP 800-22等。本研究采用了現(xiàn)階段應(yīng)用最廣泛、最具權(quán)威性的NIST SP800-22標(biāo)準(zhǔn)對本算法產(chǎn)生的偽隨機(jī)序列進(jìn)行檢測，該標(biāo)準(zhǔn)一共有15項(xiàng)測試指標(biāo)，將理想隨機(jī)序列作為參考，在統(tǒng)計(jì)特性上從不同角度檢驗(yàn)偽隨機(jī)序列的偏離程度，普遍認(rèn)為，能通過該檢測的序列具有良好的偽隨機(jī)性能[22]。SP 800-22標(biāo)準(zhǔn)的每項(xiàng)測試都會(huì)提供通過率和P值分布的均勻性兩個(gè)判斷依據(jù)。所有測試均取顯著水平α=0.01，測試序列β組，則可定義通過率的置信區(qū)間為

(6)

當(dāng)通過率落在此置信區(qū)間內(nèi)，表示序列通過測試；而若P值>0.000 1，則表明被測序列的P值是均勻分布的，序列是隨機(jī)的。

所用的測試條件為：顯著水平α=0.01，測試序列β=100組，每組長度為106bit，置信區(qū)間為[0.96，1]。測試后得到的結(jié)果如表1所示。從表1的結(jié)果可以看出，所設(shè)計(jì)的偽隨機(jī)序列生成器生成的偽隨機(jī)序列通過了NIST SP800-22測試，說明偽隨機(jī)序列具有較良好的偽隨機(jī)性能。通過與Li等[27]提出的基于Logistic混沌映射系統(tǒng)和Akhshani等[28]使用三維離散超混沌映射系統(tǒng)設(shè)計(jì)的偽隨機(jī)序列生成器所生成的混沌偽隨機(jī)序列的NIST測試結(jié)果相比較，所設(shè)計(jì)的基于高維離散混沌系統(tǒng)的偽隨機(jī)序列生成器生成的混沌偽隨機(jī)序列的NIST測試結(jié)果，有12項(xiàng)指標(biāo)的P值大于文獻(xiàn)[27]中的結(jié)果，有11項(xiàng)指標(biāo)的P值大于文獻(xiàn)[28]中的結(jié)果，因此，此偽隨機(jī)序列的隨機(jī)性更好，在保密通信等信息安全領(lǐng)域中的應(yīng)用更加安全可靠。

3.2 相關(guān)性分析

相關(guān)性是測試偽隨機(jī)序列的一個(gè)重要指標(biāo)，良好的相關(guān)性是系統(tǒng)能夠可靠運(yùn)行的重要保證，相關(guān)性包括自相關(guān)和互相關(guān)。理想的隨機(jī)序列其自相關(guān)函數(shù)接近于δ函數(shù)，互相關(guān)函數(shù)接近于0。δ函數(shù)的定義為

(7)

令a=4，b=4，c=3.5，d=2，t=4，系統(tǒng)初值[x0，y0，z0，w0]=[0.7，0.8，1.5，0.8]，從公式(4)所得的序列A′中隨機(jī)抽取長度為60 000的二進(jìn)制序列，其自相關(guān)性和互相關(guān)性，如圖6所示。該偽隨機(jī)序列生成器生成的二進(jìn)制序列A′的自相關(guān)函數(shù)接近于δ函數(shù)，互相關(guān)函數(shù)接近于0，說明其自相關(guān)性和互相關(guān)性良好。

表1 NIST SP800-22測試結(jié)果Tab.1 Test results of NIST SP800-22

(a) 自相關(guān)

(b) 互相關(guān)

圖6 相關(guān)性分析

Fig.6 Correlation analysis

4 結(jié) 論

通過對基于修正版Marotto定理構(gòu)造的四維離散超混沌映射系統(tǒng)的動(dòng)力學(xué)特性進(jìn)行分析，確定了系統(tǒng)處于超混沌狀態(tài)的參數(shù)范圍，為偽隨機(jī)序列生成器的實(shí)現(xiàn)提供了理論依據(jù)。

通過結(jié)合重復(fù)量化算法設(shè)計(jì)了偽隨機(jī)序列生成器，仿真結(jié)果表明，該偽隨機(jī)序列生成器能將該超混沌系統(tǒng)生成的序列量化為超混沌偽隨機(jī)序列。對量化后的超混沌偽隨機(jī)序列使用NIST SP800-22隨機(jī)數(shù)檢驗(yàn)標(biāo)準(zhǔn)進(jìn)行測試，測試的結(jié)果表明本文所設(shè)計(jì)的偽隨機(jī)序列生成器生成的序列具有良好的隨機(jī)性，并通過與其他文獻(xiàn)對比表明，使用高維離散超混沌映射系統(tǒng)設(shè)計(jì)的偽隨機(jī)序列生成器，其性能比使用低維混沌偽隨機(jī)序列生成器的性能更好。

經(jīng)分析超混沌偽隨機(jī)序列的自相關(guān)性和互相關(guān)性，可見此生成器生成的序列具有接近于δ函數(shù)的自相關(guān)性和接近于0的互相關(guān)性。因此，此混沌偽隨機(jī)序列生成器生成的序列可應(yīng)用于保密通信等信息安全領(lǐng)域。