李紅燕，楊萬利

裝甲兵工程學院基礎(chǔ)部，北京 100072

時空混沌二值化方法研究

李紅燕，楊萬利

裝甲兵工程學院基礎(chǔ)部，北京 100072

1 引言

密碼學中序列密碼的安全性依賴于偽隨機序列的隨機性和不可預測性。由于混沌系統(tǒng)可以提供具有良好隨機性能的偽隨機序列，因此在密碼學中具有很大的應(yīng)用價值。將混沌實值序列直接應(yīng)用于加密系統(tǒng)是不安全的[1]，也不實用，所以更多的應(yīng)用是由混沌序列生成的二值序列。在擴頻通信系統(tǒng)中，抗干擾、抗噪聲、抗截獲、信息數(shù)據(jù)隱蔽和保密、多徑保護、抗衰落、實現(xiàn)同步與捕捉等都與擴頻序列的隨機性能密切相關(guān)，所以擴頻序列的隨機性能的好壞是很重要的。實值序列二值化的問題是混沌應(yīng)用的第一步，該過程將直接影響后續(xù)序列的隨機性、復雜性，最終影響系統(tǒng)的安全性。因此有必要對產(chǎn)生混沌二值偽隨機序列的算法進行研究，使得生成的偽隨機序列滿足各種安全需求，避免系統(tǒng)遭到攻擊。

由混沌系統(tǒng)產(chǎn)生隨機序列，首先要選擇混沌系統(tǒng)。采用低維混沌系統(tǒng)，一方面有被攻破的危險[2]，另一方面，利用現(xiàn)有的量化方法得到的二值序列都不能滿足隨機性要求[3]。于是人們開始嘗試使用超混沌系統(tǒng)[4-5]、帶時延的混沌系統(tǒng)[6]或時空混沌系統(tǒng)[7-11]來產(chǎn)生混沌序列。

最主要的混沌二值偽隨機序列的產(chǎn)生方法是符號函數(shù)二值化法。近年來，也有相關(guān)文獻采用新的方法如比較法、區(qū)間法等來生成混沌二值偽隨機序列[7，12]，但是它們在原理上都類似，有的則是多種方法的組合。例如，文獻[13]使用了一種二值化方法，將序列歸一化后轉(zhuǎn)換成二進制形式，但文獻[14]證明該方法與區(qū)間法是等價的。而且每一種方法都是針對一類特出的混沌系統(tǒng)提出的。事實上，目前沒有公認的提取方法對所有的混沌序列有效，所以有必要針對混沌系統(tǒng)的特點研究二值序列的提取方法。

本文基于耦合映像格子模型，研究時空混沌序列的二值化方法。研究顯示采用耦合映像格子模型產(chǎn)生的時空混沌序列由符號函數(shù)二值化法得到的混沌二值偽隨機序列的性能也有缺陷[12]。文獻[12]中給出了一種改進的符號函數(shù)二值化的方法。將一個格點的值取反，加上另外一個格點的值，但是該方法并不能適合所有類型的耦合映像格子模型。本文在符號函數(shù)二值化法的基礎(chǔ)上，給出了一種新的二值化方法——基于符號函數(shù)二值化法的閾值調(diào)整技術(shù)和序列抽取技術(shù)相結(jié)合的二值化方法，采用嚴格的NISΤ（美國國家標準與技術(shù)委員會）測試標準[15]對得到的二值偽隨機序列進行了測試，通過大量的測試和分析說明得到的序列性能良好。

2 混沌序列的生成

最常用的生成時空混沌序列的系統(tǒng)為單向耦合映像格子（One-way Coupled Map Lattice，OCML）：

其中f(x)=4x(1-x)，x∈(0，1)，n表示離散化后的時間，i表示格子空間坐標。ε為耦合強度，當0.75〈ε〈1時，具有相同驅(qū)動序列的兩個不同的耦合映像格子系統(tǒng)能夠達到同步，這一點對于將時空混沌應(yīng)用于保密通信系統(tǒng)很重要。

