張麗娜，何 遠(yuǎn)，竇瓊英，羅桂蘭，朱 敏，陳瑞婿

(大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003)

在無(wú)線通信系統(tǒng)中，通信安全是設(shè)計(jì)者必須考慮的問(wèn)題。目前，針對(duì)不同的通信系統(tǒng)已經(jīng)提出了相關(guān)的安全協(xié)議，但是這些協(xié)議往往設(shè)計(jì)復(fù)雜，對(duì)硬件要求較高，同時(shí)增加了成本。對(duì)于計(jì)算和存儲(chǔ)資源都有限的嵌入式系統(tǒng)，如RFID系統(tǒng)、無(wú)線傳感器網(wǎng)絡(luò)等，在實(shí)際使用時(shí)越來(lái)越多的傾向采用偽隨機(jī)數(shù)來(lái)進(jìn)行系統(tǒng)安全通信的設(shè)計(jì)〔1〕，所以對(duì)偽隨機(jī)數(shù)算法的研究具有重要的意義。

偽隨機(jī)數(shù)發(fā)生器廣泛應(yīng)用于信息安全、數(shù)字通信等諸多重要領(lǐng)域。產(chǎn)生偽隨機(jī)數(shù)的方法很多，如線性同余法反饋位移寄存器法等等。混沌算法的出現(xiàn)為產(chǎn)生隨機(jī)數(shù)提供了一種新的思路。文獻(xiàn)〔2-4〕利用混沌系統(tǒng)生成隨機(jī)密鑰流，該密鑰流直接用于掩蓋明文，實(shí)現(xiàn)混沌序列加解密，但這類加密方案存在混沌隨機(jī)序列離散化后導(dǎo)致的短周期問(wèn)題。所以本文采用組合混沌映射算法進(jìn)行改進(jìn)。

1 組合混沌映射偽隨機(jī)數(shù)發(fā)生器

混沌現(xiàn)象是指在確定系統(tǒng)中出現(xiàn)的一種無(wú)規(guī)則、類似隨機(jī)的現(xiàn)象，產(chǎn)生的序列具有非周期、不可預(yù)測(cè)、對(duì)初始條件和參數(shù)極端敏感性等特點(diǎn)?；煦绠a(chǎn)生的序列具有隨機(jī)性，但混沌系統(tǒng)又可以用確定的計(jì)算公式表示，利用幾個(gè)控制參數(shù)就可以恢復(fù)混沌序列，傳遞這些參數(shù)就可以實(shí)現(xiàn)數(shù)據(jù)的加解密。

1.1 Logistic混沌映射 Logistic混沌映射是一類非常簡(jiǎn)單的一維非線性迭代方程，應(yīng)用廣泛的動(dòng)力學(xué)系統(tǒng)，其迭代公式為：

式中0＜λ≤4，λ為分形參數(shù)。當(dāng)3.5699…＜λ≤4時(shí)，系統(tǒng)處于混沌狀態(tài)。取任意初值X，可迭代出一個(gè)確定的序列X1,X2,X3…,Xn，對(duì)于不同的λ值，系統(tǒng)將呈現(xiàn)不同的狀態(tài)，隨著參數(shù)λ的增加，系統(tǒng)不斷經(jīng)歷倍周期分叉，最終達(dá)到混沌狀態(tài)〔5〕。但Logistic混沌映射存在均勻性不夠好等方面的缺陷〔6〕。

1.2 Tent混沌映射 Tent映射又稱為帳篷映射，其迭代公式為：

Tent映射經(jīng)過(guò)伯努利移位〔7〕，可變換為:

在Tent映射過(guò)程中，先給定一個(gè)初始值來(lái)產(chǎn)生足夠長(zhǎng)的迭代值，理論上混沌可以產(chǎn)生隨機(jī)數(shù)，但在Tent映射迭代過(guò)程中，由于計(jì)算機(jī)字長(zhǎng)有限，小數(shù)部分的二進(jìn)制序列經(jīng)過(guò)一定次數(shù)的無(wú)符號(hào)左移運(yùn)算將趨向于零，即趨向Tent映射的不動(dòng)點(diǎn)。仔細(xì)分析迭代序列不難發(fā)現(xiàn)，序列中存在小周期現(xiàn)象。

