基于組合混沌的偽隨機數算法研究

張麗娜，何 遠，竇瓊英，羅桂蘭，朱 敏，陳瑞婿

(大理學院數學與計算機學院，云南大理 671003)

在無線通信系統中，通信安全是設計者必須考慮的問題。目前，針對不同的通信系統已經提出了相關的安全協議，但是這些協議往往設計復雜，對硬件要求較高，同時增加了成本。對于計算和存儲資源都有限的嵌入式系統，如RFID系統、無線傳感器網絡等，在實際使用時越來越多的傾向采用偽隨機數來進行系統安全通信的設計〔1〕，所以對偽隨機數算法的研究具有重要的意義。

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

1 組合混沌映射偽隨機數發生器

混沌現象是指在確定系統中出現的一種無規則、類似隨機的現象，產生的序列具有非周期、不可預測、對初始條件和參數極端敏感性等特點。混沌產生的序列具有隨機性，但混沌系統又可以用確定的計算公式表示，利用幾個控制參數就可以恢復混沌序列，傳遞這些參數就可以實現數據的加解密。

1.1 Logistic混沌映射 Logistic混沌映射是一類非常簡單的一維非線性迭代方程，應用廣泛的動力學系統，其迭代公式為：

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

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

Tent映射經過伯努利移位〔7〕，可變換為:

在Tent映射過程中，先給定一個初始值來產生足夠長的迭代值，理論上混沌可以產生隨機數，但在Tent映射迭代過程中，由于計算機字長有限，小數部分的二進制序列經過一定次數的無符號左移運算將趨向于零，即趨向Tent映射的不動點。仔細分析迭代序列不難發現，序列中存在小周期現象。

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

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

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

第一步：取初值x0（x0應避免落入到小周期點內），記入標識組z，z(1)=x0，i=j=1;

第二步：以xn式進行迭代，i自增1，產生x序列；

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

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

第五步：結束。

2 實驗驗證

對改進后算法的初值敏感性、隨機性、遍歷性等混沌特性進行測試，結果表明算法仍具有混沌特性。初值x0取0.861進行500次迭代，得到一個既不收斂，也不呈周期運動的“雜亂無章”的隨機序列，如圖1所示，表明算法可產生較好的偽隨機序列。

圖1 改進的混沌隨機數產生算法的混沌序列時序圖

但某種算法產生的偽隨機數是否是真正意義上的隨機數，需要對所產生的隨機數進行進一步檢驗，一般通過序列是否滿足隨機數所要求的參數檢驗，均勻性檢驗，獨立性檢驗等特征來判斷〔9〕，如果通過則說明算法能產生良好的隨機數序列。

2.1 參數檢驗 均勻隨機數的參數檢驗時檢驗出某個發生器產生的隨機數序列{xi}的均值、方差、一階矩陣、二階矩陣與均勻分布的理論值是否有明顯差異〔10-11〕。

2.2 均勻性檢驗 隨機數的均勻性是用來檢驗由某個發生器產生的隨機數序列{xi}是否均勻地分布在（0,1）區間上，也就是檢驗經驗頻率與理論頻率的差異是否顯著。

假設{xi}均勻分布在（0,1）上，用x2檢驗的方法來看此假設下的計量及其分布。我們將（0,1）等分為k個子區間 I1，I2,…,Ik,則把{xi}等分為k組，記{xi}中落入區間樣本個數為nj（j=1,2,…,k），則落

此式漸進服從x2（k-1）。查對應x2分布表的分布臨界值為123.23，若u4＜123.23則通過均勻性檢驗。

2.3 獨立性檢驗 獨立性檢驗是檢查隨機序列之間的統計相關性是否顯著，若兩個隨機變量獨立，則他們的相關系數為零。樣本的k階自相關系數若||u5＜1.96，則通過獨立性檢驗。

2.43 種方法統計檢驗結果比較 取初值x0為0.861，分別用樣本容量為100,1000,10000進行統計檢驗，結果見表1。從表1可看出，Logistic混沌映射的均勻性較差，Tent混沌映射未通過參數性檢驗，組合的混沌映射在樣本為100時通過所有檢驗，明顯改善了Logistic混沌映射與Tent混沌映射的缺陷。樣本大于1000時組合混沌的獨立性還是存在一定的問題，需進一步進行改善。

表1 3種方法統計檢驗結果比較

3 結束語

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

〔1〕秦雪麗,程明,李偉.基于鐘控非線性序列的RFID偽隨機數發生器設計〔J〕.計算機應用,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〕.儀器儀表學報,2006,27(6):805-807.

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

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

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

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

〔9〕郭利.基于混沌理論的無窮維偽隨機數發生方法及其統計特征〔D〕.武漢：武漢理工大學，2009:11.

〔10〕王光義,袁方.級聯混沌及其動力學特性研究〔J〕.物理學報,2013(2):103-112.

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