在生成時空混沌序列時除了給定初始時刻所有格點處的值，還要給定第一個格子處的值，也就是驅(qū)動序列。驅(qū)動序列的選取很重要，它能影響同步性能和產(chǎn)生的時空混沌序列的性能，不影響研究，在本文中數(shù)值模擬時驅(qū)動序列和初值都用MAΤLAB自動生成的隨機序列。

ε=0.8時，系統(tǒng)式（1）的演化圖（3 000步）如圖1所示。

圖1 系統(tǒng)式（1）的時空演化圖

本文中用a(i)(n)，n=1，2，…，N表示一次實驗得到的第i個格子處產(chǎn)生的時空混沌序列，a(10)，即第10個格子處的時間發(fā)展行為如圖2所示。

圖2 a(10)的時間發(fā)展行為

3 偽隨機序列的檢測方法

如果一個序列，一方面它是可以預先確定的，并且是可以重復地生產(chǎn)和復制的；一方面它又具有某種隨機序列的隨機特性（即統(tǒng)計特性），便稱這種序列為偽隨機序列。

偽隨機序列是具有某種隨機特性的確定的序列。其隨機性只能通過統(tǒng)計測試去驗證。檢驗序列是否是偽隨機序列，主要是通過統(tǒng)計測試檢驗序列是否具有一些隨機序列具有的隨機特性。偽隨機序列的統(tǒng)計測試方法有很多，但是需要說明的是，通過所有的測試都不能說明一個偽隨機序列是真隨機的，只是說明序列的隨機性能比較好，如果不能通過某個測試，則說明序列的隨機性能不好。下面介紹幾個主要的二值隨機序列隨機性能優(yōu)劣的檢驗方法。這些方法來自美國商務(wù)部國家標準技術(shù)協(xié)會（NISΤ）于2001年5月公布的FIPS140-2。標準包括16項統(tǒng)計測試，但對時空混沌來講，最主要的測試包括頻率測試、游程測試、譜測試和相關(guān)性測試[14]。

（1）頻率測試：頻率測試的目的是檢驗這個序列中0和1的比例是否近似相等。具體的測試方法如下：

步驟1將0，1組成的序列轉(zhuǎn)換成由-1，1組成的序列，設(shè)序列的長度為n，轉(zhuǎn)換方法為xi=2εi-1，i=1，2，…，n。其中，εi，xi為轉(zhuǎn)化前后的比特值。計算轉(zhuǎn)化后的序列和Sn，即

步驟2計算統(tǒng)計值Sobs，即

步驟3計算判斷標準P-Value的值：

其中，erfc()為互補誤差函數(shù)，即

若P-Value的值小于0.01，則認為測試的系列不是隨機序列；反之，則認為序列是隨機序列。

（2）游程測試：游程是指連續(xù)的0或1的不同長度的子序列，游程測試的目的是計算序列中游程的個數(shù)，并判斷0 和1的游程個數(shù)是否與隨機序列一致。具體測試方法如下：

步驟1對需要檢測的序列進行預處理，計算1在序列中的比例，即

其中，n為序列長度，εj為比特值。

步驟3計算統(tǒng)計值：

其中，r(k)的取值為：若εk=εk+1，則r(k)=1；反之r(k)=0。

步驟4計算判斷標準P-Value的值：

其中，π通過步驟1計算得到，函數(shù)erfc()如式（2）所示。

若P-Value的值小于0.01，則認為測試的序列不是隨機序列；反之，則認為序列是隨機序列。

（3）離散傅里葉變換（譜）測試：離散傅里葉變換（譜）測試的目的是測試序列的周期特性。具體測試方法如下：

步驟1將0，1組成的序列轉(zhuǎn)換成由-1，1組成的序列，設(shè)序列的長度為n，轉(zhuǎn)換方式為xi=2εi-1，i=1，2，…，n。其中，εi，xi為轉(zhuǎn)化前后的比特值。