1.3 組合混沌映射 文獻(xiàn)〔8〕證明了在兩個(gè)獨(dú)立的離散非負(fù)周期序列 f1(n),f2(n)為常數(shù)序列,N1為序列 f1(n)的最小整數(shù)周期，N2為序列 f2(n)的最小整數(shù)周期，且N1≠N2，則兩個(gè)序列復(fù)合運(yùn)算產(chǎn)生的新序列 f1(n)Θf2(n)最小整數(shù)周期為N1和N2的最小公倍數(shù)。其中序列復(fù)合運(yùn)算符號(hào)Θ取相加“+”、相減“-”、相乘“·”之一。這為延長(zhǎng)混沌最小周期提供了理論基礎(chǔ)。

為了提高Logistic混沌映射的精度，也為了降低Tent混沌映射在選取初值時(shí)的要求，延長(zhǎng)混沌的最小周期，本文將兩者進(jìn)行結(jié)合，使其在選取任意初值時(shí)都能得到良好的偽隨機(jī)序列。先由Logistic混沌映射和Tent混沌映射，生成二維數(shù)據(jù)，通過(guò)降維組合成一維混沌。組合的混沌迭代公式為：

取初值x0，λ取3.5699～4之間的任意值，代入組合函數(shù)中進(jìn)行n次迭代得到隨機(jī)序列{xn}。具體流程如下：

第一步：取初值x0（x0應(yīng)避免落入到小周期點(diǎn)內(nèi)），記入標(biāo)識(shí)組z，z(1)=x0，i=j=1;

第二步：以xn式進(jìn)行迭代，i自增1，產(chǎn)生x序列；

第三步：如果迭代到最大次數(shù)，則跳轉(zhuǎn)到第五步；否則：若x(i)={0,0.25,0.5,0.75}或x(i)=x(i-k),k-{0,1,2,3,4}(即落入不動(dòng)點(diǎn)或5周期以內(nèi)的小循環(huán))，進(jìn)入第四步，否則返回第二步；

第四步：改變迭代初值x(i)=z(j+1)=z(j)+a，j=j+1，返回第二步。

第五步：結(jié)束。

2 實(shí)驗(yàn)驗(yàn)證

對(duì)改進(jìn)后算法的初值敏感性、隨機(jī)性、遍歷性等混沌特性進(jìn)行測(cè)試，結(jié)果表明算法仍具有混沌特性。初值x0取0.861進(jìn)行500次迭代，得到一個(gè)既不收斂，也不呈周期運(yùn)動(dòng)的“雜亂無(wú)章”的隨機(jī)序列，如圖1所示，表明算法可產(chǎn)生較好的偽隨機(jī)序列。

圖1 改進(jìn)的混沌隨機(jī)數(shù)產(chǎn)生算法的混沌序列時(shí)序圖

但某種算法產(chǎn)生的偽隨機(jī)數(shù)是否是真正意義上的隨機(jī)數(shù)，需要對(duì)所產(chǎn)生的隨機(jī)數(shù)進(jìn)行進(jìn)一步檢驗(yàn)，一般通過(guò)序列是否滿足隨機(jī)數(shù)所要求的參數(shù)檢驗(yàn)，均勻性檢驗(yàn)，獨(dú)立性檢驗(yàn)等特征來(lái)判斷〔9〕，如果通過(guò)則說(shuō)明算法能產(chǎn)生良好的隨機(jī)數(shù)序列。

2.1 參數(shù)檢驗(yàn) 均勻隨機(jī)數(shù)的參數(shù)檢驗(yàn)時(shí)檢驗(yàn)出某個(gè)發(fā)生器產(chǎn)生的隨機(jī)數(shù)序列{xi}的均值、方差、一階矩陣、二階矩陣與均勻分布的理論值是否有明顯差異〔10-11〕。

2.2 均勻性檢驗(yàn) 隨機(jī)數(shù)的均勻性是用來(lái)檢驗(yàn)由某個(gè)發(fā)生器產(chǎn)生的隨機(jī)數(shù)序列{xi}是否均勻地分布在（0,1）區(qū)間上，也就是檢驗(yàn)經(jīng)驗(yàn)頻率與理論頻率的差異是否顯著。

假設(shè){xi}均勻分布在（0,1）上，用x2檢驗(yàn)的方法來(lái)看此假設(shè)下的計(jì)量及其分布。我們將（0,1）等分為k個(gè)子區(qū)間 I1，I2,…,Ik,則把{xi}等分為k組，記{xi}中落入?yún)^(qū)間樣本個(gè)數(shù)為nj（j=1,2,…,k），則落