步驟2對轉(zhuǎn)換后的序列X進行離散傅里葉變換（DFΤ），得到序列S=DFT(X)。設(shè)Sj為S中第j個元素，則

其中，exp(2πik/n)=cos(2πkj/n)+isin(2πkj/n)，j=0，1，…，n-1且

步驟3計算M=mod(S′)，其中S′是由S的前n/2個元素組成的子序列，求模函數(shù)mod()用于產(chǎn)生尖峰高度序列。

步驟4計算作為尖峰高度的95%的閥值。

步驟5計算N0=0.95n/2，表示值小于T的尖峰的期望的理論數(shù)量。

步驟6計算N1，它表示M中實際觀察到的值小于T的尖峰數(shù)量。

若P-Value的值小于0.01，則認為測試的序列不是隨機序列；反之，則認為序列是隨機序列。

（4）相關(guān)特性：相關(guān)特性包括自相關(guān)和互相關(guān)，由于時空混沌同時產(chǎn)生多個序列，只有它們之間的互相關(guān)性滿足要求才能同時使用。期望不同格點產(chǎn)生的混沌序列的自相關(guān)函數(shù)類似于函數(shù)δ，而互相關(guān)函數(shù)的值接近于零。設(shè)a(i)，a(j)代表長度為N的兩個不同的序列，根據(jù)相關(guān)性定義，序列a(i)，a(j)的非周期互相關(guān)函數(shù)為：a?(i)為序列a(i)的平均值。當i=j時，即為自相關(guān)函數(shù)。理想的自相關(guān)特性是當m≠0時，C(m)→0，而互相關(guān)函數(shù)處處為零。在實際中，由于計算精度和序列長度的影響，導致自相關(guān)旁瓣和互相關(guān)函數(shù)不是恒為零，但值很小時（〈0.05），可以認為性能良好。

4 符號函數(shù)二值化方法及其缺陷

最主要的實值序列二值化方法就是符號函數(shù)二值化方法，即

則可由實值混沌序列a(i)(n)產(chǎn)生二進制序列{sngca(i)(n)}。通常取閥值c為序列a(i)(n)的平均值。

本文中用符號sa(i)表示由混沌序列a(i)得到的二值序列。

經(jīng)過檢驗可以發(fā)現(xiàn)由系統(tǒng)（1）產(chǎn)生的混沌序列經(jīng)式（3）產(chǎn)生的混沌二值序列的隨機性能不好。

從一次實驗結(jié)果中抽取幾個格點的混沌序列，序列長度為10 000，對由式（3）得到的二值序列進行隨機性能檢驗，檢驗結(jié)果如表1所示。

表1 用序列均值做閥值得到的二值序列隨機性能檢驗結(jié)果

由表1的數(shù)據(jù)可以看出，得到的二值序列都沒有通過頻率測試和游程測試，而譜測試都通過了。

圖3是由混沌序列a(30)得到的二值序列sa(30)的自相關(guān)圖，圖4是序列a(30)和a(50)得到的二值序列sa(30)和sa(50)的互自相圖，時間間隔?。?00～500。由于自相關(guān)函數(shù)是偶對稱的，所以圖中只顯示單側(cè)的情況。從圖中可以看出，序列的自相關(guān)性和互相關(guān)性的性能是很好的。

圖3 序列sa(30)的自相關(guān)函數(shù)圖

圖4 序列sa(30)和sa(50)的互相關(guān)函數(shù)圖

經(jīng)過大量數(shù)值實驗發(fā)現(xiàn)，由系統(tǒng)（1）產(chǎn)生的混沌序列經(jīng)式（3）產(chǎn)生的混沌二值序列的隨機性能檢驗多數(shù)都不能通過頻率測試和游程測試，這說明符號函數(shù)二值化法是有缺陷的，而導致這種缺陷的原因應(yīng)該是方法中閥值的選擇沒有給出具體的技巧，只有指導性的選擇方法。所以本文有針對性地設(shè)計了改進的時空混沌二值化方法。

5 改進的時空混沌二值化方法

經(jīng)過研究發(fā)現(xiàn)閥值調(diào)整技術(shù)和抽取技術(shù)可以改善得到的二值序列的性能。

5.1 閥值調(diào)整技術(shù)研究

觀察圖2可以發(fā)現(xiàn)混沌序列值在均值上下是分布不均的，經(jīng)過大量研究發(fā)現(xiàn)這種分布是相對固定的，所以采用均值做二值化的閥值得到的二值序列的隨機性能不好?；诖颂攸c，本文研究了均值附近的不同值做閥值的情況。

以一次實驗中第30個格子處得到的混沌序列a(30)為研究對象，序列長度為10 000。圖5顯示了a(30)在相應(yīng)閥值時得到的二值序列sa(30)的頻率測試的檢驗數(shù)，可以看出閥值c在0.64～0.73之間都可以通過測試，0.69時，檢驗數(shù)取得最大值。圖6顯示了a(40)在相應(yīng)閥值時得到的二值序列sa(40)的頻率測試的檢驗數(shù)，可以看出閥值c在0.66～0.70之間都可以通過測試，0.68時，檢驗數(shù)取得最大值。

圖5 不同閥值時sa(30)的檢驗數(shù)

圖6 不同閥值時sa(40)的檢驗數(shù)

定義1用符號函數(shù)二值化方法時，使得到的二值序列的頻率測試檢驗數(shù)最大的閥值稱為最優(yōu)閥值。

經(jīng)過大量實驗研究發(fā)現(xiàn)最優(yōu)閥值總是存在的。任意抽取一次實驗產(chǎn)生的混沌序列進行實驗，序列長度為10 000。表2列出了相應(yīng)序列的均值、頻率測試通過的閥值區(qū)間、最優(yōu)閥值、采用最優(yōu)閥值時得到的二值序列的頻率測試和游程測試的檢驗結(jié)果。

表2 最優(yōu)閥值得到的二值序列的檢驗結(jié)果

由表2可以看出，通過閥值調(diào)整技術(shù)可以使得到的二值序列通過頻率測試，但游程測試仍然沒有通過。實際使用時，可以在平均值附近搜索合適的閥值。但是如果每次使用時都進行最優(yōu)閥值的搜索，則會降低算法效率，增加計算量，通過大量實驗發(fā)現(xiàn)，系統(tǒng)（1）產(chǎn)生的混沌序列具有相對固定的均值和最優(yōu)閥值，最優(yōu)閥值都在0.69左右。在實際使用時，可以采用固定閥值0.69。

5.2 抽取技術(shù)研究

定義2設(shè)有序列(xm)=xm(i)，i=1，2，…，N，序列(xn)= xn(i)，xn(i)=xm(3i)，i=1，2，…，p(N/3)，稱為序列(xm)的抽取比為1/k的子序列。其中p(·)表示取整運算。

先對混沌序列采用抽取技術(shù)再二值化可以提高游程檢測的效果，本文計算了對混沌序列抽取比為1/2、1/3、1/4、1/5的子序列采用最優(yōu)閥值二值化后的二值序列的游程檢驗的情況，以表2中的序列為例，表3列出不同的抽取比之后的相應(yīng)的檢驗數(shù)（采用最優(yōu)閥值）。

由表3可以看出，對混沌序列進行抽取后再用最優(yōu)閥值二值化后可以通過游程測試，但抽取會減小序列的長度，增大計算量，所以沒必要選用過大的抽取比，從表3中可以看出，1/2的抽取就可以。當然，計算量可以接受的情況下，采用1/3的抽取比更好一些。經(jīng)過大量實驗研究發(fā)現(xiàn)對由系統(tǒng)（1）產(chǎn)生的混沌序列采用抽取比1/2的抽取后再用最優(yōu)閥值二值化可以通過游程測試。