此式漸進(jìn)服從x2（k-1）。查對(duì)應(yīng)x2分布表的分布臨界值為123.23，若u4＜123.23則通過(guò)均勻性檢驗(yàn)。

2.3 獨(dú)立性檢驗(yàn) 獨(dú)立性檢驗(yàn)是檢查隨機(jī)序列之間的統(tǒng)計(jì)相關(guān)性是否顯著，若兩個(gè)隨機(jī)變量獨(dú)立，則他們的相關(guān)系數(shù)為零。樣本的k階自相關(guān)系數(shù)若||u5＜1.96，則通過(guò)獨(dú)立性檢驗(yàn)。

2.43 種方法統(tǒng)計(jì)檢驗(yàn)結(jié)果比較 取初值x0為0.861，分別用樣本容量為100,1000,10000進(jìn)行統(tǒng)計(jì)檢驗(yàn)，結(jié)果見表1。從表1可看出，Logistic混沌映射的均勻性較差，Tent混沌映射未通過(guò)參數(shù)性檢驗(yàn)，組合的混沌映射在樣本為100時(shí)通過(guò)所有檢驗(yàn)，明顯改善了Logistic混沌映射與Tent混沌映射的缺陷。樣本大于1000時(shí)組合混沌的獨(dú)立性還是存在一定的問(wèn)題，需進(jìn)一步進(jìn)行改善。

表1 3種方法統(tǒng)計(jì)檢驗(yàn)結(jié)果比較

3 結(jié)束語(yǔ)

改進(jìn)的混沌算法是由Logistic混沌映射與Tent混沌映射組合而成，性能得到很大的改善。組合過(guò)程中雖然變成了二維映射，但計(jì)算仍是簡(jiǎn)單的，算法只需要提供一個(gè)映射公式，初值和參數(shù)就可得到偽隨機(jī)序列，不必存儲(chǔ)多個(gè)序列的值，大大節(jié)省了存儲(chǔ)空間。算法具有一定的實(shí)用性。

〔1〕秦雪麗,程明,李偉.基于鐘控非線性序列的RFID偽隨機(jī)數(shù)發(fā)生器設(shè)計(jì)〔J〕.計(jì)算機(jī)應(yīng)用,2009(11):112-115.

〔2〕Wang Qianxue,Christophe Guyeux,Jacques M Bahi.A novel pseudo-random number generator based on discrete chaotic iterations〔C〕//The First International Conference on Evolving Internet.2009:71-76.

〔3〕Chen Zhuo,Zhang Zhengwen,Jiang Nan.A Session Key Generator Based on Chaotic Sequence〔C〕//International Conference on Computer Science and Software Engineering.2008:635-637.

〔4〕孫曉輝,林秋華,郝育聞.基于組合混沌映射的偽隨機(jī)數(shù)發(fā)生器〔J〕.儀器儀表學(xué)報(bào),2006,27(6):805-807.

〔5〕韓雙霜,閔樂(lè)泉,臧鴻雁.基于離散廣義混沌同步定理的偽隨機(jī)數(shù)生成器設(shè)計(jì)及性能分析〔J〕.計(jì)算機(jī)應(yīng)用研究,2013,30(5):1511-1514.

〔6〕鄭曉麗,姜迪剛.混沌分組密碼抗差分密碼攻擊的分析〔J〕.通信技術(shù),2013(1):40-42.

〔7〕肖旭韜,張雪鋒.基于線性反饋移位寄存器和組合貓映射的偽隨機(jī)序列生成方法〔J〕.計(jì)算機(jī)應(yīng)用研究,2013,30(1):161-164.

〔8〕孫克輝,賀少波,何毅,等.混沌偽隨機(jī)序列的譜熵復(fù)雜性分析〔J〕.物理學(xué)報(bào),2013,62(1):10501-10501.

〔9〕郭利.基于混沌理論的無(wú)窮維偽隨機(jī)數(shù)發(fā)生方法及其統(tǒng)計(jì)特征〔D〕.武漢：武漢理工大學(xué)，2009:11.

〔10〕王光義,袁方.級(jí)聯(lián)混沌及其動(dòng)力學(xué)特性研究〔J〕.物理學(xué)報(bào),2013(2):103-112.

〔11〕王濤,王煥.改進(jìn)的自適應(yīng)混沌差分進(jìn)化算法〔J〕.計(jì)算機(jī)系統(tǒng)應(yīng)用,2013(2):138-141.