表3 不同抽取比得到的二值序列的游程測試檢驗結(jié)果

5.3 閾值調(diào)整技術(shù)和序列抽取技術(shù)相結(jié)合符號函數(shù)二值化法

基于以上研究，本文給出閾值調(diào)整技術(shù)和序列抽取技術(shù)相結(jié)合符號函數(shù)二值化法，具體方法如下：

（2）在得到的序列a(i)k的均值附近進行最優(yōu)閥值的搜索；

（3）用最優(yōu)閥值做閥值用式（3）得到二值序列。

從一次實驗結(jié)果中抽取幾個格點的混沌序列，序列長度為10 000，對序列采用閾值調(diào)整技術(shù)和序列抽取技術(shù)相結(jié)合符號函數(shù)二值化法（取抽取比為1/2，閥值0.69）后得到的二值序列的各項檢驗結(jié)果如表4所示。

表4 二值序列隨機性檢驗結(jié)果（抽取比為1/2，閥值為0.69）

由表4的數(shù)據(jù)可以看出，得到的二值序列通過了所有測試。

圖7是由混沌序列a(30)得到的二值序列sa(30)的自相關(guān)圖，圖8是序列a(30)和a(50)得到的二值序列sa(30)和sa(50)的互相關(guān)函數(shù)圖，時間間隔?。?00～500。從圖中可以看出，序列的自相關(guān)性和互相關(guān)性的性能也是很好的。

對系統(tǒng)（1）不同初值產(chǎn)生的50組（每組64個格點）的長度為2萬位的混沌序列，由上述方法得到的二值序列進行了隨機性能測試，測試結(jié)果全部通過了，說明本文提出的方法是有效的。本文還研究了另一種單向耦合映像格子（COML1）：xn+1(i)=(1-ε)f(xn(i))+εf(xn(i-1))

圖7 序列sa(30)的自相關(guān)函數(shù)圖

圖8 序列sa(30)和sa(50)的互相關(guān)函數(shù)圖

其中f(x)=1-2x2，x∈(-1，1)，n表示離散化后的時間，i表示格子空間坐標。ε為耦合強度，0.75〈ε〈1。

對COML1模型產(chǎn)生的混沌序列也進行了同樣的研究，發(fā)現(xiàn)COML1模型產(chǎn)生的混沌序列用式（3）生成的二值序列具有同樣的特點，不能通過頻率測試和游程測試，而采用本文提出的閥值調(diào)整技術(shù)和抽取技術(shù)相結(jié)合的改進的符號函數(shù)二值化方法后，對隨機得到的二值序列進行檢驗，結(jié)果都通過了檢驗。說明本文提出的方法不僅有效而且有一定的適用性。

6 結(jié)論

本文提出的二值化方法，簡單實用，按這種方法得到的二值序列具有優(yōu)良的偽隨機性能及相關(guān)特性，可以用來作為擴頻序列。這種方法既保留了符號函數(shù)的運算簡單的優(yōu)點，又增強了方法的適用范圍，使得得到的序列滿足使用的要求。兩種技術(shù)可以單獨使用，也可結(jié)合使用，使用的前后順序?qū)Y(jié)果沒有影響，而且可以靈活地和其他的二值化方法結(jié)合使用。相比起文獻[12]中的方法，計算量相當，不需要選擇序列，操作簡單，并且有望對各種類型的耦合映像格子模型都適用。

[1]高俊山.基于混沌理論的加密過程的研究[J].自動化技術(shù)與應(yīng)用，2001（6）：13-16.

[2]Perez G，Cerdeira H A.Extracting messages masked by chaos[J]. Phys Rev Lett，1995，74（11）：1970-1973.

[3]董斌輝，周健勇，黃金源.混沌偽隨機序列生成算法研究[C]//第十一屆“保密通信與信息安全現(xiàn)狀研討會”，2009.

[4]程東升，葉瑞松.基于四維混沌系統(tǒng)生成二值序列的方法及其加密應(yīng)用[J].計算機應(yīng)用，2008，28（3）：677-679.

[5]姚洪興，李萌，杜賢利.一種基于超混沌的二值序列生成方法[J].科學技術(shù)與工程，2008（13）：3508-3512.

[6]戴躍偉，卓成春，茅耀斌，等.一種二值混沌加密序列的產(chǎn)生及其性能分析[J].南京理工大學學報，2001，25（5）：528-531.

[7]李寧，山秀明，任勇，等.一種實用的時空混沌二值化方法[J].系統(tǒng)工程與電子技術(shù)，2002，24（11）：60-63.

[8]彭軍，李學明，張偉，等.基于耦合映像格子模型的時空混沌二值序列及其性能分析[J].計算機科學，2005，32（2）：196-198.

[9]陳宇環(huán)，易稱福，張小紅.二維耦合映象格子混沌序列的二值化及特性研究[J].計算機應(yīng)用與軟件，2009，26（7）：222-224.

[10]李紅燕，楊萬利，羅俊之，等.基于時空混沌系統(tǒng)和脈沖同步控制的加密系統(tǒng)設(shè)計[J].裝甲兵工程學院學報，2012，26（6）：80-84.

[11]林金秋，司錫才，孟維曉，等.基于混沌的一種圖像加密算法[J].計算機應(yīng)用研究，2010，27（2）：697-698.

[12]趙莉，張雪鋒，范九倫.一種改進的混沌序列產(chǎn)生方法[J].計算機工程與應(yīng)用，2006，42（23）：31-33.

[13]Li P，Li Z，Halang W A，et al.A multiple pseudorandom-bit generator based on a spatiotemporal chaotic map[J].Physics Letters A，2006，349（6）：467-473.

[14]劉金梅，屈強.幾類混沌序列的隨機性測試[J].計算機工程與應(yīng)用，2011，47（5）：46-49.

[15]A statistical test suite for random and pseudorandom number generators for cryptographic applications[S].2001.

LI Hongyan,YANG Wanli

Department of Fundamental Courses,Academy of Armored Force Engineering,Beijing 100072,China

According to the characteristic of spatiotemporal chaotic sequences produced by coupled map lattices model,based on the binarization method using sign function,a new binarization method is proposed.Τhe results of randomness and correlation tests show that the randomness of binary sequences given by the new method is good.Moreover these sequences have good correlation.Τhese facts show that the new binarization method proposed in this paper is effective,simple and practive.

spatiotemporal chaos;binarization method;binary sequences;randomness;coupled map lattices

針對耦合映像格子模型產(chǎn)生的時空混沌序列的特點，在符號函數(shù)二值化法的基礎(chǔ)上，給出了一種新的二值化方法。隨機性能和相關(guān)性檢驗的結(jié)果表明按這種方法得到的二值序列具有優(yōu)良的偽隨機性能及相關(guān)特性，說明提出的方法是有效的，而且簡單實用。

時空混沌；二值化方法；二值序列；隨機性能；耦合映像格子

A

ΤN914

10.3778/j.issn.1002-8331.1303-0009

LI Hongyan,YANG Wanli.Research on spatiotemporal chaos binarization method.Computer Engineering and Applications,2013,49（21）：65-69.

國家部委預研基金項目資助；裝甲兵工程學院創(chuàng)新基金項目資助。

李紅燕（1976—），女，講師，研究領(lǐng)域為混沌控制和保密通信。E-mail：lhyshm1@sina.com

2013-03-04

2013-05-13

1002-8331（2013）21-0065-05

CNKI出版日期：2013-06-18http://www.cnki.net/kcms/detail/11.2127.ΤP.20130618.1601.011.html